Комбинации без использования «itertools.combinations»

Question

Мне нужно будет создавать комбинации для двух элементов времени.

Если список содержит: seq = ['A', 'B', 'C'] , выход будет ком = [['A', 'B'], ['A', 'C' ], ['B', 'C']]

все это без метода «itertools.combinations».

Я использовал этот код для перестановок. Но как я могу изменить код, чтобы он работал с комбинациями?

def permute(seq): 

    if len(seq) <= 1: 
     perms = [seq] 
    else: 
     perms = [] 
     for i in range(len(seq)): 
      sub = permute(seq[:i]+seq[i+1:]) 
      for p in sub:  
       perms.append(seq[i:i+1]+p) 

return perms 

Answer 1

Если вы не хотите использовать itertools, а затем использовать documented pure-Python equivalent:

def combinations(iterable, r): 
    # combinations('ABCD', 2) --> AB AC AD BC BD CD 
    # combinations(range(4), 3) --> 012 013 023 123 
    pool = tuple(iterable) 
    n = len(pool) 
    if r > n: 
     return 
    indices = range(r) 
    yield tuple(pool[i] for i in indices) 
    while True: 
     for i in reversed(range(r)): 
      if indices[i] != i + n - r: 
       break 
     else: 
      return 
     indices[i] += 1 
     for j in range(i+1, r): 
      indices[j] = indices[j-1] + 1 
     yield tuple(pool[i] for i in indices) 

Answer 2

Ослабленный перевод рекурсивного кода C++ в answer на аналогичный вопрос:

_NULL = type('_NULL', (object,), {})() # unique sentinel singleton object 

def combinations(sequence, length): 
    """ Find all combinations of the specified length from a sequence. """ 
    if length <= 0: 
     combos = [_NULL] 
    else: 
     combos = [] 
     for i, item in enumerate(sequence, 1): 
      rem_items = sequence[i:] 
      rem_combos = combinations(rem_items, length-1) 
      combos.extend(item if combo is _NULL else [item, combo] 
            for combo in rem_combos) 

    return combos 

print(combinations(['A', 'B', 'C'], 2)) 

Выход:

[['A', 'B'], ['A', 'C'], ['B', 'C']] 

Answer 3

Это тривиально сделать непосредственно:

def comb2(s): 
    for i, v1 in enumerate(s): 
     for j in range(i+1, len(s)): 
      yield [v1, s[j]] 

Тогда:

print list(comb2(['A', 'B', 'C'])) 

дисплеи:

[['A', 'B'], ['A', 'C'], ['B', 'C']] 

Единственное, что делает комбинации вообще сложно это питание для known- only-at-runtime Количество элементов, которые нужно брать за раз. Пока вы знаете это число заранее, фиксированное количество циклов вложенных, что глубоко делает работу очевидным образом.