комбинации / перестановки без повторов по группам - PullRequest
Новая
       6

комбинации / перестановки без повторов по группам

2 голосов
/ 05 июля 2010

Я ищу код C или Python для реализации любой из двух функций псевдокода: 

function 1:

list1 = [0,1,2] #any list of single-integer elements
list2 = [0,3,4]
list3 = [0,2,4]

function1(list1, list2, list3)

>>> (0,3,2),(0,3,4),(0,4,2),(1,0,2),(1,0,4),(1,3,0),(1,3,2),(1,3,4),
    (1,4,0),(1,4,2),(2,0,4),(2,3,0),(2,3,4),(2,4,0)

По сути, он генерирует все допустимые перестановки, как определено наличием a) одного элемента из каждого списка и b) отсутствием элементов с одинаковым значением. 

function 2:

list1 = [(0,1),(0,2),(0,3)] #any list of double-integer tuples
list2 = [(0,4),(1,4),(2,4)]

function2(list1, list2)
>>> ((0,1),(2,4)) , ((0,2),(1,4)) , ((0,3),(1,4)) , ((0,3),(2,4))

Функция 2 генерирует любую перестановку, в которой есть один кортеж из каждого списка и нет элементов внутри каждого повторяемого кортежа.

Я посмотрел на справку по Python itertools и не смог найти ничего, что повторяло бы эти псевдофункции. Есть идеи?

Спасибо

Mike

Ответы [ 5 ]

4 голосов
/ 05 июля 2010 
from itertools import product
def function1(*seqs):
  return (x for x in product(*seqs) if len(x) == len(set(x)))

>>> list(function1([0,1,2], [0,3,4], [0,2,4]))
[(0, 3, 2), (0, 3, 4), (0, 4, 2), (1, 0, 2), (1, 0, 4), (1, 3, 0), (1, 3, 2), (1, 3, 4), (1, 4, 0), (1, 4, 2), (2, 0, 4), (2, 3, 0), (2, 3, 4), (2, 4, 0)]
3 голосов
/ 05 июля 2010

Пяр Висландер дал хорошее общее решение для функции1.Вот общее решение для функции2 

from itertools import product
def function2(*args):
    return [i for i in product(*args) if (lambda x: len(x) == len(set(x)))([k for j in i for k in j])]

Конечно, вместо этого вы можете вернуть выражение генератора, если оно лучше подходит вашей цели.
Например: 

def function2(*args):
    return (i for i in product(*args) if (lambda x: len(x) == len(set(x)))([k for j in i for k in j]))
1 голос
/ 05 июля 2010 
def f2(first, second):
    for a in first:
        for b in second:
            if len(set(a + b)) == 4:
                yield (a, b)
1 голос
/ 05 июля 2010 
>>> [(x,y,z) for x in list1 for y in list2 for z in list3 if (x != y and y != z
and x != z)]
[(0, 3, 2), (0, 3, 4), (0, 4, 2), (1, 0, 2), (1, 0, 4), (1, 3, 0), (1, 3, 2), (1
, 3, 4), (1, 4, 0), (1, 4, 2), (2, 0, 4), (2, 3, 0), (2, 3, 4), (2, 4, 0)]

для первого

0 голосов
/ 06 июля 2010

Для всех, кто интересуется, вот заключительная реализация: 

def function2(arg1, arg2):
    return [i for i in product(*arg1) if (lambda x: len(x) == len(set(x)))
            ([k for j in i for k in j] + arg2)]

Два отличия от превосходного решения gnibbler:

1) arg1 теперь является списком, который включает каждый список, который был быв аргументах *.Вместо того, чтобы перечислять каждое из args *, я просто передаю arg1 и распаковываю его в продукте (* arg1).Не уверен, что есть лучший способ сделать это ...

2) arg2 - это список вещей, которые я хочу исключить из любой комбинации.Включение их в параметры для лямбда-функции позволяет мне дополнительно ограничить результаты продукта (* arg1) без введения комбинаций.

С именованными переменными, чтобы показать вам, что я с ним делаю, вот точный код: 

def makeMyMenu(allmeals, dont_eat):
    return [menu for menu in product(*allmeals) if (lambda x: len(x) == len(set(x)))
            ([ingredient for meal in menu for ingredient in meal] + dont_eat)]
...