0

Let's say I have a set with n=3 elements: [a,b,c]

Using combinatorics we know that this set has 8 subsets with j elements:

[∅], [a], [b], [c], [a,b], [a,c], [b,c], [a,b,c]

Now what I want to do using Python is print all of the permutations of these 8 subsets with the constraints being that there must be exactly 3 subsets for each permutation (empty subsets are fine), all elements must be used, and alphabetical order must be maintained within each subset (alphabetical order does not need to be maintained outside of the subset--e.g. [c],[a],[b] is fine).

I have attempted something like this: 

x=1
y=3

for i in set(permutations(chain.from_iterable(set_n))):
    while x<=3:
        permuted = sorted([i[:y], i[x:]])
        x = x+1
        y = y-1

    print permuted

Where set_n is my set of n elements, but this of course only gives permutations of two subsets and only a single permutation of those two subsets. It's also not maintaining alphabetical order within the subsets.

martineau
  • 119,623
  • 25
  • 170
  • 301
Daniel
  • 159
  • 1
  • 3
  • 9
  • 1
    What you are looking for is called the [power set](https://en.wikipedia.org/wiki/Power_set). `itertools` has a power set function. See [this answer](https://stackoverflow.com/a/1482316/4408538). – Joseph Wood Mar 03 '18 at 17:58

1 Answers1

1

First, note that a set does not have an implicit ordering: not in Python, not in set algebra.

I suggest that you're attacking the problem from a difficult angle. Rather than finding exactly the permutations you want from the C(8,3) possibilities, why not generate the ones you want, and no more?

Start with empty sub-lists. Iterate through the 3^3 possibilities, placing each letter in the indicated sub-list. Sort the sub-lists and print.

for ai in range(3):
    for bi in range(3):
        for ci in range(3):
            permute = [ [], [], [] ]
            permute[ai].append('a')    
            permute[bi].append('b')    
            permute[ci].append('c')
            print(permute)

Output:

[['a', 'b', 'c'], [], []]
[['a', 'b'], ['c'], []]
[['a', 'b'], [], ['c']]
[['a', 'c'], ['b'], []]
[['a'], ['b', 'c'], []]
[['a'], ['b'], ['c']]
[['a', 'c'], [], ['b']]
[['a'], ['c'], ['b']]
[['a'], [], ['b', 'c']]
[['b', 'c'], ['a'], []]
[['b'], ['a', 'c'], []]
[['b'], ['a'], ['c']]
[['c'], ['a', 'b'], []]
[[], ['a', 'b', 'c'], []]
[[], ['a', 'b'], ['c']]
[['c'], ['a'], ['b']]
[[], ['a', 'c'], ['b']]
[[], ['a'], ['b', 'c']]
[['b', 'c'], [], ['a']]
[['b'], ['c'], ['a']]
[['b'], [], ['a', 'c']]
[['c'], ['b'], ['a']]
[[], ['b', 'c'], ['a']]
[[], ['b'], ['a', 'c']]
[['c'], [], ['a', 'b']]
[[], ['c'], ['a', 'b']]
[[], [], ['a', 'b', 'c']]

Yes, this is brute-force. Simplifications (e.g. see itertools.product) are left as an exercise for the reader. :-)

Prune
  • 76,765
  • 14
  • 60
  • 81