Muszę wygenerować wszystkie "zamówione podzbiory" (przepraszam, jeśli nie używam prawidłowej terminologii matematycznej) sekwencji w Pythonie, z pominiętymi elementami zastąpionymi {x0}}. Biorąc pod uwagę {x1}}, chcę [1, 2], chcę [1, 2], chcę [1, 2] }}. Każdy "zamówiony podzbiór" powinien mieć właściwość, że w każdej pozycji jest dokładnie taki sam element jak w sekwencji nasion, albo jest None.

Mogę dość łatwo generować podzbiory z pominiętymi elementami brakującymi z następującymi:

from itertools import combinations
for length in xrange(len(items), 0, -1):
    for combination in combinations(items, length):
        yield combination

Nie mogę zrozumieć, jaki byłoby najbardziej skuteczny sposób rekonstrukcji brakujących elementów. Moja pierwsza myśl ma zrobić coś takiego:

from itertools import combinations
indexes = range(len(items))
for length in xrange(len(items), 0, -1):
    for combination in combinations(indexes, length):
        yield tuple(items[i] if i in combination else None for i in indexes)

Właśnie zastanawiam się, czy ktoś może zaoferować w tym oczywiste niedociągnięcia, lub jeśli jest bardziej wydajne rozwiązanie, które przegapiłem. (Należy pamiętać, że items będzie dość krótką listą, zazwyczaj poniżej 10 elementów, więc nie martwiam się o o (n) wyszukiwania "kombinacji" w pętli wewnętrznej).

7
dcrosta 18 sierpień 2012, 00:53

3 odpowiedzi

Najlepsza odpowiedź
from itertools import product, repeat
given = [1, 2]
with_nones = zip(given, repeat(None))
print(list(product(*with_nones)))
12
Joel Cornett 18 sierpień 2012, 00:42

Możesz zacząć od pustej liście, dla każdego elementu w nasieniu możesz skopiować wszystkie ostateczne listy i dodać nasiona na końcu.

Na przykład

solutions = []
solutions.append([])
for elem in seed:
    newPartials = []
    for partial in solutions:
        newPartial = partial[:]
        newPartial.append(elem)
        newPartials.append(newPartial)
    solutions.extend(newPartials)

Lub można utworzyć liczbę możliwych rozwiązań, 2^n, gdzie n jest długością listy nasion i stosując modułowe arytmetyczne, usuń elementy, jak:

solutions = []
for i in xrange(2**n):
    solutions.append(seed[:])
seedLen = len(seed)
for i in xrange(2**(n-1)): // % 0 case of following loop
    solutions[i].pop(0)
for elemLoc in xrange(1,seedLen):
    for solutionNum in xrange(2**n):
        if solutionNum % elemLoc = 0:
            solutions[solutionNum].pop(elemLoc)

To rozwiązanie jest zabawnie nieefektywne, włączam głównie, ponieważ jest to interesujący sposób na rozwiązanie problemu.

2
rsegal 17 sierpień 2012, 21:15

Alternatywny - w przypadku, gdy chcesz pokazać, jak głupi, nie możesz używać iTertools:

>>> given=[1,2]
>>> gz=zip(given,[None]*len(given))
>>> [(i,j) for i in gz[0] for j in gz[1]]
[(1, 2), (1, None), (None, 2), (None, None)]
2
the wolf 18 sierpień 2012, 00:45