How to find the combination of a list to a list without rearrangement?

Question

I am want to achieve all possible combinations (w/o rearr.) of partitioning/breaking the string by k elements.

for example, I have a string "abcd" and k=3, I want achieve the following,

if [a,b,c,d] and k=3 then return,
[ [ [a],   [b],   [c,d] ]
  [ [a],   [b,c], [d]   ]
  [ [a,b], [c],   [d]   ] ]

for example, I have a string "abcde" and k=3, I want achieve the following,

if [a,b,c,d,e] and k=3 then return,
[ [ [a],     [b],     [c,d,e] ]
  [ [a],     [b,c,d], [e]     ]
  [ [a,b,c], [d],     [e]     ]
  [ [a],     [b,c],   [d,e]   ]
  [ [a,b],   [c],     [d,e]   ]
  [ [a,b],   [c,d],   [e]     ] ]

Note, that all the combinations have the a-b-c-d(-e) are in straight order i.e. without rearrangement.

Let's say there's a function "breaklist" which does the work, takes the list and breaks it into k elements of the combination of the elements in the list (w/o rearr.) and finally, returns me a three-dimensional array.

def breakList(l: list, k: int):
    ...
    return partitionedList

My Logic:

1. Let's say the size of the string be, "z=len(string)" and "k" be an integer by which the string is to be divided.
2. Now by observation, the maximum size of a element of the combination is "z-k+1", let that be n.
3. Now start from the first index, go till "n" and the rest by "j=1" then saves in a 3D Array.
4. Next iteration, will be the same by decrement of n by 1 i.e. "n-1" and the rest by "j=2" then saves to the 3D Array.
5. Next iteration, will decrement n by another 1 i.e. "(n-1)-1" and the rest by "j=3" then saves to the 3D Array.
6. "j" runs till "n", and, "n" runs to 1
7. This gives all the combination w/o rearrangement.

But this is not the most efficient approach I came up with, and at the same time it makes the task somewhat complex and time-consuming. So, is there any better approach (I know there is...)? and also can I simplify the code (in terms of number of lines of codes) by using python3?

Answer 1

There's a better way... As mentioned in the referenced question, you just need to re-focus your thinking on the slice points. If you want 3 segments, you need 2 partitions. These partitions are all of the possible combinations of index positions between [1, end-1]. Sounds like a job for itertools.combinations!

This is only a couple lines of code, with the most complicated piece being the printout, and if you don't need to print, it gets easier.

from itertools import combinations as c

data = list('abcdefg')
k = 3

slice_point_sets = c(range(1, len(data)), k-1)

# do the slicing
for point_set in slice_point_sets:
    start = 0
    for end in point_set:
        print(data[start:end], end=',')
        start = end
    print(data[end:])

# or pop it into a 3d array...
slice_point_sets = c(range(1, len(data)), k-1)
result = []
for point_set in slice_point_sets:
    sublist = []
    start = 0
    for end in point_set:
        sublist.append(data[start:end])
        start = end
    sublist.append(data[end:])
    result.append(sublist)

Output:

['a'],['b'],['c', 'd', 'e', 'f', 'g']
['a'],['b', 'c'],['d', 'e', 'f', 'g']
['a'],['b', 'c', 'd'],['e', 'f', 'g']
['a'],['b', 'c', 'd', 'e'],['f', 'g']
['a'],['b', 'c', 'd', 'e', 'f'],['g']
['a', 'b'],['c'],['d', 'e', 'f', 'g']
['a', 'b'],['c', 'd'],['e', 'f', 'g']
['a', 'b'],['c', 'd', 'e'],['f', 'g']
['a', 'b'],['c', 'd', 'e', 'f'],['g']
['a', 'b', 'c'],['d'],['e', 'f', 'g']
['a', 'b', 'c'],['d', 'e'],['f', 'g']
['a', 'b', 'c'],['d', 'e', 'f'],['g']
['a', 'b', 'c', 'd'],['e'],['f', 'g']
['a', 'b', 'c', 'd'],['e', 'f'],['g']
['a', 'b', 'c', 'd', 'e'],['f'],['g']

Answer 2

I think this could work:

1. Get all possible sum partitions of the len(your_list).
2. Filter them by len(partition) == k.
3. Get the itertools.permutations by k elements of all this partitions.
   Now you have list of lists like this: [(1, 1, 2), (1, 2, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 1, 1)]
4. Clean up this list of duplicates (make the set): {(1, 2, 1), (2, 1, 1), (1, 1, 2)}
5. For each permutation pick exact number elements from your_list:
   (1, 1, 2) -> [[a], [b], [c, d]],
   (1, 2, 1) -> [[a], [b, c], [d]],
   and so on..

---

Code

import itertools as it

start_list = ['a', 'b', 'c', 'd', 'e']
k = 3

def partitions(n, k=None): # step 1 function
    if k is None:
        k = n

    if n == 0:
        return []

    return ([[n]] if n<=k else []) + [
        l + [i]
        for i in range(1, 1+min(n, k))
        for l in partitions(n-i, i)]

final_list = []

partitions = filter(lambda x: len(x)==k, partitions(len(start_list))) # step 1-2
for partition in partitions:
    pickings = set(it.permutations(partition, k)) # step 3-5
    for picking in pickings:
        temp = []
        i = 0
        for e in picking: # step 6
            temp.append(start_list[i:i+e])
            i += e
        final_list.append(temp)
print(*final_list, sep='\n')