Python中唯一不可逆排列的优化

Question

我目前正在尝试解决Python 3中的'dance recital'kattis挑战] >> [See here

在输入了舞蹈独奏会的演出之后，您必须以最小化舞者连续演出的方式安排演出。

我已经看到了用C ++完成的挑战，但是我的代码一直用不完，我想对其进行优化。

问题：

截至目前，我生成了所有可能的性能排列并对其进行比较。一种更快的方法是不生成所有排列，因为其中一些只是简单地颠倒了，并会产生完全相同的输出。

import itertools
print(list(itertools.permutations(range(2)))) --> [(0,1),(1,0)] #They're the same, backwards and forwards
print(magic_algorithm(range(2))) --> [(0,1)] #This is what I want
我如何生成这样的排列列表？

我已经尝试过：

-生成所有排列，再次对其进行遍历以得到reversed（）重复项并保存它们。这会花费太长时间，并且由于文件太大，结果无法硬编码到解决方案中。

-仅生成直到中途标记的排列，然后停止，假设之后没有生成唯一的排列（我发现不是真的）

-我在这里签出了问题，但似乎没有人和我有同样的问题，网上也有同上

---

这是我当前的代码：

from itertools import permutations

number_of_routines = int(input()) #first line is number of routines
dance_routine_list = [0]*10
permutation_list = list(permutations(range(number_of_routines))) #generate permutations

for q in range(number_of_routines):
    s = input()
    for c in s:
        v = ord(c) - 65
        dance_routine_list[q] |= (1 << v) #each routine ex.'ABC' is A-Z where each char represents a performer in the routine

def calculate():
    least_changes_possible = 1e9 #this will become smaller, as optimizations are found
    for j in permutation_list:
        tmp = 0
        for i in range(1,number_of_routines):
            tmp += (bin(dance_routine_list[j[i]] & dance_routine_list[j[i - 1]]).count('1')) #each 1 represents a performer who must complete sequential routines
        least_changes_possible = min(least_changes_possible, tmp)
    return least_changes_possible

print(calculate())
编辑：

进行了一次淋浴，并决定添加查找表将加快速度，因为许多操作都在重复。仍然不能解决整个排列的迭代问题，但应该会有所帮助。

我目前正在尝试解决Python 3中的'dance recital'kattis挑战。

[最多有10种可能的舞蹈例程，因此最多有3.6M个排列，甚至坏的算法（如全部生成它们并进行测试也将很快完成。

如果您想为多达24个左右的例程提供快速解决方案，那么我会这样做...

鉴于R舞蹈例程，在独奏会中的任何位置，为了决定下一步可以执行的例程，您需要了解：

您已经执行过哪些例程，因为在那里您接下来无法执行那些例程。有2套可能已经执行的例程；和
1. 哪个例程在最后执行，因为这有助于确定下一个例程的成本。最多有R-1个可能的值。^{因此，可能的独奏状态少于（R-2）* 2}
2. R
。

想象一个有向图，它通过要达到该状态的例程的边缘将每个可能的状态连接到所有可能的跟随状态。用执行该例程的代价来标记每个边缘。^{例如，如果您执行了例程5和6，最后执行了5，那么您将处于（5,6）：5状态，并且（3,5,6）：3处于边缘状态您可以在执行例行程序3之后进入。}

[从初始的“什么都没做”状态（）开始：-，请使用Dijkstra的算法找到执行了所有例程的状态的成本最低的路径。

总复杂度大约为O（R

2

* 2

R

），具体取决于您如何实现。对于R = 10，R 2 * 2

R

为〜100 000，这根本不需要很长时间。对于R = 24，大约为90亿，在相当不错的C ++中，这将花费不到半分钟的时间。

Answer 1

[最多有10种可能的舞蹈例程，因此最多有3.6M个排列，甚至坏的算法（如全部生成它们并进行测试也将很快完成。