Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Set partitions in Python

I have an array of [1,2,3]

I want to make all the possible combinations using all elements of the array:

Result:

[[1], [2], [3]] [[1,2], [3]] [[1], [2,3]] [[1,3], [2]] [[1,2,3]] 
like image 217
user2880257 Avatar asked Oct 14 '13 20:10

user2880257


People also ask

How do I create a set partition in Python?

To generate set partitions in Python, we can use the more_itertools module. We use list comprehension with mit. set_partitions(lst, k) to create partitions by dividing it with k as the boundary. It returns the part list which has the partition with k as the boundary.

How do you get all the subsets of a list in Python?

Python has itertools. combinations(iterable, n) which Return n length subsequences of elements from the input iterable. This can be used to Print all subsets of a given size of a set.


Video Answer


1 Answers

Since this nice question has been brought back to life, here's a fresh answer.

The problem is solved recursively: If you already have a partition of n-1 elements, how do you use it to partition n elements? Either place the n'th element in one of the existing subsets, or add it as a new, singleton subset. That's all it takes; no itertools, no sets, no repeated outputs, and a total of just n calls to partition():

def partition(collection):     if len(collection) == 1:         yield [ collection ]         return      first = collection[0]     for smaller in partition(collection[1:]):         # insert `first` in each of the subpartition's subsets         for n, subset in enumerate(smaller):             yield smaller[:n] + [[ first ] + subset]  + smaller[n+1:]         # put `first` in its own subset          yield [ [ first ] ] + smaller   something = list(range(1,5))  for n, p in enumerate(partition(something), 1):     print(n, sorted(p)) 

Output:

1 [[1, 2, 3, 4]] 2 [[1], [2, 3, 4]] 3 [[1, 2], [3, 4]] 4 [[1, 3, 4], [2]] 5 [[1], [2], [3, 4]] 6 [[1, 2, 3], [4]] 7 [[1, 4], [2, 3]] 8 [[1], [2, 3], [4]] 9 [[1, 3], [2, 4]] 10 [[1, 2, 4], [3]] 11 [[1], [2, 4], [3]] 12 [[1, 2], [3], [4]] 13 [[1, 3], [2], [4]] 14 [[1, 4], [2], [3]] 15 [[1], [2], [3], [4]] 
like image 58
alexis Avatar answered Sep 30 '22 18:09

alexis