1

来自维基百科：

字典顺序生成

对于每个数字 k，0 ≤ k < n!，以下算法生成初始序列 sj, j = 1, ..., n 的相应词典排列：

function permutation(k, s) {
     var int n:= length(s); factorial:= 1;
     for j= 2 to n- 1 {             // compute (n- 1)!
         factorial:= factorial* j;
     }
     for j= 1 to n- 1 {
         tempj:= (k/ factorial) mod (n+ 1- j);
         temps:= s[j+ tempj]
         for i= j+ tempj to j+ 1 step -1 {
             s[i]:= s[i- 1];      // shift the chain right
         }
         s[j]:= temps;
         factorial:= factorial/ (n- j);
     }
     return s;
 }

这背后的逻辑是什么？它是如何工作的？？

4

3 回答 3

3

考虑一个多维数组，包含 n 项的所有排列，其维度为：

p[n][n-1][n-2]...[1]

任何多维数组都可以线性化为一维数组：

a[n*(n-1)*(n-2)*...*1]

这就像一个可变基数；按数值顺序进行确实会给您数字上的字典顺序。

您用来引用元组 x[n] = eg 的索引(i[n],i[n-1]...,i[0])是sum_j i[j]*(j!)

因此，除法/mod 正在从元组中恢复下一个位置。

元组中第 k 个索引的值是其右侧维度的乘积，恰好是 k!。

于 2009-09-19T01:50:50.560 回答
2

想象一下，你有一个整数x，你想知道百位是什么数字。（例如，如果 x=4723 你想要答案 7。）要计算这个，你首先除以 100，扔掉小数部分。（在我们的示例中，剩下 47。）然后除以 10 时找到余数。

现在假设您要查找千位中数字的值。要找到你首先除以 1000，丢弃小数部分，然后在除以 10 时再次找到余数。

在常规十进制编号系统中，每个位置都包含 10 个值之一。您可以观察到，在我们的数字查找练习中，我们首先除以我们关心的那个位置右侧的值的可能组合数（第一个示例中为 10 * 10）。然后我们在除以我们关心的地方的可能值的数量时找到余数。当然，所有地方都有 10 个可能的值，所以我们只需除以 10。

现在，想象一个编号系统，其中每个位置都有不同数量的值。我们最右边的位置可以有两个值，0 或 1。下一个位置可以有三个值，0、1 或 2；等等。在这个系统中，我们这样计算：

  0
  1
 10
 11
 20
 21
100
101
110
111
120
121
200
201
210
211
220
...

这就是 wrang-wrang 所指的“可变基数”。

现在，您可以看到我们如何计算该系统中某个位置的数字。要找到最右边的值，我们不需要先除，而是找到余数模 2，因为该列中的一个数字有 2 个可能的值。为了找到左边的下一列，我们首先除以右边列中数字的可能组合数：只有一列有两个可能的数字，所以我们除以 2。然后我们取余数模 3，因为该列有三个可能的值。继续向左，对于第 3 列，我们除以 6（因为右边的列各有 3 和 2 种可能性，相乘得到 6）然后取余数模 4，因为在这一列中有 4 个可能的值。

我们来看看函数：

function permutation(k, s) {
    var int n:= length(s); factorial:= 1;
    for j= 2 to n- 1 {             // compute (n- 1)!
        factorial:= factorial* j;
    }

factorial从 (n-1) 开始！

    for j= 1 to n- 1 {

每次我们到达这里，factorial都等于 (nj)！这在第一次很明显，因为j=1 并且我们知道我们初始化factorial为 (n-1)！我们稍后会看到factorial确实总是 (nj)！

        tempj:= (k/ factorial) mod (n+ 1- j);

这里我们除以k（factorial等于 (nj)！）并丢弃余数，然后当我们将结果除以 (n+1-j) 时取余数。等一下，我开始的所有喋喋不休开始听起来很熟悉！我们只是使用我们的“可变基数系统”在左起第 n 列中找到“数字”的值！

下一位获取索引之间的元素序列j并将j + tempj其向右旋转 - 即每个元素都向上移动一个索引，除了最后一个，它移回起点。重要的是要意识到位置 j 右侧的所有数字都是有序的。我们有效地将其中一个拔出并轻推其余的以保持它们井井有条。我们采摘哪一个取决于tempj。当tempj为 0 时，我们选择最小的（实际上不需要做任何微调），当tempj等于 nj 时，我们选择最大的。

        temps:= s[j+ tempj]
        for i= j+ tempj to j+ 1 step -1 {
            s[i]:= s[i- 1];      // shift the chain right
        }
        s[j]:= temps;

接下来，（nj）！除以 (nj) 得到 (nj-1)！如果你仔细想想，你应该看到这意味着当我们回到循环的顶部并j增加一时，factorial将再次等于 (nj)！

        factorial:= factorial/ (n- j);
    }
    return s;
}

我希望这会有所帮助！

于 2009-10-01T22:21:43.650 回答
1

假设你的初始序列为 a[] = { 1,2,3,4,5,6 } of n = 6; 你想生成第k个烫发。Ist place 有 1 个，你可以生成 5 个！（即 (n-1)! ）与其余位置一起烫发。

1 ,.......

然后你交换 1 和 2，你可以再次生成 5！烫发。

2 ,.......

所以给定k的想法，我们需要找到k的范围。我的意思是：说k是225，有多少5！k 有：245/5！= 2 所以如果k = 245，在我要生成的排列中，第一名肯定是3（即a[2]）（bcoz经过2*5！= 240，我将xchange 1和3），我会有

3,1,2,4,5,6 (the array a[] obtained after shifting the chain)
(why we are shifting is to make the remaining array sorted for the 
  next iteration so that lexicographic order is maintained.)

这就是为什么在算法中，你做 k/(n-1)！在第一次迭代中。并获得余数 k = k mod (n-1)!。这是 k 的新值，你用 (nj) 递归地做同样的事情！在剩下的地方。

于 2009-10-05T07:12:40.523 回答