There are existing questions about how to generate all possible permutations of a list.
But I need to generate all possible preorders. A preorder on a list is essentially a partition of the list, together with a permutation of those partitions. Is there an efficient way to generate all of these?
One way to do it would be to first generate all permutations of the list, and then use something like this to generate all partitions consistent with that permutation.
But this would be wasteful, because two permutations that only differ in the internal ordering of elements inside each part should be considered the same.
Is there an efficient way to do this?
1