Python Itertools Permutationen mit gebundenen Werte

Question

Ich möchte effizient finden Permutationen eines Vektors, der Werte gebunden hat.

Z. B. wenn Ich würde alle Kombinationen von [0,0,1,2], [0,0,2,1], [0,1,2,0] als Ausgabe erhalten mag, und so weiter, aber ich will nicht [0,0,1,2] zweimal erhalten, das ist es, was die Standard-itertools.permutations(perm_vector) geben würde.

habe ich versucht, die folgenden aber es funktioniert wirklich langsam, wenn perm_vector grows in len:

vectors_list = [] 
for it in itertools.permutations(perm_vector): 
    vectors_list.append(list(it)) 
df_vectors_list = pd.DataFrame(vectors_list) 
df_gb = df_vectors_list.groupby(list(df_vectors_list.columns)) 
vectors_list = pd.DataFrame(df_gb.groups.keys()).T 

Die Frage der allgemeineren "Speed-up" Natur ist, eigentlich. Die Hauptzeit wird verwendet, um die Permutationen von langen Vektoren zu erzeugen - auch ohne die Duplizität nimmt die Erzeugung von Permutationen eines Vektors von 12 einzigartigen Werten eine "Unendlichkeit" an. Gibt es eine Möglichkeit, die itertools iterativ aufzurufen, ohne auf die gesamten Permutationsdaten zuzugreifen, sondern daran zu arbeiten?

Answer 1

Wie wäre es damit:

from collections import Counter 

def starter(l): 
    cnt = Counter(l) 
    res = [None] * len(l) 
    return worker(cnt, res, len(l) - 1) 

def worker(cnt, res, n): 
    if n < 0: 
     yield tuple(res) 
    else: 
     for k in cnt.keys(): 
      if cnt[k] != 0: 
       cnt[k] = cnt[k] - 1 
       res[n] = k 
       for r in worker(cnt, res, n - 1): 
        yield r 
       cnt[k] = cnt[k] + 1 

Answer 2

dies versuchen, wenn perm_vector klein ist:

import itertools as iter 
{x for x in iter.permutations(perm_vector)} 

Dies sollten Sie eindeutige Werte geben, denn jetzt ist es eine Reihe wird, die standardmäßig Vervielfältigungen löschen.

Wenn perm_vector groß ist, könnten Sie Rückzieher versuchen:

def permu(L, left, right, cache): 
    for i in range(left, right): 
     L[left], L[i] = L[i], L[left] 
     L_tuple = tuple(L) 
     if L_tuple not in cache:     
      permu(L, left + 1, right, cache) 
      L[left], L[i] = L[i], L[left] 
      cache[L_tuple] = 0 
cache = {} 
permu(perm_vector, 0, len(perm_vector), cache) 
cache.keys()