Set ordered partitions in Python of maximum size n

Question

I have a problem which is similar to the following but not quite exactly the same: Set partitions in Python

So I would like to achieve the same result as this other question, but I would like to block the maximum number of partitions to n, and only get ordered partitions. Also, the values in the partitions should be unique. As an example, the example from the question yielded the following partition for range(1,5)

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

As in my case, I would like to only obtain the following:

1 [[1, 2, 3, 4]]
2 [[1], [2, 3, 4]]
3 [[1, 2], [3, 4]]
4 [[1], [2], [3, 4]]
5 [[1, 2, 3], [4]]
6 [[1], [2, 3], [4]]
7 [[1, 2], [3], [4]]
8 [[1], [2], [3], [4]]

Furthermore, I would like to be able to block the number of partitions to a number n. If I take an example where n=2, the following would need to be yielded:

1 [[1, 2, 3, 4]]
2 [[1], [2, 3, 4]]
3 [[1, 2], [3, 4]]
4 [[1, 2, 3], [4]]

Please bear in mind that the ultimate array I will be working on will be of size greater than 1,000, and therefore is why I would like the algorithm to be efficient, but be able to block it to n partitions.

• jspurim: Keep in mind, if you have N elements and block to k partitions you will have O(N^k) posible partitions, which is a lower bound for your solution complexity.
• jspurim: Actually, you would have exactly CnR(N-1, k-1) possible partitions. Imagine you have N-1 positions to place k-1 separators. Since CnR(N-1, k-1) is the size of your output you can not compute this faster than that. This would only be viable for values of k really close to 0 or N
• przemo_li: Will values be unique? [1,2,3] vs [1,2,2] If former, should output treat those unique values as different elements?
• Eric B: @jspurim actually, this is the main reason why I would like to limit the partitions k to a low number. For your information, I am trying to reproduce the MIC score I found online: science.sciencemag.org/content/334/6062/1518. The partition is actually part of their algorithm. Reading the article, I have the feeling that if I have N values, a partition of (N^0.6)^0.5 would do the job. So for 1,000 results, a maximum of 8-10 parititons size would be good.
• Eric B: @przemo_li yes, values should be unique, I will edit my question thank you

Answer 1

As mentioned in the comments, with n distinct elements and k blocks or slices, it is sufficient to generate all choices of putting k-1 separators in n-1 possible positions:

from itertools import combinations
def segmentations(a, k):
 n = len(a)
 assert 1 <= k <= n, (n, k)
 def split_at(js):
 i = 0
 for j in js:
 yield a[i:j]
 i = j
 yield a[i:]
 for separations in combinations(range(1, n), k - 1):
 yield list(split_at(separations))

This generates divisions into exactly k parts, and it is trivial to modify it to generate up to k parts. It also makes it clear that there are indeed C(n-1, k-1) elements in the result for exactly k parts. Now, C(1000, 8) is 24,115,080,524,699,431,125. Probably better to try a different approach altogether?

• Eric B: Thanks, your answer seems to be working fine, but like you said, probably too many combinations..!! I will try to think about it for alternatives for what I want to do, many thanks!