Как создать все различные комбинации (где элементы ввода повторяются) в Python (используя Itertools)? - PullRequest
Новая
       144

Как создать все различные комбинации (где элементы ввода повторяются) в Python (используя Itertools)?

1 голос
/ 30 апреля 2019

У меня есть набор чисел [1, 2, 4, 1]. Теперь я хочу сгенерировать все возможные комбинации из этого набора размера k (пример k = 3). Все сгенерированные выходные наборы не должны повторяться

Пример: [1, 2, 1] и [2, 1, 1] - это одинаковые наборы, но их не следует выбирать. Только один из них должен появиться. Возможно ли использовать комбинации из itertools в Python? 

import itertools
x = [1, 2, 1]
print([p for p in itertools.product(x, repeat=3)])

Я пытался использовать itertools.product, но он не работает и использование комбинаций из itertools позволяет получить дубликаты

Я пытался использовать itertools.combinsk print([p for p in set(itertools.combinations(x, r=3))])

Если я приведу следующий текст 

  x =  [-1, 0, 1, 2, -1, -4]

Выходной сигнал, сгенерированный для r = 3, равен 

[(0, -1, -4), (-1, -1, -4), (-1, 1, -4), (0, 2, -1), (-1, 0, 2), (-1, 2, -4), (0, 1, 2), (2, -1, -4), (-1, 0, -1), (0, 1, -4), (1, 2, -4), (-1, 0, 1), (-1, 1, 2), (0, 2, -4), (-1, 1, -1), (-1, 2, -1), (1, 2, -1), (0, 1, -1), (-1, 0, -4), (1, -1, -4)]

(-1, 0, 1) и (0, 1, -1) являются дублирующими наборами с одинаковыми комбинациями. Я не уверен, как это преодолеть.

Ответы [ 3 ]

0 голосов
/ 30 апреля 2019

Как насчет получения комбинаций, а затем получения только уникальных, путем ввода словаря с результатом frozenset комбинаций. Это будет использовать только генераторы до создания dictionary. 

combs1, combs2 = itertools.tee(itertools.combinations(x, r=3))
res = list(dict(zip(map(frozenset, combs1), combs2)).values())
0 голосов
/ 30 апреля 2019

Они называются мультимножествами , и мы можем легко получить их комбинации с помощью модуля sympy. 

from sympy.utilities.iterables import multiset_combinations

list(multiset_combinations([1, 2, 4, 1], 3))
[[1, 1, 2], [1, 1, 4], [1, 2, 4]]

А вот пример @EdedkiOkoh: 

x = [-1, 0, 1, 2, -1, -4]
list(multiset_combinations(x, 3))
[[-4, -1, -1],
    [-4, -1, 0],
    [-4, -1, 1],
    [-4, -1, 2],
    [-4, 0, 1],
    [-4, 0, 2],
    [-4, 1, 2],
    [-1, -1, 0],
    [-1, -1, 1],
    [-1, -1, 2],
    [-1, 0, 1],
    [-1, 0, 2],
    [-1, 1, 2],
    [0, 1, 2]]
0 голосов
/ 30 апреля 2019

Вы можете использовать python set datatype , чтобы удалить эти дубликаты, поскольку наборы будут содержать только уникальные комбинации: 

import itertools as it
x = [-1, 0, 1, 2, -1, -4]

permutations = [p for p in set(it.combinations(x, r=3))]
print(permutations)

Выход: 

[(0, 1, 2),
 (-1, 1, -1),
 (-1, 2, -1),
 (0, -1, -4),
 (-1, -1, -4),
 (-1, 1, -4),
 (-1, 2, -4),
 (2, -1, -4),
 (1, 2, -4),
 (-1, 0, 1),
 (1, 2, -1),
 (-1, 0, -4),
 (-1, 0, 2),
 (-1, 0, -1),
 (-1, 1, 2),
 (0, 2, -4),
 (0, 2, -1),
 (0, 1, -4),
 (1, -1, -4),
 (0, 1, -1)]

Тогда можно использовать следующую строку: 

unique_permutations = set(tuple(sorted(t)) for t in permutations)

Выход: 

{(-4, -1, -1),
 (-4, -1, 0),
 (-4, -1, 1),
 (-4, -1, 2),
 (-4, 0, 1),
 (-4, 0, 2),
 (-4, 1, 2),
 (-1, -1, 0),
 (-1, -1, 1),
 (-1, -1, 2),
 (-1, 0, 1),
 (-1, 0, 2),
 (-1, 1, 2),
 (0, 1, 2)}
...