0

Here is what I am trying to do. Given a number k and a set of numbers, I want to partition the set with elements of size not bigger than k.

Ex) lst = [1, 2, 3, 4], k=2

All possible set partition of lst is as follows. codes are in previous question below: (Set partitions in Python)

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]]

However, the size of each element of each partition should not exceed k = 2. All the case where any subset has more than k=2 elements should be deleted. Therefore, the result should be as follows:

3 [[1, 2], [3, 4]]
5 [[1], [2], [3, 4]]
7 [[1, 4], [2, 3]]
8 [[1], [2, 3], [4]]
9 [[1, 3], [2, 4]]
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]]

Would there be an algorithm in python?

lollpang
  • 1
  • Welcome to SO. This isn't a discussion forum or tutorial. Please take the [tour] and take the time to read [ask] and the other links found on that page. Invest some time with [the Tutorial](https://docs.python.org/3/tutorial/index.html) practicing the examples. It will give you an idea of the tools Python offers to help you solve your problem. [“Can someone help me?” not an actual question?](https://meta.stackoverflow.com/questions/284236/why-is-can-someone-help-me-not-an-actual-question). – wwii May 19 '22 at 13:55
  • `Would there be an algorithm..?` - Are you looking for an actual code solution or a written description of an algorithm? – wwii May 19 '22 at 13:56
  • [https://docs.python.org/3/library/itertools.html#itertools.combinations](https://docs.python.org/3/library/itertools.html#itertools.combinations) may be of use. – wwii May 19 '22 at 13:58
  • Seems similar: Does [Python: Finding random k-subset partition for a given list](https://stackoverflow.com/questions/45829748/python-finding-random-k-subset-partition-for-a-given-list) answer your question? – wwii May 19 '22 at 14:34
  • Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. – Community May 19 '22 at 14:40
  • If you don't mind *generating* the unwanted partitions, can't they be excluded with a simple check of their length? – wwii May 19 '22 at 14:40
  • I see you numbered them. So order is important? – Kelly Bundy May 19 '22 at 14:45

1 Answers1

0

Filter the result of an answer posted in the link you provided by length. For example with more_itertools.set_partitions if you want to avoid technicality (not in the standard library).

p = [[[1, 2, 3, 4]],
[[1], [2, 3, 4]],
[[1, 2], [3, 4]],
[[1, 3, 4], [2]],
[[1], [2], [3, 4]],
[[1, 2, 3], [4]],
[[1, 4], [2, 3]],
[[1], [2, 3], [4]],
[[1, 3], [2, 4]],
[[1, 2, 4], [3]],
[[1], [2, 4], [3]],
[[1, 2], [3], [4]],
[[1, 3], [2], [4]],
[[1, 4], [2], [3]],
[[1], [2], [3], [4]]]

def filter_partition(partitions, k):
   return [p for p in partitions if all(len(block)<=k for block in p)]


print(*filter_partition(p, 2), sep='\n')

Output

[[1, 2], [3, 4]]
[[1], [2], [3, 4]]
[[1, 4], [2, 3]]
[[1], [2, 3], [4]]
[[1, 3], [2, 4]]
[[1], [2, 4], [3]]
[[1, 2], [3], [4]]
[[1, 3], [2], [4]]
[[1, 4], [2], [3]]
[[1], [2], [3], [4]]
cards
  • 2,194
  • 1
  • 3
  • 21