Permutationen mit eindeutigen Werten

76

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'))

sortedDies 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.

xyz-123
quelle
Was ist zu groß? Die GESAMT-Permutationen oder die EINZIGARTIGEN Permutationen oder beides?
FogleBird
4
Es gibt eine noch schnellere Lösung als die hier
Gerrat
Sie suchen nach Permutationen von Multisets . Siehe die Antwort von Bill Bell unten.
Joseph Wood
Hast du es versucht for x in permutation() set.add(x)?
NotAnAmbiTurner
Vielleicht wäre ein besserer Titel für diese Frage "unterschiedliche Permutationen". Besser noch, "unterschiedliche Permutationen einer Liste mit Duplikaten".
Don Hatch

Antworten:

58
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 yieldgä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.

Luka Rahne
quelle
3
Ich versuche zu verstehen, wie das funktioniert, aber ich bin ratlos. Könnten Sie bitte einen Kommentar abgeben?
Nathan
@ Nathan Ich habe die Antwort bearbeitet und den Code verfeinert. Fühlen Sie sich frei, zusätzliche Fragen zu stellen, die Sie haben.
Luka Rahne
1
Schöner Code. Sie haben neu implementiert itertools.Counter, richtig?
Eric Duminil
Ich bin nicht mit itertools Counter vertraut. Dieser Code ist eher ein Beispiel und dient zu Bildungszwecken, aufgrund von Leistungsproblemen jedoch weniger für die Produktion. Wenn man eine bessere Lösung benötigt, würde ich eine iterative / nicht rekursive Lösung vorschlagen, die von Narayana Pandita stammt und auch von Donad Knuth in der Kunst der Computerprogrammierung mit möglicher Python-Implementierung unter stackoverflow.com/a/12837695/429982
Luka Rahne,
Ich habe dies mit neu erstellt itertools.Counter, aber es scheint, dass Ihr Code schneller ist :)
Roelant
44

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]]
Bill Bell
quelle
8
Dies ist die einzige Antwort, die explizit angibt, wonach das OP wirklich sucht (dh Permutationen von Multisets ).
Joseph Wood
25

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')
Steven Rumbalski
quelle
funktioniert einwandfrei, aber langsamer als die akzeptierte Lösung. Vielen Dank!
XYZ-123
Dies gilt nicht für neuere Versionen von Python. In Python 3.7.1 wird beispielsweise 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)].
Kirk Strauser
@ KirkStrauser: Du bist richtig. Die Aussage "Jede Permutation einer sortierten Iterable ist in sortierter Reihenfolge" traf nicht einmal auf ältere Versionen von Python zu. Ich habe Python-Versionen bis 2.7 getestet und festgestellt, dass Ihr Ergebnis korrekt ist. Interessanterweise macht es den Algorithmus nicht ungültig. Es werden Permutationen erzeugt, so dass an jedem Punkt nur die maximalen Permutationen original sind.
Steven Rumbalski
@ KirkStrauser: Ich muss es wieder gut machen. Du bist falsch. Ich ging, um meine Antwort zu bearbeiten und genauer zu lesen, was ich schrieb. Meine Aussage hatte ein Qualifikationsmerkmal, das es richtig machte: "Jede Permutation einer sortierten Iterable ist in sortierter Reihenfolge, es sei denn, es handelt sich um Duplikate früherer Permutationen ."
Steven Rumbalski
15

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_permutationsvon (1,2,3,1) durchgehen, um zu sehen, wie es funktioniert:

  • unique_elements sind 1,2,3
  • Lassen Sie uns sie durchgehen: first_elementBeginnt mit 1.
    • remaining_elements sind [2,3,1] (dh 1,2,3,1 minus der ersten 1)
    • Wir iterieren (rekursiv) durch die Permutationen der verbleibenden Elemente: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)
    • Für jedes sub_permutationfügen wir Folgendes ein first_element: ( 1 , 1,2,3), ( 1 , 1,3,2), ... und ergeben das Ergebnis.
  • Jetzt iterieren wir zu first_element= 2 und machen dasselbe wie oben.
    • remaining_elements sind [1,3,1] (dh 1,2,3,1 minus der ersten 2)
    • Wir durchlaufen die Permutationen der verbleibenden Elemente: (1, 1, 3), (1, 3, 1), (3, 1, 1)
    • Für jedes sub_permutationfügen wir Folgendes ein first_element: ( 2 , 1, 1, 3), ( 2 , 1, 3, 1), ( 2 , 3, 1, 1) ... und ergeben das Ergebnis.
  • Schließlich machen wir dasselbe mit first_element= 3.
MiniQuark
quelle
13

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

Paul Rubel
quelle
9
Möglicherweise benötigt er eine Liste (set (itertools.permutations ([1,1,2,2])))
Luka Rahne
2
Oder 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 sie set()trotzdem verwenden. Und @ralu: Schauen Sie sich die Frage noch einmal an, eine anschließende Filterung wäre kostspielig.
JAB
32
set (permutations (somelist))! = permutations (set (somelist))
Luka Rahne
1
Das Problem dabei ist, dass ich die Ausgabe brauche, um die Länge der Eingabe zu haben. ZB list(itertools.permutations([1, 1, 0, 'x']))aber ohne die Duplikate, bei denen die vertauscht sind.
XYZ-123
2
@JAB: hm, das dauert sehr lange für mehr als 12 Werte ... was ich eigentlich will, ist so etwas wie, 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).
XYZ-123
9

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]]
Kleine Roys
quelle
Ich mag diese Lösung
jef
Ich bin froh, dass Ihnen diese Methode gefällt
Little Roys
Hallo @LittleRoys. Ich habe eine leicht modifizierte Version Ihres Codes für eine PR in verwendetmore-itertools . Wäre das für dich in Ordnung?
Jferard
1
Ich bin neugierig, bringt die Klasse einen Mehrwert? Warum ist das nicht nur eine Funktion?
Don Hatch
9

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_permutationsein 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_permutationsist 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 .

Pylang
quelle
Upvoted. list(mit.distinct_permutations([1]*12+[0]*12))Es stellte sich auch heraus, dass es ~ 5,5-mal schneller war als list(multiset_permutations([1]*12+[0]*12))aus der Antwort von @Bill Bell.
Darkonaut
3

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))
Prafi
quelle
2

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)]
Fredrik Pihl
quelle
8
Nein, Kombinationen hätten das gleiche Problem.
JAB
gibt es nur in der Reihenfolge, z. B. würde [1, 2, 3] [1, 2, 3] erzeugen, aber nicht [3, 2, 1] oder [2, 3, 1] usw.
Jk
1

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.

Ashish Datta
quelle
Das , 4sollte 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 es for i in dont_repeat([1]*20+[2]): print i; es wird ewig dauern.
Don Hatch
1

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 s

bmorgan
quelle
1

Sie können eine Funktion erstellen collections.Counter, mit der eindeutige Elemente und ihre Anzahl aus der angegebenen Reihenfolge itertools.combinationsabgerufen 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']
blhsing
quelle
1

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 Dnicht 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

model = smf.ols(string_for_ols, pd_dataframe).fit()
model.summary()
Griff
quelle
0

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')]
CCC
quelle
0

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.

mnmldani
quelle
0

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))
Gregory Morse
quelle
0

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']
David Tam
quelle
-1

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
Andre Manoel
quelle