Есть ли алгоритм для поиска уникальных комбинаций из 2 списков? 5 списков?

Возможно, вы ищете itertools.product:

 #!/usr/bin/env python import itertools a=[1,2] b=['a','b'] c=[str(s)+str(t) for s,t in itertools.product(a,b)] print(c) ['1a', '1b', '2a', '2b'] v=[1,'a'] w=[1,'b'] x=[1,'c'] y=[1,'d'] z=[1,'e'] r=[''.join([str(elt) for elt in p]) for p in itertools.product(v,w,x,y,z)] print(r) # ['11111', '1111e', '111d1', '111de', '11c11', '11c1e', '11cd1', '11cde', '1b111', '1b11e', '1b1d1', '1b1de', '1bc11', '1bc1e', '1bcd1', '1bcde', 'a1111', 'a111e', 'a11d1', 'a11de', 'a1c11', 'a1c1e', 'a1cd1', 'a1cde', 'ab111', 'ab11e', 'ab1d1', 'ab1de', 'abc11', 'abc1e', 'abcd1', 'abcde'] 

Обратите внимание, что продукт дает 2 ** 5 элементов. Это то, что вы хотите?

Продукт itertools.product находится в Python 2.6. Для предыдущих версий вы можете использовать это:

 def product(*args, **kwds): ''' Source: http://docs.python.org/library/itertools.html#itertools.product ''' # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111 pools = map(tuple, args) * kwds.get('repeat', 1) result = [[]] for pool in pools: result = [x+[y] for x in result for y in pool] for prod in result: yield tuple(prod) 

Редактировать: Как указывает Джеллибо, исходный вопрос задает уникальные наборы. Вышеприведенный код не будет создавать уникальные множества, если a , b , v , w , x , y или z содержат повторяющиеся элементы. Если это проблема для вас, вы можете конвертировать каждый список в набор перед отправкой его на itertools.product:

 r=[''.join([str(elt) for elt in p]) for p in itertools.product(*(set(elt) for elt in (v,w,x,y,z)))] 

Я думаю, еще один ответ, чтобы ответить на это:

Я написал это на своей доске, и все это похоже на образец, я его еще не нашел.

Есть образец.

Предположим, у вас есть только два списка для объединения. Вы можете найти все комбинации, создав сетку.

  black blue +------------+------------+ coat | black coat | blue coat | +------------+------------+ hat | black hat | blue hat | +------------+------------+ 

Как вы можете видеть, есть 2 * 2 комбинации. Если бы было 30 цветов и 14 видов одежды, у вас было бы 30 * 14 = 420 комбинаций.

Шаблон продолжается по мере добавления дополнительных списков. Вместо двумерного прямоугольника вы получаете трехмерный массив ящиков или, в конечном счете, n- мерный гиперрейтинг. Несмотря на это, общее количество комбинаций всегда является результатом длин всех списков.

Если вы знаете, сколько у вас списков, вложенные циклы – естественный способ сделать все комбинации.

 for color in colors: for kind in kinds: print color, kind # "black coat", "black hat", etc. 

Если списки начинаются с начала словаря, а дубликатов нет, вывод также будет в порядке словаря.

Я не думаю, что вопрос задает полномочия на входные данные, я думаю, что он запрашивает (часть) декартово произведение входных множеств. Я ожидаю, что кто-то исправит меня, если я ошибаюсь.

И, что касается алгоритма, теперь, когда вы знаете, что именно вы ищете, Google станет вашим другом.

Во втором примере вы исключаете записи, такие как 1b1de из вашего результирующего набора. Это преднамеренно? Если это преднамеренно, каково правило, с помощью которого создается выход?

Я предполагаю, что вы хотите, чтобы декартово произведение – все возможные списки, созданные путем выбора только одного элемента из каждого списка. Вы можете реализовать его рекурсивно, например:

 def cartesian_product(l): if l: for b in cartesian_product(l[1:]): for a in l[0]: yield [a] + b else: yield [] l = [ [ 'a', 'b' ], [ 'c', 'd', 'e' ], [ 'f', 'g' ], ] for x in cartesian_product(l): print x 

Обновление: ~ предложение unutbu itertools.product лучше, но я все равно оставлю это здесь.

Так как вам нужен декартовой продукт , используйте его !

 >>> import itertools >>> v = [1, 'a'] >>> w = [1, 'b'] >>> x = [1, 'c'] >>> y = [1, 'd'] >>> z = [1, 'e'] >>> p = [''.join(str(x) for x in c) for c in itertools.product(v,w,x,y,z)] >>> p ['11111', '1111e', '111d1', '111de', '11c11', '11c1e', '11cd1', '11cde', '1b111' , '1b11e', '1b1d1', '1b1de', '1bc11', '1bc1e', '1bcd1', '1bcde', 'a1111', 'a111e ', 'a11d1', 'a11de', 'a1c11', 'a1c1e', 'a1cd1', 'a1cde', 'ab111', 'ab11e', 'ab1d 1', 'ab1de', 'abc11', 'abc1e', 'abcd1', 'abcde'] >>> 

Может, это трюк?

 def getAllCombinations(listOfLists): if len(listOfLists) == 1: return [str(x) for x in listOfLists[0]] result = set() head, tail = listOfLists[0], listOfLists[1:] tailCombs = getAllCombinations(tail) for elem in head: for tc in tailCombs: result.add(str(elem) + tc) return result v = [1, 'a'] w = [1, 'b'] x = [1, 'c'] y = [1, 'd'] z = [1, 'e'] >>> print getAllCombinations([v, w, x, y, z]) set(['111de', 'abc11', 'a1c1e', 'a111e', '11c11', 'ab11e', '1bc11', 'ab1d1', 'a1cd1', '1b1de', 'a11d1', '11111', '1b111', '11cd1', 'abcd1', '1bcde', 'ab111', '1bc1e', 'abc1e', '111d1', 'a1111', '11c1e', 'a1c11', '11cde', '1b11e', '1bcd1', 'abcde', 'a1cde', '1b1d1', 'a11de', 'ab1de', '1111e']) 

Вы ищете декартово произведение. В Python, если вы хотите кортежи:

 c = [(x, y) for x in a for y in b] r = [(vv, ww, xx, yy, zz) for vv in v for ww in w for xx in x for yy in y for zz in z]