请问这个“字典顺序生成算法”的工作？

Question

这维基百科：

<强>辞书订单生成

  

有关每隔数k，其中0≤ķ

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;
 }

什么是在逻辑这背后？ 如何它的工作原理??

Answer 1

假设你有一个整数x，你想知道的是在百位数字是什么。要通过100计算这个，你先分，丢掉小数部分（如果x = 4723你想要的答案7.如）。 （在我们的例子，这留下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，因为有此列的三个可能的值。持续左，因为我们除以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等于（N-J）！这是显而易见的轮第一时间，因为j = 1，我们知道我们初始化factorial到（n-1）！稍后我们会看到，factorial确实总是（N-J）！

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

下面我们除以k factorial（其等于（N-j）的！）和扔掉残余物，然后我们取保持时，我们除以（N + 1-j）的结果。且慢，一切潺潺我开始开始听起来熟悉！我们只是从左边使用我们的“可变基数系统”发现第n列中的“位”的值！

此下位取索引之间的元素序列j和j + tempj和向右旋转时，其 - 即每个元素向上移动一个索引，除了最后一个，其移动回到开始。要认识到所有的位置j右边的数字是为了这一点很重要。我们有效地采摘其中一人出去，沿着轻推剩下的让他们在秩序。我们挑选哪一个出来取决于tempj。当tempj为0时，我们挑选的最小（和实际上不需要做任何轻推），当tempj等于n-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;

接着，第（n-j）的！除以（N-J）给出了（N-J-1）！ 如果你仔细想想，你应该看到，这意味着，当我们回到循环和j顶部已经加一，factorial将再次等于（N-J）！

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

我希望有点帮助！

Answer 2

想的多维阵列，的n项的所有排列的，具有尺寸：

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

任何多维数组可以被线性化到尺寸的一维数组：

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

这就像一个可变基数;在数字值的顺序去确实给你的数字词典顺序。

在索引使用来指代一个元组X [η] =例如(i[n],i[n-1]...,i[0])被sum_j i[j]*(j!)

因此，分割/ MOD被回收来自元组中的下一个位置。

在元组的第k个指标的值是尺寸以它的右边，这恰好为K的乘积！

Answer 3

假设u有初始序列作为[] = {1,2,3,4,5,6}的N = 6;和u要产生第k个烫发。 随着1对IST地方，u能产生5！ （即第（n-1）！）烫发用剩余的地方。

1 ,.......  

则u XCHANGE 1和2，并再次u能再次生成5！烫发。

2 ,.......

这样的想法是给定的K，我们需要找到k的程度。我的意思是： 说k为225，有多少5！确实K色：5分之245！ = 2 所以如果k = 245，因为我要生成的排列，第一位肯定是 3（即一个[2]）（bcoz打算2 * 5！= 240以后，要在交换网板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.)

这就是为什么在算法中，U不克/每第（n-1）！在第一次迭代。 和获得剩余k = k MOD（N-1）！这是k的新值，你要去递归做同样的事情（N-J）！对剩余的地方。