Generate the partition of a set

Asked Jun 19 '18 at 13:39

Active Jun 19 '18 at 13:58

Viewed 534 times

Given a string like xyz i would like to generate the partition of a set. NOT a power set but only pairings one can construct the original string from (see example below).

def get_pairings(a_string):
    # return a list of lists where each list contains 
    # lists that together contain all the characters of a_string

Example

Given the string xyz, the function get_pairings shall return:

[
 [['x'], ['y'], ['z']], 
 [['z'], ['x', 'y']], 
 [['x'], ['y', 'z']], 
 [['y'], ['x', 'z']],
 [['x', 'y', 'z']]
]

Given the string xy, the result would be:

[
 [['x'], ['y']],
 [['x', 'y']]
]

How is this possible in python?

Thanks for your help!

edited Jun 19 '18 at 13:58

asked Jun 19 '18 at 13:39

BetterSaveThanSorry

No i don't mean a power set. I am only looking for pairings that all together construct the original string. – BetterSaveThanSorry Jun 19 '18 at 13:44
Your example, demostrates a power set. – Samer Tufail Jun 19 '18 at 13:45
How do you want duplicates to be handled? If the string is `xxy`, should there be two items in the result set that are `[['x'], ['x', 'y']]`? – lxop Jun 19 '18 at 13:46
2

@SamerTufail No, it doesn't. `{{}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}` is the power set which is nowhere near what the OP wants. – user2390182 Jun 19 '18 at 13:47
The difference between a straight up powerset and what OP wants is the outputs are joined in a way that inside the list they can create the input. There is a slight difference. – Sqoshu Jun 19 '18 at 13:48
No, the power set of `xyz` would be: `{{}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}`. I am looking for all possible pairings of `xyz` to construct `xyz`. – BetterSaveThanSorry Jun 19 '18 at 13:49
@Ixop the most inner list which contains the characters should be treated as a set. So order does not matter and no duplicates. – BetterSaveThanSorry Jun 19 '18 at 13:50
2

What you are looking for is a list of all ["set partitions"](https://en.wikipedia.org/wiki/Partition_of_a_set) of your initial pool. – user2390182 Jun 19 '18 at 13:51
Yes, blind me, misunderstood. – Samer Tufail Jun 19 '18 at 13:52
@schwobaseggl YES, set partitions, that's it! – BetterSaveThanSorry Jun 19 '18 at 13:53
You just asked [a very similar question](https://stackoverflow.com/q/50925906/857390). Please do not multi-post. – Florian Brucker Jun 19 '18 at 14:00

Generate the partition of a set

0 Answers0