The problem is to, given an array, write a generator function that will yield all combinations of cutting the array into consistent pieces(arrays of elements that are consecutive in the given array) of any size and which together make up the whole given array. The elements in any one of the combinations don't have to be of the same size. For example given an array [1,2,3,4] I want to yield: [[1],[2],[3],[4]] [[1,2],[3],[4]] [[1],[2,3],[4]] [[1],[2],[3,4]] [[1,2],[3,4]] [[1],[2,3,4]] [[1,2,3],[4]] [[1,2,3,4]]

def powerset_but_consistent(T):

    if len(T)==0:
        return

    for el in T:
        yield el
        for k in range(len(el)):
            yield ([el[:k],el[k:]])
            #for l in range(k, len(el)):
            #    yield ([el[:k],el[k:l],el[l:]])
            powerset_but_consistent([T[:k],T[k:]])


T = [[1,2,3,4,5]]
subsets = [x for x in powerset_but_consistent(T)]
for i in subsets:
    print(i)

And this prints only those combinations that are made of two arrays. If I uncomment what I commented then it will also print combinations consisting of 3 arrays. If I add another inner for loop, it will print those combinations consisting of 4 arrays and so on... How can I use recursion instead of infinite inner for loops? Is it time for using something like: for x in powerset_but_consistent(T[some_slicing] or something else) ? I find it difficult to understand this construction. Can anyone help?

CodePudding user response：

One of the algorithm commonly used for these type of questions (permutations and combinations) is using depth-first-search (DFS). Here's a link to a more similar but harder leetcode problem on palindrome partitioning that uses backtracking and DFS. My solution is based off of that leetcode post.

Algorithm

If my explanation is not enough go through the leetcode link provided above it may make sense.

The general idea is iteration through the list and get all the combinations from current element by resursively traversing through the remaining elements after the current elements.

Pseudocode

function recursive (list)
    recurise condition
        yield child
    
    for element in remaining-elements:
        // Get the combinations from all elements start from 'element'
        partitions = recursive (...)

        // join the list of elements already explored with the provided combinations
        for every child from partitions:
            yield combination_before   child

The major concept through this is using Depth-First-Search, and maybe figuring out the recursive condition as that really took me a while when.

You can also optimize the code by storing the results of the deep recursive operations in a dictionary and access them when you revisit over in the next iterations. I'm also pretty sure there is some optimal dynamic programming solution for this somewhere out there. Goodluck, hope this helped

Edit: My bad, I realised i had the actual solution before the edit, had no idea that may slighty conflict with individual community guidelines.