python 中的排列过多

Question

我的程序需要在列表列表中包含 2 和 0 的所有组合。例如：[[0,0,0,2],[0,0,2,0],[0,2,0,0].....]。我将在每个子列表中始终有 n^2 个元素，其中有 n-1 次 2s。所以我应该有 n^2!/((n^2-n)!*(n-1)!) 结果。

问题是我的代码首先计算所有排列，然后删除重复项。所以对于 n = 4 会有 16！子列表，这让我的电脑崩溃了。我怎样才能解决这个问题？（它至少需要处理 n = 8）

代码如下：

servers = n*n   #number of elements in each sublist
infected = n - 1 #number of 2s
grid = [ 0 for a in range(servers)] #list representing grid, with all 0s
grid = grid[:-infected] + infected * [2] #make last ones 2s

all_infections = list(itertools.permutations(grid))  # !!PROBLEM!! create all permutations of infection (touple)
all_infections = [list(a) for a in all_infections]   # Convert touple to lists


all_infections.sort()
all_infections = list(k for k,_ in itertools.groupby(all_infections)) #remove duplicates

combinations = len(all_infections)
print (all_infections)

results = []

for index in range(combinations): #calculate the infected states
    results = results + [grid_infecter(all_infections[index],n)]

Answer 1

你的主要问题是组合爆炸远远超出了实际问题的要求。如您所说，n=8 的情况只需要 64!/(57!7!) 个结果。为什么要一次存储它们？

剩下两个基本选择：

编写您自己的排列例程。这些很容易通过基本搜索找到，例如 this one.
从 permutations() 构建一个生成器流，并在重复项进入您的列表之前消除它们。

像这样：

def no_duplicate(gen):
   previous = set()
   for permutation in gen:
      if permutation not in previous:
         previous.add(permutation)
         yield permutation

# Now set up a generator pipeline for the permutations
infection_stream = (no_duplicate(itertools.permutations(grid)))
result_stream = (grid_infecter(dish) for dish in infection_stream)

result_stream 是一个生成器，您可以将其用于您想要的任何目的，例如：

results = [_ for _ in result_stream]

生成器的神奇之处在于，到目前为止，我们在任何时候都只有一个活跃的排列。唯一的存储在 no_duplicates 中的 "previous" 集合中，但这是您唯一有潜在 space 问题的地方。如果这超出了您计算机的内存或您的耐心（毕竟算法是 O(n^2 ！)，那么您将需要编写自己的排列生成器，这样您就可以一次处理一个，而无需长期 "remembering" 设备。

python 中的排列过多

Too many permutations in python

python

algorithm

permutation