2

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.

Eric B
  • 1,635
  • 4
  • 13
  • 27
  • 3
    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 Aug 22 '17 at 14:25
  • 2
    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` – jspurim Aug 22 '17 at 14:29
  • Will values be unique? [1,2,3] vs [1,2,2] If former, should output treat those unique values as different elements? – przemo_li Aug 22 '17 at 14:35
  • @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: http://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 Aug 22 '17 at 14:44
  • @przemo_li yes, values should be unique, I will edit my question thank you – Eric B Aug 22 '17 at 14:44
  • Assuming `k` is reasonably small I would use complete search with backtracking to solve this problem. Each time you reach a leave in your recursion tree you add that partition to your result set. Keep in mind your problem is isomorphic to the problem of finding all the ways to add up to N with k numbers, which may be useful to construct your backtracking algorithm by representing each partition as a list of `k` integers. I'm a bit busy now but I'll provide a code example later if no one does so before. – jspurim Aug 22 '17 at 15:31
  • I will give it a try, if i find something, I will post it as an answer, as a starting point. Thanks! – Eric B Aug 22 '17 at 16:19
  • "and only get ordered partitions" -> you mean partitions of consecutive elements? cause for instance `4 [[1, 3, 4], [2]]` is ordered (sorted) it just has gaps. As for the "uniqueness" requirement, it seems completely redundant - we are talking about _set_ partitions - this would never have duplicates to begin with, correct? – Mr_and_Mrs_D Jan 18 '22 at 11:21

1 Answers1

2

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?

  • 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! – Eric B Aug 23 '17 at 12:55