1

Phillip Fuchs 教授有一个非常简洁的算法，可以使用纯迭代方法生成对象数组的排列（参见 quickperm.org）。基本上有 2 种变体，一种倒计时算法和一种计数（向上计数）算法。想法是相同的，只是初始化问题以及是否增加或减少“里程表”数字不同。

我已经研究了一段时间的算法，并且可以理解这个想法，除了一个特定的细节。在算法中，以及Fuchs教授对其算法的解释中，如果high index是偶数，low index设置为0；而如果高位指数为奇数，则低位指数设置为高位指数所指向的“里程表”位（原文使用j、i、p[]）：

lowIndex = (highIndex %2 == 0) ? 0 : odometerDigit[highIndex];

我只是很难理解这个逻辑。为什么 highIndex 为偶数或奇数确定 lowIndex 应为 0 或 odometerDigit 中的值？Fuchs 教授没有对此提供更详细的解释，但这就是算法的“魔力”症结所在。我真的很感激任何可以帮助我进一步理解这一点的见解。

4

1 回答 1

2

既然你踩了 N = 5（！），我会尝试一下。

除了 Fuchs 对递归的 [引证需要] 态度之外，我认为解释正在发生的事情的一种方法是他修改了以下递归算法。我希望这对你来说不是魔法。

def permute0(lst, n):
    if n < 2:
        print(lst)
    else:
        for j in range(n - 1, -1, -1):  # j in [0, n) descending
            # generate permutations with lst[n - 1] fixed
            lst[j], lst[n - 1] = lst[n - 1], lst[j]  # swap
            permute0(lst, n - 1)
            lst[j], lst[n - 1] = lst[n - 1], lst[j]  # swap back

第一个优化是，在内部堆栈帧中，只需要将变量的值j存储在他调用的数组中p。我不会打扰那个。

第二个优化是他做了一个交换切除术。我们可以通过不与自身交换元素来稍微减少交换。

def permute1(lst, n):
    if n < 2:
        print(lst)
    else:
        permute1(lst, n - 1)
        for j in range(n - 2, -1, -1):
            lst[j], lst[n - 1] = lst[n - 1], lst[j]
            permute1(lst, n - 1)
            lst[j], lst[n - 1] = lst[n - 1], lst[j]

为了进一步减少交换的数量，我们必须变得更聪明。permute2，与以前的版本不同，在返回之前不会恢复lst。permute2不是递归permute1的，因为它用来做脏活。

def permute2(lst, n):
    if n < 2:
        print(lst)
    else:
        permute1(lst, n - 1)
        for j in range(n - 2, -1, -1):
            lst[j], lst[n - 1] = lst[n - 1], lst[j]
            permute1(lst, n - 1)

permute2做什么lst？忽略对保持不变的调用permute1，它将一个元素向左旋转。现在我们可以编写，它调用并查找下一个元素以交换到放置它的位置，但我们不能编写整个s 塔。lstlstpermute2apermute2lst[n - 1]permute2permute

我们需要一个关于我们尚未存在的permute函数行为的归纳假设，我们可以用它来证明下一个。这是一种创造性的行为，也是计算机科学中许多“魔法”的来源。我要写的可能不是对我的想法的真实描述。

我们正在研究的算法类别有两个自然约束。首先，这些算法使交换次数最少。其次，它们是自相似的，并且在移动最后一个元素之前耗尽了前 N - 1 个元素的所有排列。这些约束一起强制将交换的元素之一存储在与 Fuchs 对应的位置i。

N = 0: there's only one permutation
N = 1: there's only one permutation
N = 2: the graph looks like 0 1 - 1 0
N = 3: the graph looks like

0 1 2   1 2 0   2 0 1
  |       |       |
   -------+-------     all bipartite connections
  |       |       |
0 2 1   2 1 0   1 0 2

在 不失一般性的情况下开始0 1 2。（初始内容lst无所谓。）那我们就要开始了

0 1 2  # forced w.l.o.g.
1 0 2  # forced because 2 cannot be moved yet.

唯一有趣的选择出现在这里。我们可以完成

2 0 1  # chose 1
0 2 1  # forced because 1 cannot be moved yet
1 2 0  # forced because we must move element 1 and 0 1 2 is already visited
2 1 0  # forced because 0 cannot be moved yet.

