Search code examples
pythonrecursionpython-itertools

nesting for loop n times to add sublists of a list to itself

suppose i have a list list_ = [['a'],['b'],['c']] and i want to write a program that that add this list with itself by iterating over each element and then writes the results to a main list (here n is (len(list_)-1))

this is what i have written so far

list_ = [['a'],['b'],['c']]
result = []
for i in list_:
    for j in list_:
        x = i+j
        result.append(x)
print(result)

now i suppose if i have a list of 4 sublists for ex list_ = [['a'],['b'],['c'],['d']], i'm doing

list_ = [['a'],['b'],['c'],['d']]
result = []
for i in list_:
    for j in list_:
        for k in list_:
            x = i+j+k
            result.append(x)
print(result)

how do i write a function that follows the same pattern for a list of n sublists using recursion or itertools or something better. i apologize if i was not able to explain the problem properly.

i want to use the above logic to rewrite lines 15-17 for list_ of any number of alphabets

from itertools import chain, combinations, product

def powerset(iterable):
        s = list(iterable)
        pset = []
        for s in list(chain.from_iterable(combinations(s, r) for r in range(len(s)+1))):
             pset.append(list(s))
    
        return pset
    
list_ = ['a','b','c'] 
test_list = powerset(list_)
list_1 = []
list_2 = []
for i in test_list:
    for j in test_list:
        x = i+j
        if len(x)==len(list_):
            if len(x) == len(set(x)):
                list_2.append(i)
                list_2.append(j)
                list_1.append(list_2)
                list_2 = []

print(list_1)

desired output

[
    [[], ['a', 'b', 'c']],
    [['a'], ['b', 'c']],
    [['b'], ['a', 'c']],
    [['c'], ['a', 'b']],
    [['a', 'b'], ['c']],
    [['a', 'c'], ['b']],
    [['b', 'c'], ['a']],
    [['a', 'b', 'c'], []]
]

so in case of four alphabets, the code would look like

list_ = ['a','b','c','d'] 
test_list = powerset(list_)
list_1 = []
list_2 = []
for i in test_list:
    for j in test_list:
        for k in test_list:
            x = i+j+k
            if len(x)==len(list_):
                if len(x) == len(set(x)):
                    list_2.append(i)
                    list_2.append(j)
                    list_2.append(k)
                    list_1.append(list_2)
                    list_2 = []
      

print(list_1)

output

