I have a list of numbers, how to generate all unique k-partitions?

Question

So if I had the numbers [1,2,2,3] and I want k=2 partitions I'd have [1][2,2,3], [1,2][2,3], [2,2][1,3], [2][1,2,3], [3][1,2,2], etc.

Answer 1

Python solution:

pip install PartitionSets

Then:

import partitionsets.partition
filter(lambda x: len(x) == k, partitionsets.partition.Partition(arr))

The PartitionSets implementation seems to be pretty fast however it's a pity you can't pass number of partitions as an argument, so you need to filter your k-set partitions from all subset partitions.

You may also want to look at: similar topic on researchgate.

Answer 2

Here's a version in Haskell:

import Data.List (nub, sort, permutations)

parts 0 = []
parts n = nub $ map sort $ [n] : [x:xs | x <- [1..n`div`2], xs <- parts(n - x)]

partition [] ys result = sort $ map sort result
partition (x:xs) ys result = 
  partition xs (drop x ys) (result ++ [take x ys])

partitions xs k = 
  let variations = filter (\x -> length x == k) $ parts (length xs)
  in nub $ concat $ map (\x -> mapVariation x (nub $ permutations xs)) variations
    where mapVariation variation = map (\x -> partition variation x [])


OUTPUT:
*Main> partitions [1,2,2,3] 2
[[[1],[2,2,3]],[[1,2,3],[2]],[[1,2,2],[3]],[[1,2],[2,3]],[[1,3],[2,2]]]

Answer 3

user3569's solution at Code Review produces five 2-tuples for the test case below, instead of exclusively 3-tuples. However, removing the frozenset() call for the returned tuples leads to the code returning exclusively 3-tuples. The revised code is as follows:

from itertools import chain, combinations

def subsets(arr):
    """ Note this only returns non empty subsets of arr"""
    return chain(*[combinations(arr,i + 1) for i,a in enumerate(arr)])

def k_subset(arr, k):
    s_arr = sorted(arr)
    return set([i for i in combinations(subsets(arr),k) 
               if sorted(chain(*i)) == s_arr])

s = k_subset([2,2,2,2,3,3,5],3)

for ss in sorted(s):
    print(len(ss)," - ",ss)

As user3569 says "it runs pretty slow, but is fairly concise".

(EDIT: see below for Knuth's solution)

The output is:

3  -  ((2,), (2,), (2, 2, 3, 3, 5))
3  -  ((2,), (2, 2), (2, 3, 3, 5))
3  -  ((2,), (2, 2, 2), (3, 3, 5))
3  -  ((2,), (2, 2, 3), (2, 3, 5))
3  -  ((2,), (2, 2, 5), (2, 3, 3))
3  -  ((2,), (2, 3), (2, 2, 3, 5))
3  -  ((2,), (2, 3, 3), (2, 2, 5))
3  -  ((2,), (2, 3, 5), (2, 2, 3))
3  -  ((2,), (2, 5), (2, 2, 3, 3))
3  -  ((2,), (3,), (2, 2, 2, 3, 5))
3  -  ((2,), (3, 3), (2, 2, 2, 5))
3  -  ((2,), (3, 5), (2, 2, 2, 3))
3  -  ((2,), (5,), (2, 2, 2, 3, 3))
3  -  ((2, 2), (2, 2), (3, 3, 5))
3  -  ((2, 2), (2, 3), (2, 3, 5))
3  -  ((2, 2), (2, 5), (2, 3, 3))
3  -  ((2, 2), (3, 3), (2, 2, 5))
3  -  ((2, 2), (3, 5), (2, 2, 3))
3  -  ((2, 3), (2, 2), (2, 3, 5))
3  -  ((2, 3), (2, 3), (2, 2, 5))
3  -  ((2, 3), (2, 5), (2, 2, 3))
3  -  ((2, 3), (3, 5), (2, 2, 2))
3  -  ((2, 5), (2, 2), (2, 3, 3))
3  -  ((2, 5), (2, 3), (2, 2, 3))
3  -  ((2, 5), (3, 3), (2, 2, 2))
3  -  ((3,), (2, 2), (2, 2, 3, 5))
3  -  ((3,), (2, 2, 2), (2, 3, 5))
3  -  ((3,), (2, 2, 3), (2, 2, 5))
3  -  ((3,), (2, 2, 5), (2, 2, 3))
3  -  ((3,), (2, 3), (2, 2, 2, 5))
3  -  ((3,), (2, 3, 5), (2, 2, 2))
3  -  ((3,), (2, 5), (2, 2, 2, 3))
3  -  ((3,), (3,), (2, 2, 2, 2, 5))
3  -  ((3,), (3, 5), (2, 2, 2, 2))
3  -  ((3,), (5,), (2, 2, 2, 2, 3))
3  -  ((5,), (2, 2), (2, 2, 3, 3))
3  -  ((5,), (2, 2, 2), (2, 3, 3))
3  -  ((5,), (2, 2, 3), (2, 2, 3))
3  -  ((5,), (2, 3), (2, 2, 2, 3))
3  -  ((5,), (2, 3, 3), (2, 2, 2))
3  -  ((5,), (3, 3), (2, 2, 2, 2))

Knuth's solution, as implemented by Adeel Zafar Soomro on the same Code Review page can be called as follows if no duplicates are desired:

s = algorithm_u([2,2,2,2,3,3,5],3)
ss = set(tuple(sorted(tuple(tuple(y) for y in x) for x in s)))

I haven't timed it, but Knuth's solution is visibly faster, even for this test case.

However, it returns 63 tuples rather than the 41 returned by user3569's solution. I haven't yet gone through the output closely enough to establish which output is correct.

Answer 4

See an answer in Python at Code Review.