Spliting a list into n uneven buckets with all combinations

Question

I have a list like:

lst = [1,2,3,4,5,6,7,8,9,10]

and I want to get the combination of all splits for a given n bucket without changing the order of the list. Output exp for n=3:

[
 [1],[2],[3,4,5,6,7,8,9,10],
 [1],[2,3],[4,5,6,7,8,9,10],
 [1],[2,3,4],[5,6,7,8,9,10],
 .
 .
 .
 [1,2,3,4,5,6,7,8],[9],[10],
]

Python is the language I use but if you can direct me to an algorithm that would nice as well. I see this problem is usually apllied on strings. But couldn't figure it out on the list.

P.S. this is my first question. Any feedback is appreciated on how to improve the question.

You could start with the answers to [this question](https://stackoverflow.com/questions/19368375/set-partitions-in-python/61141601) and filter out the results that specifically have 3 sublists. There's more discussion about algorithms on [this CodeReview question](https://codereview.stackexchange.com/questions/1526/finding-all-k-subset-partitions). — Mark Reed, Sep 01 '21 at 14:53

score 4 · Accepted Answer · answered Sep 01 '21 at 14:59

Try:

from itertools import product


def generate(n, l):
    for c in product(range(1, l), repeat=n - 1):
        s = sum(c)
        if s > l - 1:
            continue
        yield *c, l - s


lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n = 3

for groups in generate(n, len(lst)):
    l, out = lst, []
    for g in groups:
        out.append(l[:g])
        l = l[g:]
    print(out)

Prints:

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

user2390182 · Answer 2 · 2021-09-01T15:19:43.807

For a manual implementation, you could use a recursive generator function:

def parts(lst, n):
    if 0 < n <= len(lst):
        if n == 1:
            yield [lst]
        else:
            for i in range(1, len(lst)-n+2):
                for part in parts(lst[i:], n-1):
                    yield [lst[:i]] + part



pprint(list(parts([1,2,3,4], 3)))
# [[[1], [2], [3, 4]], 
#  [[1], [2, 3], [4]], 
#  [[1, 2], [3], [4]]]
pprint(list(parts([1,2,3,4,5,6], 3)))
# [[[1], [2], [3, 4, 5, 6]],
#  [[1], [2, 3], [4, 5, 6]],
#  [[1], [2, 3, 4], [5, 6]],
#  [[1], [2, 3, 4, 5], [6]],
#  [[1, 2], [3], [4, 5, 6]],
#  [[1, 2], [3, 4], [5, 6]],
#  [[1, 2], [3, 4, 5], [6]],
#  [[1, 2, 3], [4], [5, 6]],
#  [[1, 2, 3], [4, 5], [6]],
#  [[1, 2, 3, 4], [5], [6]]]

score 2 · Answer 3 · edited Jul 21 '22 at 13:01

A slightly shorter recursive approach:

lst, n = [1,2,3,4,5,6,7,8,9,10], 3
def group(d, c = []):
   if not d and len(c) == n:
      yield c
   if d and c:
       yield from group(d[1:], c[:-1]+[c[-1]+[d[0]]])
   if d and len(c) < n:
       yield from group(d[1:], c+[[d[0]]])

print(list(group(lst)))

Output:

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

Spliting a list into n uneven buckets with all combinations

3 Answers3