[[[], [], ['a', 'b', 'c', 'd']], [[], ['a'], ['b', 'c', 'd']], [[], ['b'], ['a', 'c', 'd']], [[], ['c'], ['a', 'b', 'd']], [[], ['d'], ['a', 'b', 'c']], [[], ['a', 'b'], ['c', 'd']], [[], ['a', 'c'], ['b', 'd']], [[], ['a', 'd'], ['b', 'c']], [[], ['b', 'c'], ['a', 'd']], [[], ['b', 'd'], ['a', 'c']], [[], ['c', 'd'], ['a', 'b']], [[], ['a', 'b', 'c'], ['d']], [[], ['a', 'b', 'd'], ['c']], [[], ['a', 'c', 'd'], ['b']], [[], ['b', 'c', 'd'], ['a']], [[], ['a', 'b', 'c', 'd'], []], [['a'], [], ['b', 'c', 'd']], [['a'], ['b'], ['c', 'd']], [['a'], ['c'], ['b', 'd']], [['a'], ['d'], ['b', 'c']], [['a'], ['b', 'c'], ['d']], [['a'], ['b', 'd'], ['c']], [['a'], ['c', 'd'], ['b']], [['a'], ['b', 'c', 'd'], []], [['b'], [], ['a', 'c', 'd']], [['b'], ['a'], ['c', 'd']], [['b'], ['c'], ['a', 'd']], [['b'], ['d'], ['a', 'c']], [['b'], ['a', 'c'], ['d']], [['b'], ['a', 'd'], ['c']], [['b'], ['c', 'd'], ['a']], [['b'], ['a', 'c', 'd'], []], [['c'], [], ['a', 'b', 'd']], [['c'], ['a'], ['b', 'd']], [['c'], ['b'], ['a', 'd']], [['c'], ['d'], ['a', 'b']], [['c'], ['a', 'b'], ['d']], [['c'], ['a', 'd'], ['b']], [['c'], ['b', 'd'], ['a']], [['c'], ['a', 'b', 'd'], []], [['d'], [], ['a', 'b', 'c']], [['d'], ['a'], ['b', 'c']], [['d'], ['b'], ['a', 'c']], [['d'], ['c'], ['a', 'b']], [['d'], ['a', 'b'], ['c']], [['d'], ['a', 'c'], ['b']], [['d'], ['b', 'c'], ['a']], [['d'], ['a', 'b', 'c'], []], [['a', 'b'], [], ['c', 'd']], [['a', 'b'], ['c'], ['d']], [['a', 'b'], ['d'], ['c']], [['a', 'b'], ['c', 'd'], []], [['a', 'c'], [], ['b', 'd']], [['a', 'c'], ['b'], ['d']], [['a', 'c'], ['d'], ['b']], [['a', 'c'], ['b', 'd'], []], [['a', 'd'], [], ['b', 'c']], [['a', 'd'], ['b'], ['c']], [['a', 'd'], ['c'], ['b']], [['a', 'd'], ['b', 'c'], []], [['b', 'c'], [], ['a', 'd']], [['b', 'c'], ['a'], ['d']], [['b', 'c'], ['d'], ['a']], [['b', 'c'], ['a', 'd'], []], [['b', 'd'], [], ['a', 'c']], [['b', 'd'], ['a'], ['c']], [['b', 'd'], ['c'], ['a']], [['b', 'd'], ['a', 'c'], []], [['c', 'd'], [], ['a', 'b']], [['c', 'd'], ['a'], ['b']], [['c', 'd'], ['b'], ['a']], [['c', 'd'], ['a', 'b'], []], [['a', 'b', 'c'], [], ['d']], [['a', 'b', 'c'], ['d'], []], [['a', 'b', 'd'], [], ['c']], [['a', 'b', 'd'], ['c'], []], [['a', 'c', 'd'], [], ['b']], [['a', 'c', 'd'], ['b'], []], [['b', 'c', 'd'], [], ['a']], [['b', 'c', 'd'], ['a'], []], [['a', 'b', 'c', 'd'], [], []]]
Solution

  • You can start with recursive function that produces N partitions of a given list. This can be achieved using itertools.combinations by pairing a left and right side formed of combinations of increasing size on the left side and their reciprocal on the right. Recursion would repeat the parting process on the right side for each left side combination:

    def partitions(L,n):
    if n == 1:
        yield [[*L]]
        return
    indexSet = set(range(len(L)))
    for size in range(len(L)+1):
        for iLeft in combinations(range(len(L)),size):
            left  = [L[i] for i in iLeft]
            right = [L[i] for i in indexSet.difference(iLeft)] 
            for rest in partitions(right,n-1):
                yield [left,*rest]

    output:

    print(*partitions(['a','b','c'],2),sep="\n")
[[], ['c', 'b', 'a']]
[['a'], ['c', 'b']]
[['b'], ['c', 'a']]
[['c'], ['b', 'a']]
[['a', 'b'], ['c']]
[['a', 'c'], ['b']]
[['b', 'c'], ['a']]
[['a', 'b', 'c'], []]

    You can then use this generalized partitions function (generator actually), to obtain the length-1 partitions of you list of lists and combine the sublist as you go:

    def partLists(L):
    for parts in partitions(L,len(L)-1):
        yield [ [i for v in p for i in v] for p in parts ]

    output:

    print(*partLists([['a'],['b'],['c'],['d']]),sep="\n")
