-1

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
  • 3,936
  • 1
  • 7
  • 25
  • I wish there was a faster way to generate those, beyond n = 13 it's quite slow... – jokoon Aug 20 '22 at 12:58
  • @jokoon It is quite brute-force... so not very efficient. I haven't gotten any feedback so I haven't tried to reimplement it. At the moment I would recommend you to look at the answer of _alexis_ in the link provided in the question and "inject" the condition of the size directly in its solution – cards Aug 21 '22 at 19:39
  • I did, but it's still pretty slow. – jokoon Aug 21 '22 at 19:45
  • Mmm... just an input for a new reimplementation: I think the problem is related to Stirling Numbers of II-kind, [see](https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind). I will give it a try... – cards Aug 21 '22 at 20:37
  • I was using set partitions to brute force a bin packing problem, so I've changed my approach and I might not need set partitions. – jokoon Aug 21 '22 at 21:23