restart; delta := (a,b) -> `if`(a=b, 1, 0); # Kronecker delta function Zio2JEkiYUc2IkkiYkdGJUYlNiRJKW9wZXJhdG9yR0YlSSZhcnJvd0dGJUYlLUkjaWZHJSpwcm90ZWN0ZWRHNiUvOSQ5JSIiIiIiIUYlRiVGJQ== # Knuth, Donald E., The Art of Computer Programming (Fascicle 3B), # Combinatorial Algorithms Generating All Combinations and Partitions, # Section 7.2.1.5. Generating all set partitions RestrictedGrowthStrings := proc(n) description "Algorithm H (Restricted growth strings in lexicographic order.)"; local a, b, m, state, j, S; state := 1: S := {}; while state > 0 do if state = 1 then a := Array(1 .. n, fill=0): b := Array(1 .. n-1, fill=1): m := 1: state := 2; elif state = 2 then if a[n] = m then state := 4 else state := 3 end if; elif state = 3 then a[n] := a[n] + 1; state := 2 elif state = 4 then j := n - 1; while a[j] = b[j] do j := j - 1 end do; state := 5 elif state = 5 then if j = 1 then state := -1 else a[j] := a[j] + 1; state := 6 end if elif state = 6 then m := b[j] + delta(a[j], b[j]); j := j + 1; while j < n do a[j] := 0; b[j] := m; j := j + 1 end do; a[n] := 0; state := 2 else state := -1 end if; S := S union {convert(a, list)}; end do; S; end proc: n := 4: S := RestrictedGrowthStrings(n); nops(S); combinat[bell](n); # The number of partitions of the integers 1 .. n is equal to the n'th Bell number. PDE3JiIiIUYkRiRGJDcmRiRGJEYkIiIiNyZGJEYkRiZGJDcmRiRGJEYmRiY3JkYkRiRGJiIiIzcmRiRGJkYkRiQ3JkYkRiZGJEYmNyZGJEYmRiRGKjcmRiRGJkYmRiQ3JkYkRiZGJkYmNyZGJEYmRiZGKjcmRiRGJkYqRiQ3JkYkRiZGKkYmNyZGJEYmRipGKjcmRiRGJkYqIiIk IiM6 IiM6 # Use ListTools[Categorize] to partition the integers 1..n using restricted growth strings. # For each element of set S, Categorize the elements of list L according to a routine that takes an element of S L := [seq(i, i = 1 .. n)]; f := (a,b) -> s[a] = s[b]: LL := NULL: for s in S do t := ListTools[Categorize](f, L); LL := LL, [t] end do: LL; nops([LL]); # How many partitions are there? combinat[bell](n); # How many partitions should there be? NyYiIiIiIiMiIiQiIiU= NjE3IzcmIiIiIiIjIiIkIiIlNyQ3JUYlRiZGJzcjRig3JDclRiVGJkYoNyNGJzckNyRGJUYmNyRGJ0YoNyVGMEYuRis3JDclRiVGJ0YoNyNGJjckNyRGJUYnNyRGJkYoNyVGN0Y1Ris3JDckRiVGKDckRiZGJzckNyNGJTclRiZGJ0YoNyVGPkY8Ris3JUY7RjVGLjclRj5GOEYuNyVGPkY1RjE3JkY+RjVGLkYr IiM6 IiM6