itertools.permutations generiert, wo seine Elemente basierend auf ihrer Position und nicht aufgrund ihres Werts als eindeutig behandelt werden. Grundsätzlich möchte ich solche Duplikate vermeiden:
>>> list(itertools.permutations([1, 1, 1]))
[(1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1)]
Eine anschließende Filterung ist nicht möglich, da in meinem Fall die Anzahl der Permutationen zu groß ist.
Kennt jemand einen geeigneten Algorithmus dafür?
Vielen Dank!
BEARBEITEN:
Was ich grundsätzlich möchte, ist Folgendes:
x = itertools.product((0, 1, 'x'), repeat=X)
x = sorted(x, key=functools.partial(count_elements, elem='x'))
sorted
Dies ist nicht möglich, da eine Liste erstellt wird und die Ausgabe von itertools.product zu groß ist.
Entschuldigung, ich hätte das eigentliche Problem beschreiben sollen.
python
permutation
itertools
xyz-123
quelle
quelle
for x in permutation() set.add(x)
?Antworten:
class unique_element: def __init__(self,value,occurrences): self.value = value self.occurrences = occurrences def perm_unique(elements): eset=set(elements) listunique = [unique_element(i,elements.count(i)) for i in eset] u=len(elements) return perm_unique_helper(listunique,[0]*u,u-1) def perm_unique_helper(listunique,result_list,d): if d < 0: yield tuple(result_list) else: for i in listunique: if i.occurrences > 0: result_list[d]=i.value i.occurrences-=1 for g in perm_unique_helper(listunique,result_list,d-1): yield g i.occurrences+=1 a = list(perm_unique([1,1,2])) print(a)
Ergebnis:
[(2, 1, 1), (1, 2, 1), (1, 1, 2)]
BEARBEITEN (wie das funktioniert):
Ich habe das obige Programm umgeschrieben, um länger, aber besser lesbar zu sein.
Normalerweise fällt es mir schwer zu erklären, wie etwas funktioniert, aber lassen Sie es mich versuchen. Um zu verstehen, wie dies funktioniert, müssen Sie ein ähnliches, aber einfacheres Programm verstehen, das alle Permutationen mit Wiederholungen liefert.
def permutations_with_replacement(elements,n): return permutations_helper(elements,[0]*n,n-1)#this is generator def permutations_helper(elements,result_list,d): if d<0: yield tuple(result_list) else: for i in elements: result_list[d]=i all_permutations = permutations_helper(elements,result_list,d-1)#this is generator for g in all_permutations: yield g
Dieses Programm ist offensichtlich viel einfacher: d steht für Tiefe in permutations_helper und hat zwei Funktionen. Eine Funktion ist die Stoppbedingung unseres rekursiven Algorithmus und die andere ist die Ergebnisliste, die herumgereicht wird.
Anstatt jedes Ergebnis zurückzugeben, geben wir es zurück. Wenn es keine Funktion / keinen Operator
yield
gäbe, müssten wir das Ergebnis an der Stelle der Stoppbedingung in eine Warteschlange stellen. Auf diese Weise wird das Ergebnis, sobald die Stoppbedingung erfüllt ist, über alle Stapel bis zum Anrufer weitergegeben.for g in perm_unique_helper(listunique,result_list,d-1): yield g
Dies ist der Zweck, damit jedes Ergebnis an den Anrufer weitergegeben wird.Zurück zum ursprünglichen Programm: Wir haben eine Liste einzigartiger Elemente. Bevor wir jedes Element verwenden können, müssen wir überprüfen, wie viele davon noch verfügbar sind, um auf result_list zu pushen. Die Arbeit mit diesem Programm ist sehr ähnlich zu
permutations_with_replacement
. Der Unterschied besteht darin, dass jedes Element nicht öfter wiederholt werden kann als in perm_unique_helper.quelle
itertools.Counter
, richtig?itertools.Counter
, aber es scheint, dass Ihr Code schneller ist :)Da manchmal neue Fragen als Duplikate markiert werden und ihre Autoren auf diese Frage verwiesen werden, kann es wichtig sein zu erwähnen, dass Sympy zu diesem Zweck einen Iterator hat.
>>> from sympy.utilities.iterables import multiset_permutations >>> list(multiset_permutations([1,1,1])) [[1, 1, 1]] >>> list(multiset_permutations([1,1,2])) [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
quelle
Dies beruht auf dem Implementierungsdetail, dass jede Permutation einer sortierten Iterable in sortierter Reihenfolge erfolgt, es sei denn, es handelt sich um Duplikate früherer Permutationen.
from itertools import permutations def unique_permutations(iterable, r=None): previous = tuple() for p in permutations(sorted(iterable), r): if p > previous: previous = p yield p for p in unique_permutations('cabcab', 2): print p
gibt
('a', 'a') ('a', 'b') ('a', 'c') ('b', 'a') ('b', 'b') ('b', 'c') ('c', 'a') ('c', 'b') ('c', 'c')
quelle
list(itertools.permutations([1,2,2], 3))
zurückgegeben[(1, 2, 2), (1, 2, 2), (2, 1, 2), (2, 2, 1), (2, 1, 2), (2, 2, 1)]
.Etwa so schnell wie Luka Rahnes Antwort, aber meiner Meinung nach kürzer und einfacher.
def unique_permutations(elements): if len(elements) == 1: yield (elements[0],) else: unique_elements = set(elements) for first_element in unique_elements: remaining_elements = list(elements) remaining_elements.remove(first_element) for sub_permutation in unique_permutations(remaining_elements): yield (first_element,) + sub_permutation >>> list(unique_permutations((1,2,3,1))) [(1, 1, 2, 3), (1, 1, 3, 2), (1, 2, 1, 3), ... , (3, 1, 2, 1), (3, 2, 1, 1)]
Es funktioniert rekursiv, indem das erste Element festgelegt wird (alle eindeutigen Elemente durchlaufen) und die Permutationen für alle verbleibenden Elemente durchlaufen werden.
Lassen Sie uns das
unique_permutations
von (1,2,3,1) durchgehen, um zu sehen, wie es funktioniert:unique_elements
sind 1,2,3first_element
Beginnt mit 1.remaining_elements
sind [2,3,1] (dh 1,2,3,1 minus der ersten 1)sub_permutation
fügen wir Folgendes einfirst_element
: ( 1 , 1,2,3), ( 1 , 1,3,2), ... und ergeben das Ergebnis.first_element
= 2 und machen dasselbe wie oben.remaining_elements
sind [1,3,1] (dh 1,2,3,1 minus der ersten 2)sub_permutation
fügen wir Folgendes einfirst_element
: ( 2 , 1, 1, 3), ( 2 , 1, 3, 1), ( 2 , 3, 1, 1) ... und ergeben das Ergebnis.first_element
= 3.quelle
Sie könnten versuchen, set zu verwenden:
>>> list(itertools.permutations(set([1,1,2,2]))) [(1, 2), (2, 1)]
Der Aufruf zum Entfernen entfernter Duplikate
quelle
list(itertools.permutations({1,1,2,2}))
in Python 3+ oder Python 2.7, da festgelegte Literale vorhanden sind. Wenn er keine wörtlichen Werte verwendet, würde er sieset()
trotzdem verwenden. Und @ralu: Schauen Sie sich die Frage noch einmal an, eine anschließende Filterung wäre kostspielig.list(itertools.permutations([1, 1, 0, 'x']))
aber ohne die Duplikate, bei denen die vertauscht sind.itertools.product((0, 1, 'x'), repeat=X)
aber ich muss Werte mit wenigen x zuerst verarbeiten (sortiert ist nicht geeignet, weil es eine Liste generiert und auch verwendet viel Gedächtnis).Dies ist meine Lösung mit 10 Zeilen:
class Solution(object): def permute_unique(self, nums): perms = [[]] for n in nums: new_perm = [] for perm in perms: for i in range(len(perm) + 1): new_perm.append(perm[:i] + [n] + perm[i:]) # handle duplication if i < len(perm) and perm[i] == n: break perms = new_perm return perms if __name__ == '__main__': s = Solution() print s.permute_unique([1, 1, 1]) print s.permute_unique([1, 2, 1]) print s.permute_unique([1, 2, 3])
--- Ergebnis ----
[[1, 1, 1]] [[1, 2, 1], [2, 1, 1], [1, 1, 2]] [[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]
quelle
more-itertools
. Wäre das für dich in Ordnung?Ein naiver Ansatz könnte darin bestehen, die Menge der Permutationen zu übernehmen:
list(set(it.permutations([1, 1, 1]))) # [(1, 1, 1)]
Diese Technik berechnet jedoch Replikationspermutationen verschwenderisch und verwirft sie. Ein effizienterer Ansatz wäre
more_itertools.distinct_permutations
ein Tool von Drittanbietern .Code
import itertools as it import more_itertools as mit list(mit.distinct_permutations([1, 1, 1])) # [(1, 1, 1)]
Performance
Mit einem größeren Iterable werden wir die Leistungen zwischen naiven Techniken und Techniken von Drittanbietern vergleichen.
iterable = [1, 1, 1, 1, 1, 1] len(list(it.permutations(iterable))) # 720 %timeit -n 10000 list(set(it.permutations(iterable))) # 10000 loops, best of 3: 111 µs per loop %timeit -n 10000 list(mit.distinct_permutations(iterable)) # 10000 loops, best of 3: 16.7 µs per loop
Wir sehen,
more_itertools.distinct_permutations
ist eine Größenordnung schneller.Einzelheiten
Aus der Quelle wird ein Rekursionsalgorithmus (wie in der akzeptierten Antwort zu sehen) verwendet, um unterschiedliche Permutationen zu berechnen, wodurch verschwenderische Berechnungen vermieden werden. Weitere Informationen finden Sie im Quellcode .
quelle
list(mit.distinct_permutations([1]*12+[0]*12))
Es stellte sich auch heraus, dass es ~ 5,5-mal schneller war alslist(multiset_permutations([1]*12+[0]*12))
aus der Antwort von @Bill Bell.Hier ist eine rekursive Lösung für das Problem.
def permutation(num_array): res=[] if len(num_array) <= 1: return [num_array] for num in set(num_array): temp_array = num_array.copy() temp_array.remove(num) res += [[num] + perm for perm in permutation(temp_array)] return res arr=[1,2,2] print(permutation(arr))
quelle
Es hört sich so an, als würden Sie nach itertools.combinations () docs.python.org suchen
list(itertools.combinations([1, 1, 1],3)) [(1, 1, 1)]
quelle
Ich bin auf diese Frage gestoßen, als ich selbst nach etwas gesucht habe!
Folgendes habe ich getan:
def dont_repeat(x=[0,1,1,2]): # Pass a list from itertools import permutations as per uniq_set = set() for byt_grp in per(x, 4): if byt_grp not in uniq_set: yield byt_grp uniq_set.update([byt_grp]) print uniq_set for i in dont_repeat(): print i (0, 1, 1, 2) (0, 1, 2, 1) (0, 2, 1, 1) (1, 0, 1, 2) (1, 0, 2, 1) (1, 1, 0, 2) (1, 1, 2, 0) (1, 2, 0, 1) (1, 2, 1, 0) (2, 0, 1, 1) (2, 1, 0, 1) (2, 1, 1, 0) set([(0, 1, 1, 2), (1, 0, 1, 2), (2, 1, 0, 1), (1, 2, 0, 1), (0, 1, 2, 1), (0, 2, 1, 1), (1, 1, 2, 0), (1, 2, 1, 0), (2, 1, 1, 0), (1, 0, 2, 1), (2, 0, 1, 1), (1, 1, 0, 2)])
Machen Sie im Grunde ein Set und fügen Sie es weiter hinzu. Besser als Listen usw. zu erstellen, die zu viel Speicherplatz beanspruchen. Ich hoffe, es hilft der nächsten Person, die nach draußen schaut :-) Kommentieren Sie das eingestellte 'Update' in der Funktion aus, um den Unterschied zu erkennen.
quelle
, 4
sollte entfernt werden, damit es bei Dingen beliebiger Länge funktioniert. Selbst wenn dies behoben ist, ist dies keine großartige Lösung. Zum einen werden alle Elemente gleichzeitig im Speicher gespeichert, wodurch einige der Vorteile eines Generators zunichte gemacht werden. Zum anderen ist es in Bezug auf die Zeit immer noch sehr ineffizient, in einigen Fällen sollte es sofort geschehen. Versuchen Sie esfor i in dont_repeat([1]*20+[2]): print i
; es wird ewig dauern.Die beste Lösung für dieses Problem, die ich gesehen habe, ist Knuths "Algorithmus L" (wie zuvor von Gerrat in den Kommentaren zum ursprünglichen Beitrag erwähnt):
http://stackoverflow.com/questions/12836385/how-can-i-interleave- oder-erstellen-eindeutige-Permutationen-von-zwei-Stichen-ohne-Wiederholungen / 12837695
Einige Timings:
Sortierung
[1]*12+[0]*12
(2.704.156 eindeutige Permutationen):Algorithmus L → 2,43 s
Lösung von Luke Rahne → 8,56 s
scipy.multiset_permutations()
→ 16,8 squelle
Sie können eine Funktion erstellen
collections.Counter
, mit der eindeutige Elemente und ihre Anzahl aus der angegebenen Reihenfolgeitertools.combinations
abgerufen und Kombinationen von Indizes für jedes eindeutige Element in jedem rekursiven Aufruf ausgewählt und die Indizes wieder einer Liste zugeordnet werden, wenn alle Indizes ausgewählt sind:from collections import Counter from itertools import combinations def unique_permutations(seq): def index_permutations(counts, index_pool): if not counts: yield {} return (item, count), *rest = counts.items() rest = dict(rest) for indices in combinations(index_pool, count): mapping = dict.fromkeys(indices, item) for others in index_permutations(rest, index_pool.difference(indices)): yield {**mapping, **others} indices = set(range(len(seq))) for mapping in index_permutations(Counter(seq), indices): yield [mapping[i] for i in indices]
so dass
[''.join(i) for i in unique_permutations('moon')]
zurückkehrt:['moon', 'mono', 'mnoo', 'omon', 'omno', 'nmoo', 'oomn', 'onmo', 'nomo', 'oonm', 'onom', 'noom']
quelle
Um eindeutige Permutationen von zu generieren, verwende
["A","B","C","D"]
ich Folgendes:from itertools import combinations,chain l = ["A","B","C","D"] combs = (combinations(l, r) for r in range(1, len(l) + 1)) list_combinations = list(chain.from_iterable(combs))
Was erzeugt:
[('A',), ('B',), ('C',), ('D',), ('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D'), ('A', 'B', 'C'), ('A', 'B', 'D'), ('A', 'C', 'D'), ('B', 'C', 'D'), ('A', 'B', 'C', 'D')]
Beachten Sie, dass keine Duplikate erstellt werden (z. B. werden Elemente in Kombination mit
D
nicht generiert, da sie bereits vorhanden sind).Beispiel: Dies kann dann verwendet werden, um Begriffe höherer oder niedrigerer Ordnung für OLS-Modelle über Daten in einem Pandas-Datenrahmen zu generieren.
import statsmodels.formula.api as smf import pandas as pd # create some data pd_dataframe = pd.Dataframe(somedata) response_column = "Y" # generate combinations of column/variable names l = [col for col in pd_dataframe.columns if col!=response_column] combs = (combinations(l, r) for r in range(1, len(l) + 1)) list_combinations = list(chain.from_iterable(combs)) # generate OLS input string formula_base = '{} ~ '.format(response_column) list_for_ols = [":".join(list(item)) for item in list_combinations] string_for_ols = formula_base + ' + '.join(list_for_ols)
Erstellt ...
Y ~ A + B + C + D + A:B + A:C + A:D + B:C + B:D + C:D + A:B:C + A:B:D + A:C:D + B:C:D + A:B:C:D'
Was dann zu Ihrer OLS-Regression geleitet werden kann
quelle
Kam neulich darüber hinweg, als ich an einem eigenen Problem arbeitete. Ich mag den Ansatz von Luka Rahne, aber ich dachte, dass die Verwendung der Counter-Klasse in der Sammlungsbibliothek eine bescheidene Verbesserung darstellt. Hier ist mein Code:
def unique_permutations(elements): "Returns a list of lists; each sublist is a unique permutations of elements." ctr = collections.Counter(elements) # Base case with one element: just return the element if len(ctr.keys())==1 and ctr[ctr.keys()[0]] == 1: return [[ctr.keys()[0]]] perms = [] # For each counter key, find the unique permutations of the set with # one member of that key removed, and append the key to the front of # each of those permutations. for k in ctr.keys(): ctr_k = ctr.copy() ctr_k[k] -= 1 if ctr_k[k]==0: ctr_k.pop(k) perms_k = [[k] + p for p in unique_permutations(ctr_k)] perms.extend(perms_k) return perms
Dieser Code gibt jede Permutation als Liste zurück. Wenn Sie eine Zeichenfolge eingeben, erhalten Sie eine Liste mit Permutationen, wobei jede eine Liste mit Zeichen ist. Wenn Sie die Ausgabe stattdessen als Liste von Zeichenfolgen verwenden möchten (z. B. wenn Sie eine schreckliche Person sind und meinen Code missbrauchen möchten, um beim Betrügen in Scrabble zu helfen), gehen Sie einfach wie folgt vor:
[''.join(perm) for perm in unique_permutations('abunchofletters')]
quelle
In diesem Fall habe ich mit itertools.product eine sehr geeignete Implementierung gefunden (dies ist eine Implementierung, bei der Sie alle Kombinationen wünschen
unique_perm_list = [''.join(p) for p in itertools.product(['0', '1'], repeat = X) if ''.join(p).count() == somenumber]
Dies ist im Wesentlichen eine Kombination (n über k) mit n = X und somenumber = k itertools.product () iteriert von k = 0 nach k = X. Durch anschließendes Filtern mit count wird sichergestellt, dass nur die Permutationen mit der richtigen Anzahl von Einsen eingegossen werden eine Liste. Sie können leicht sehen, dass es funktioniert, wenn Sie n über k berechnen und es mit der len (unique_perm_list) vergleichen.
quelle
Angepasst, um Rekursion zu entfernen, verwenden Sie ein Wörterbuch und numba für eine hohe Leistung, verwenden Sie jedoch nicht den Ertrags- / Generatorstil, damit die Speichernutzung nicht beschränkt ist:
import numba @numba.njit def perm_unique_fast(elements): #memory usage too high for large permutations eset = set(elements) dictunique = dict() for i in eset: dictunique[i] = elements.count(i) result_list = numba.typed.List() u = len(elements) for _ in range(u): result_list.append(0) s = numba.typed.List() results = numba.typed.List() d = u while True: if d > 0: for i in dictunique: if dictunique[i] > 0: s.append((i, d - 1)) i, d = s.pop() if d == -1: dictunique[i] += 1 if len(s) == 0: break continue result_list[d] = i if d == 0: results.append(result_list[:]) dictunique[i] -= 1 s.append((i, -1)) return results
import timeit l = [2, 2, 3, 3, 4, 4, 5, 5, 6, 6] %timeit list(perm_unique(l)) #377 ms ± 26 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) ltyp = numba.typed.List() for x in l: ltyp.append(x) %timeit perm_unique_fast(ltyp) #293 ms ± 3.37 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) assert list(sorted(perm_unique(l))) == list(sorted([tuple(x) for x in perm_unique_fast(ltyp)]))
Etwa 30% schneller, leidet aber immer noch ein bisschen unter dem Kopieren und Verwalten von Listen.
Alternativ ohne numba, aber immer noch ohne Rekursion und mit einem Generator, um Speicherprobleme zu vermeiden:
def perm_unique_fast_gen(elements): eset = set(elements) dictunique = dict() for i in eset: dictunique[i] = elements.count(i) result_list = list() #numba.typed.List() u = len(elements) for _ in range(u): result_list.append(0) s = list() d = u while True: if d > 0: for i in dictunique: if dictunique[i] > 0: s.append((i, d - 1)) i, d = s.pop() if d == -1: dictunique[i] += 1 if len(s) == 0: break continue result_list[d] = i if d == 0: yield result_list dictunique[i] -= 1 s.append((i, -1))
quelle
Dies ist mein Versuch, ohne auf set / dict zurückzugreifen, als Generator mit Rekursion, aber mit String als Eingabe. Die Ausgabe erfolgt ebenfalls in natürlicher Reihenfolge:
def perm_helper(head: str, tail: str): if len(tail) == 0: yield head else: last_c = None for index, c in enumerate(tail): if last_c != c: last_c = c yield from perm_helper( head + c, tail[:index] + tail[index + 1:] ) def perm_generator(word): yield from perm_helper("", sorted(word))
Beispiel:
from itertools import takewhile word = "POOL" list(takewhile(lambda w: w != word, (x for x in perm_generator(word)))) # output # ['LOOP', 'LOPO', 'LPOO', 'OLOP', 'OLPO', 'OOLP', 'OOPL', 'OPLO', 'OPOL', 'PLOO', 'POLO']
quelle
Wie wäre es mit
np.unique(itertools.permutations([1, 1, 1]))
Das Problem ist, dass die Permutationen jetzt Zeilen eines Numpy-Arrays sind und somit mehr Speicher belegen. Sie können sie jedoch wie zuvor durchlaufen
perms = np.unique(itertools.permutations([1, 1, 1])) for p in perms: print p
quelle
ans=[] def fn(a, size): if (size == 1): if a.copy() not in ans: ans.append(a.copy()) return for i in range(size): fn(a,size-1); if size&1: a[0], a[size-1] = a[size-1],a[0] else: a[i], a[size-1] = a[size-1],a[i]
https://www.geeksforgeeks.org/heaps-algorithm-for-generating-permutations/
quelle