Set Partition Generation | Algorithms Notes

Set Partition Generation | Algorithms Notes

Design an algorithm to generate all partition of a set. Solution: We represent each set partition by a  restricted growth string  c, where c[i] is the number of the set that i-th element belongs to. Initially, all elements are in the first set. To find the next partition, we find the right most element so that c[i] is less than c[j] + 1, for some j < i. Then, we increment c[i] by one and set c[k] to one for all k > i. One easy recursive version is proposed in [1]. Optimized iterative version can be found in [2]. Minimal change order can be found in [3]. [1] M. C. Er, " A fast algorithm for generating set partitions," The Computer Journal Volume 31 Issue 3, June 1988 Pages 283 – 284 [2] B. Djokic M. Miyakawa S. Sekiguchi I. Semba I. Stojmenovic, "A fast iterative algorithm for generating set partitions," The Computer Journal Volume 32 Issue 3, June 1989 Pages 281-282 [3] Richard Kaye, "A gray code for set partitions," Information Processing Letters Volume 5, Issue 6, December 1976,

Read full article from Set Partition Generation | Algorithms Notes