Combination where order matters -Python-CodePudding

i have this problem, i need to show all possible “subsets” from a text entry , for example:

-entry: ab

(a,b) and (ab)

-entry: abc

(a,b,c) and (ab,c) and (a,bc) and (abc)

-entry: abcd

(a,b,c,d) and (a,bcd) and (abc,d) and (ab,cd) and (ab,c,d) and (a,bc,d) and (a,b,cd) and (abcd)

All my “subsets” need to stay in the same order than my entry with all the elements, i do the math and the amount of subsets are 2^(n-1) with n the amount of letters, also there is no limitation if the person entry the same letter more than once.

I don’t know to start , i’m guessing i need some recursive function, someone told me about backtracking but i dont understand how to implement that

Thanks for reading me

CodePudding user response：

The problem boils down to distributing a number of commas to n-1 possible positions (with n the number of entries in the list). The number of commas can be anything between 1 and n-1, so we need to iterate over that and get all the different combinations for the respective number. This can be done with the routine combinations from the itertools package.

import itertools

mylist = [1, 2, 3, 4]# this is the list from which to draw the subsets

print ([mylist])# the first subsequence of the list is the list itself
# iterating through the possible numbers of commas to be distributed
for n in range(1, len(mylist)):
    comma_positions_comb = list( itertools.combinations(range(1, len(mylist)), n) )
    # iterating through the combinations of comma positions
    for comma_positions in comma_positions_comb:
        subset = []
        start_id = 0
        # iterating through the specific comma positions in the given combination
        for single_comma_position in comma_positions:
            subset.append(mylist[start_id:single_comma_position])
            start_id = single_comma_position
        # the last bit of the list must be appended by hand
        subset.append(mylist[start_id:])
        print (subset)

This gives me the following output:

[[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]]

This should be what you are looking for, judging from the example that you gave. Note that this does not include more nested subsets like [1, [2, [3, [4]]]], corresponding to (a, (b, (c, d))), but it seemed like you don't want to get those out anyway.