permutazioni itertools python con valori legati

Question

Voglio trovare efficientemente permutazioni di un vettore che ha valori legati.

esempio se mi vorrebbe per ottenere come output tutte le combinazioni di [0,0,1,2], [0,0,2,1], [0,1,2,0] e così via, ma non voglio per ottenere [0,0,1,2] due volte che è ciò che la norma itertools.permutations(perm_vector) darebbe.

Ho provato quanto segue ma funziona molto lento quando 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 

La questione è più generale di "speed-up" la natura, in realtà. Il tempo principale è dedicato alla creazione delle permutazioni di lunghi vettori - anche senza la duplicità, la creazione di permutazioni di un vettore di 12 valori unici prende un "infinito". C'è la possibilità di chiamare itertools iterativamente senza accedere ai dati di tutte le permutazioni ma lavorando su molti di essi?

Answer 1

ne dite di questo:

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

Prova questa se perm_vector è piccolo:

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

Questo dovrebbe dare valori univoci, perché ora si trasforma in un set, che di default eliminare duplicazioni.

Se perm_vector è di grandi dimensioni, si potrebbe desiderare di provare backtracking:

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