另一个可能的延续是

1 2 0  # chose 0
2 1 0  # forced because 0 cannot be moved yet
2 0 1  # forced because we must move element 0 and 0 1 2 is already visited
0 2 1  # forced because 1 cannot be moved yet.

在这一点上，我注意到 N = 2 和 N = 3 的第一种可能性都反转了排列。我将尝试构建permute3reverses lst。让我们看看它在 N = 4 时会做什么。

0 1 2 3
...
2 1 0 3
3 1 0 2
...
0 1 3 2
0 2 3 1
...
3 2 0 1
3 2 1 0
...
1 2 3 0  # oops

好吧，那没有用。我们需要奇数次递归调用才能使子数组反转。这是第一个建议，也许我们需要i奇数和i偶数的不同行为。

就像permute2，对于 N = 4，这个假设的算法将元素向左旋转一个。该主题的变化似乎是死胡同。这里已经够晚了，我已经做了足够多的徒劳无功的实验，Fuchs 的算法对我来说也开始看起来很神奇。

permute2a毕竟让我写。回想一下，将一个元素向左permute2旋转。lst如果在补偿旋转的同时permute2a随着位置的增加进行交换，它会重复交换相同的位置（例如，因为不能保证可以访问其他位置）。j0

def permute2a(lst, n):
    if n < 2:
        print(lst)
    else:
        permute2(lst, n - 1)
        for j in range(n - 2, -1, -1):
            lst[0], lst[n - 1] = lst[n - 1], lst[0]
            permute2(lst, n - 1)

现在，我意识到，如果permute2调用permute2a而不是permute1，这对几乎等同于 Fuchs 的算法。这对我来说似乎仍然很神奇，但现在是我收工的时候了。明天吧。

事实上，permute2a它不仅可以处理左旋转，还可以处理任何固定排列permute2，即循环，即，当重复应用于其域中的单个元素时，一个排列会给出所有其他元素。鉴于这种permute2行为方式，效果permute2a是应用permute2的 (N - 1) 循环置换 N 次，除了它在循环之间交换元素进出位置 0，效果是每个元素沿循环移动N - 1次，没有效果。因此，无论是什么， permute2aon的效果都是交换位置 0 和 N - 1。lstpermute2

现在我们要做的就是论证permute2可以使用permute2a. 的行为permute2a对permute2. 此外，由于permute2a仅涉及子数组的第一个和最后一个元素，因此当前的实现permute2大部分都在那里。事实上，如果 N 是偶数，它就可以正常工作。

0123
...
2103
2130
...
3120
3021
...
2031
1032
...
3012

N 奇数的问题是同一个元素将被交换两次到最后一个位置。

01234
...
31204
31240
...
41230
41032
...
31042
32041
...
42031
12034  # oops

我们现在要做的就是证明新permute2循环它的元素（当 N 是偶数时）。我将使用一些群论，因为我看不到简单的基本证明。在循环符号中，排列是

(0 n-2)(0 n-1)(0 n-2)(1 n-1)(0 n-2)...(0 n-2)(n-3 n-1)(0 n-2)(n-2 n-1)(0 n-2).

不相交的周期通勤。

(0 n-2)(0 n-1)[(0 n-2)...n-2 times...(0 n-2)](1 n-1)...(n-3 n-1)(n-2 n-1)(0 n-2).

由于 n 是偶数，因此 n-2 次连续交换无效。

(0 n-2)(0 n-1)(1 n-1)...(n-3 n-1)(n-2 n-1)(0 n-2).

正如我们之前观察到的，序列(0 n-1)(1 n-1)...(n-3 n-1)(n-2 n-1)是一个循环。

(0 n-2)(0 n-1 n-2 ... 1)(0 n-2).

这是一个共轭循环，这也是一个循环。

(0 n-3 n-4 ... 1 n-2 n-1).

这是最终版本。我声称它相当于 Fuchs 的算法以显式堆栈为模。

def permute3(lst, n):
    if n < 2:
        print(lst)
    else:
        permute3(lst, n - 1)
        for k in range(n - 2, -1, -1):
            i = n - 1
            j = 0 if i % 2 == 0 else k
            lst[j], lst[i] = lst[i], lst[j]
            permute3(lst, n - 1)
于 2013-04-16T03:59:39.373 回答