[[], [], ['a', 'b', 'c', 'd']]
[[], ['a'], ['b', 'c', 'd']]
[[], ['b'], ['a', 'c', 'd']]
[[], ['c'], ['a', 'b', 'd']]
[[], ['d'], ['a', 'b', 'c']]
[[], ['a', 'b'], ['c', 'd']]
[[], ['a', 'c'], ['b', 'd']]
[[], ['a', 'd'], ['b', 'c']]
[[], ['b', 'c'], ['a', 'd']]
[[], ['b', 'd'], ['a', 'c']]
[[], ['c', 'd'], ['a', 'b']]
[[], ['a', 'b', 'c'], ['d']]
[[], ['a', 'b', 'd'], ['c']]
[[], ['a', 'c', 'd'], ['b']]
[[], ['b', 'c', 'd'], ['a']]
[[], ['a', 'b', 'c', 'd'], []]
[['a'], [], ['b', 'c', 'd']]
[['a'], ['b'], ['c', 'd']]
[['a'], ['c'], ['b', 'd']]
[['a'], ['d'], ['b', 'c']]
[['a'], ['b', 'c'], ['d']]
[['a'], ['b', 'd'], ['c']]
[['a'], ['c', 'd'], ['b']]
[['a'], ['b', 'c', 'd'], []]
[['b'], [], ['a', 'c', 'd']]
[['b'], ['a'], ['c', 'd']]
[['b'], ['c'], ['a', 'd']]
[['b'], ['d'], ['a', 'c']]
[['b'], ['a', 'c'], ['d']]
[['b'], ['a', 'd'], ['c']]
[['b'], ['c', 'd'], ['a']]
[['b'], ['a', 'c', 'd'], []]
[['c'], [], ['a', 'b', 'd']]
[['c'], ['a'], ['b', 'd']]
[['c'], ['b'], ['a', 'd']]
[['c'], ['d'], ['a', 'b']]
[['c'], ['a', 'b'], ['d']]
[['c'], ['a', 'd'], ['b']]
[['c'], ['b', 'd'], ['a']]
[['c'], ['a', 'b', 'd'], []]
[['d'], [], ['a', 'b', 'c']]
[['d'], ['a'], ['b', 'c']]
[['d'], ['b'], ['a', 'c']]
[['d'], ['c'], ['a', 'b']]
[['d'], ['a', 'b'], ['c']]
[['d'], ['a', 'c'], ['b']]
[['d'], ['b', 'c'], ['a']]
[['d'], ['a', 'b', 'c'], []]
[['a', 'b'], [], ['c', 'd']]
[['a', 'b'], ['c'], ['d']]
[['a', 'b'], ['d'], ['c']]
[['a', 'b'], ['c', 'd'], []]
[['a', 'c'], [], ['b', 'd']]
[['a', 'c'], ['b'], ['d']]
[['a', 'c'], ['d'], ['b']]
[['a', 'c'], ['b', 'd'], []]
[['a', 'd'], [], ['b', 'c']]
[['a', 'd'], ['b'], ['c']]
[['a', 'd'], ['c'], ['b']]
[['a', 'd'], ['b', 'c'], []]
[['b', 'c'], [], ['a', 'd']]
[['b', 'c'], ['a'], ['d']]
[['b', 'c'], ['d'], ['a']]
[['b', 'c'], ['a', 'd'], []]
[['b', 'd'], [], ['a', 'c']]
[['b', 'd'], ['a'], ['c']]
[['b', 'd'], ['c'], ['a']]
[['b', 'd'], ['a', 'c'], []]
[['c', 'd'], [], ['a', 'b']]
[['c', 'd'], ['a'], ['b']]
[['c', 'd'], ['b'], ['a']]
[['c', 'd'], ['a', 'b'], []]
[['a', 'b', 'c'], [], ['d']]
[['a', 'b', 'c'], ['d'], []]
[['a', 'b', 'd'], [], ['c']]
[['a', 'b', 'd'], ['c'], []]
[['a', 'c', 'd'], [], ['b']]
[['a', 'c', 'd'], ['b'], []]
[['b', 'c', 'd'], [], ['a']]
[['b', 'c', 'd'], ['a'], []]
[['a', 'b', 'c', 'd'], [], []]

    [EDIT] Avoiding duplicates would be better implemented by optimizing the partitions function for it but it can also be done on the resulting partitions using a set (which requires converting them to tuples):

    def partLists(L):
    seen = set()
    for parts in partitions(L,len(L)-1):
        p = [ tuple(sorted(i for v in p for i in v)) for p in parts ]
        p = tuple(sorted(p))
        if p not in seen:
            yield list(map(list,p))
            seen.add(p)

    filtered output:

    print(*partLists([['a'],['b'],['c'],['d']]),sep="\n")
[[], [], ['a', 'b', 'c', 'd']]
[[], ['a'], ['b', 'c', 'd']]
[[], ['a', 'c', 'd'], ['b']]
[[], ['a', 'b', 'd'], ['c']]
[[], ['a', 'b', 'c'], ['d']]
[[], ['a', 'b'], ['c', 'd']]
[[], ['a', 'c'], ['b', 'd']]
[[], ['a', 'd'], ['b', 'c']]
[['a'], ['b'], ['c', 'd']]
[['a'], ['b', 'd'], ['c']]
[['a'], ['b', 'c'], ['d']]
[['a', 'd'], ['b'], ['c']]
[['a', 'c'], ['b'], ['d']]
[['a', 'b'], ['c'], ['d']]