Все комбинации списка wIthout itertools

Question

Я пытаюсь сделать рекурсивную функцию, которая находит все комбинации списка python.

Я хочу, чтобы ввести [ «A», «B», «C»] в моей функции и, как работает функция Я хочу, чтобы след выглядеть следующим образом:

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

Моя рекурсивная функция выглядит это:

def combo(lst,new_lst = []): 
    for item in lst: 
     new_lst.append([lst[0],item]) 
     print([lst[0],item]) 
    return combo(new_lst,lst[1:]) 

Answer 1

Кажется, что вы хотите, чтобы все продукт из списка, вы можете использовать itertools.product в следующей функции возвращать список генераторов:

>>> from itertools import product 
>>> def pro(li): 
...  return [product(l,repeat=i) for i in range(2,len(l)+1)] 
... 
>>> for i in pro(l): 
...  print list(i) 
... 
[('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'b'), ('b', 'c'), ('c', 'a'), ('c', 'b'), ('c', 'c')] 
[('a', 'a', 'a'), ('a', 'a', 'b'), ('a', 'a', 'c'), ('a', 'b', 'a'), ('a', 'b', 'b'), ('a', 'b', 'c'), ('a', 'c', 'a'), ('a', 'c', 'b'), ('a', 'c', 'c'), ('b', 'a', 'a'), ('b', 'a', 'b'), ('b', 'a', 'c'), ('b', 'b', 'a'), ('b', 'b', 'b'), ('b', 'b', 'c'), ('b', 'c', 'a'), ('b', 'c', 'b'), ('b', 'c', 'c'), ('c', 'a', 'a'), ('c', 'a', 'b'), ('c', 'a', 'c'), ('c', 'b', 'a'), ('c', 'b', 'b'), ('c', 'b', 'c'), ('c', 'c', 'a'), ('c', 'c', 'b'), ('c', 'c', 'c')] 

Answer 2

Правильный ответ: вы должны использовать itertools.combinations. Но если по какой-то причине вы этого не хотите и хотите написать рекурсивную функцию, вы можете использовать следующий фрагмент кода. Это приспособление Erlang способ генерации комбинаций, так что это может показаться немного странным на первый:

def combinations(N, iterable): 
    if not N: 
     return [[]] 
    if not iterable: 
     return [] 

    head = [iterable[0]] 
    tail = iterable[1:] 
    new_comb = [ head + list_ for list_ in combinations(N - 1, tail) ] 

    return new_comb + combinations(N, tail) 

Это очень элегантный способ мышления комбинаций размера N: вы берете первый элемент итератора (головка) и объединить его с меньшими (N-1) комбинациями остальной части итерации (хвост). Затем вы добавляете одинаковые размеры (N) комбинации хвоста. Вот как вы получаете все возможные комбинации.

Если вам нужны все комбинации, все длины вы могли бы сделать:

for n in range(1, len(iterable) + 1): 
    print(combinations(n, iterable))