具有绑定(bind)值的 python itertools 排列

Question

我想有效地找到具有绑定(bind)值的向量的排列。

例如，如果 perm_vector = [0,0,1,2] 我想获得 [0,0,1,2]、[0, 0,2,1], [0,1,2,0] 等等，但我不想两次获得 [0,0,1,2]是标准的 itertools.permutations(perm_vector) 会给出的。

我尝试了以下方法，但当 perm_vector 在 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

实际上，这个问题具有更普遍的“加速”性质。主要时间花在创建长向量的排列上——即使没有口是心非，创建 12 个唯一值的向量排列也需要“无穷大”。是否可以迭代调用 itertools 而无需访问整个排列数据，而是处理其中的一串数据？

Answer 1

如果 perm_vector 很小，试试这个:

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

这应该给你唯一的值，因为现在它变成了一个集合，默认情况下会删除重复项。

如果 perm_vector 很大，您可能想尝试回溯:

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