Fast permutation -> number -> permutation mapping algorithms

小开

每个元素可以位于七个位置中的一个。要描述一个元素的位置，需要三个位。这意味着您可以将所有元素的位置存储在一个32位值中。这远远不够有效，因为这种表示甚至允许所有元素处于相同的位置，但我认为位掩码应该相当快。

然而，超过8个职位，你需要更漂亮的东西。

小开

多么有趣的问题！

如果所有元素都是数字，则可能需要考虑将它们从字符串转换为实际数字。然后，您就可以将所有的排列按顺序排序，并将它们放置在一个数组中。在那之后，你可以使用任何一种搜索算法。

小开

这恰好是 J中的一个内置函数:

   A. 1 2 3 4 5 6 7
0
0 A. 1 2 3 4 5 6 7
1 2 3 4 5 6 7


?!7
5011
5011 A. 1 2 3 4 5 6 7
7 6 4 5 1 3 2
A. 7 6 4 5 1 3 2
5011

小开

最佳答案

为了描述 n 个元素的排列你可以看到对于第一个元素最终到达的位置你有 n 个可能性所以你可以用0到 n-1之间的数字来描述它。对于下一个元素最终到达的位置，剩下的可能性是 n-1，因此可以用0到 n-2之间的数字来描述它。
等等，直到你有 n 个数字。

以 n = 5为例，考虑将 abcde置换为 caebd的排列。

a, the first element, ends up at the second position, so we assign it index 1.
b最终位于第四个位置，也就是索引3，但它是剩下的第三个位置，所以我们把它分配给 2。
c最终位于第一个剩余位置，该位置始终是 0。
d最终到达最后剩余的位置，这个位置(只剩下两个位置)是 1。
e最终位于唯一剩余的位置，索引位于 0。

我们得到了索引序列 {1,2,0,1,0}。

Now you know that for instance in a binary number, 'xyz' means z + 2y + 4x. For a decimal number,
是 z + 10y + 100x。将每个数字乘以某个权重，然后对结果进行求和。权重的明显模式当然是 w = b ^ k，b 是数字的基数，k 是数字的索引。(我总是从右边开始数数字，从索引0开始数最右边的数字。同样，当我说到“第一个”数字时，我指的是最右边的数字。)

数字的权重遵循这种模式的原因是，从0到 k 的数字所能表示的最高数字必须正好比只能用数字 k + 1表示的最低数字低1。在二进制中，0111必须小于1000。在十进制中，099999必须小于100000。

变量基编码
后续数字之间的间距正好为1是一个重要的规则。认识到这一点，我们可以用 可变基数可变基数表示索引序列。每个数字的基数是该数字的不同可能性的数量。对于十进制，每个数字有10个可能性，对于我们的系统，最右边的数字有1个可能性，最左边的数字有 n 个可能性。但是因为最右边的数字(我们序列中的最后一个数字)总是0，所以我们省略了它。这意味着我们只剩下基数2到 n。一般来说，k‘ th 数字的基数是 b [ k ] = k + 2。数字 k 允许的最高值是 h [ k ] = b [ k ]-1 = k + 1。

我们关于数字权重 w [ k ]的规则要求 h [ i ] * w [ i ]的和等于1 * w [ k + 1]。W [ k + 1] = w [ k ] + h [ k ] * w [ k ] = w [ k ] * (h [ k ] + 1).第一个权重 w [0]应该总是1。从这里开始，我们有以下值:

k    h[k] w[k]


0    1    1
1    2    2
2    3    6
3    4    24
...  ...  ...
n-1  n    n!

(w [ k-1] = k! 的一般关系很容易用归纳法证明。)

我们通过转换序列得到的数字将是 s [ k ] * w [ k ]的和，k 从0运行到 n-1。这里 s [ k ]是序列的 k‘ th (最右边，从0开始)元素。以{1,2,0,1,0}为例，如前所述，去掉最右边的元素: {1,2,0,1}。我们的和是1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 37。

注意，如果我们取每个索引的最大位置，我们将得到{4,3,2,1,0} ，并将其转换为119。因为我们选择了数字编码中的权重，所以我们不会跳过任何数字，所有数字0到119都是有效的。一共有120个，也就是 n！对于我们的例子中的 n = 5，正好是不同排列的数目。所以你可以看到我们编码的数字完全指定了所有可能的排列。

基于变量的解码
译码类似于转换成二进制或十进制。通常的算法是这样的:

int number = 42;
int base = 2;
int[] bits = new int[n];


for (int k = 0; k < bits.Length; k++)
{
bits[k] = number % base;
number = number / base;
}

对于我们的可变基数:

int n = 5;
int number = 37;


int[] sequence = new int[n - 1];
int base = 2;


for (int k = 0; k < sequence.Length; k++)
{
sequence[k] = number % base;
number = number / base;


base++; // b[k+1] = b[k] + 1
}

这将我们的37正确地解码回{1,2,0,1}(在这个代码示例中，sequence应该是 {1, 0, 2, 1}，但是无论如何... ... 只要您适当地索引)。我们只需要在右端加上0(记住最后一个元素的新位置总是只有一个可能性) ，就可以得到原来的序列{1,2,0,1,0}。

Permuting a list using an index sequence
可以使用下面的算法根据特定的索引序列对列表进行排序。不幸的是，这是 O (n2)算法。

int n = 5;
int[] sequence = new int[] { 1, 2, 0, 1, 0 };
char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];
bool[] set = new bool[n];


for (int i = 0; i < n; i++)
{
int s = sequence[i];
int remainingPosition = 0;
int index;


// Find the s'th position in the permuted list that has not been set yet.
for (index = 0; index < n; index++)
{
if (!set[index])
{
if (remainingPosition == s)
break;


remainingPosition++;
}
}


permuted[index] = list[i];
set[index] = true;
}

排列的公共表示法
Normally you would not represent a permutation as unintuitively as we've done, but simply by the absolute position of each element after the permutation is applied. Our example {1, 2, 0, 1, 0} for abcde to caebd is normally represented by {1, 3, 0, 4, 2}. Each index from 0 to 4 (or in general, 0 to n-1) occurs exactly once in this representation.

Applying a permutation in this form is easy:

int[] permutation = new int[] { 1, 3, 0, 4, 2 };


char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];


for (int i = 0; i < n; i++)
{
permuted[permutation[i]] = list[i];
}

反过来看，情况非常相似:

for (int i = 0; i < n; i++)
{
list[i] = permuted[permutation[i]];
}

从我们的表示转换为公共表示
注意，如果我们使用我们的算法使用索引序列排列一个列表，并将其应用于恒等位置置换{0,1,2，... ，n-1} ，我们将得到相反置换，以公共形式表示。(在我们的例子中是 {2, 0, 4, 1, 3})。

为了得到非倒置预置，我们应用我刚才展示的排列算法:

int[] identity = new int[] { 0, 1, 2, 3, 4 };
int[] inverted = { 2, 0, 4, 1, 3 };
int[] normal = new int[n];


for (int i = 0; i < n; i++)
{
normal[identity[i]] = list[i];
}

或者你可以直接应用排列，通过使用逆排列算法:

char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];


int[] inverted = { 2, 0, 4, 1, 3 };


for (int i = 0; i < n; i++)
{
permuted[i] = list[inverted[i]];
}

注意，处理常见形式的排列的所有算法都是 O (n) ，而在我们的形式中应用排列的算法都是 O (n2)。如果需要多次应用排列，首先将其转换为公共表示形式。

小开

我之前的回答是草率的(删除) ，但我确实有实际的答案。它是由一个类似的概念因子提供的，并且与排列有关(我的答案与组合有关，我为那个混淆道歉)。我讨厌仅仅发布维基百科的链接，但是由于某些原因，我前一段时间发布的内容让人难以理解。如果你需要，我可以稍后再详细说明。

小开

可以使用递归算法对排列进行编码。如果一个 N- 排列(数字{0，... ，N-1}的某种排序)是{ x，... }的形式，那么将它编码为 x + N * ，这是在数字{0，N-1}-{ x }上用“ ...”表示的(N-1)-排列的编码。听起来很拗口，这里有一些代码:

// perm[0]..perm[n-1] must contain the numbers in {0,..,n-1} in any order.
int permToNumber(int *perm, int n) {
// base case
if (n == 1) return 0;


// fix up perm[1]..perm[n-1] to be a permutation on {0,..,n-2}.
for (int i = 1; i < n; i++) {
if (perm[i] > perm[0]) perm[i]--;
}


// recursively compute
return perm[0] + n * permToNumber(perm + 1, n - 1);
}


// number must be >=0, < n!
void numberToPerm(int number, int *perm, int n) {
if (n == 1) {
perm[0] = 0;
return;
}
perm[0] = number % n;
numberToPerm(number / n, perm + 1, n - 1);


// fix up perm[1] .. perm[n-1]
for (int i = 1; i < n; i++) {
if (perm[i] >= perm[0]) perm[i]++;
}
}

这个算法是 O (n ^ 2)。如果有人有一个 O (n)算法，加分。

小开

There is a book written about this. Sorry, but I do not remember the name of it (you will find it quite probably from wikipedia). 但无论如何，我编写了一个枚举系统的 python 实现: http://kks.cabal.fi/Kombinaattori 有些是芬兰语，但只要复制代码和名称变量..。

小开

复杂性可以归结为 n * log (n) ，参见10.1.1节 ("The Lehmer code (inversion table)", p.232ff) of the fxtbook: Http://www.jjj.de/fxt/#fxtbook 有关快速方法，请跳到第10.1.1.1节(“使用大数组进行计算”，第235页)。 (GPLed，C + +)代码在同一个网页上。

小开

我发现了一个运行在 O (n)中的算法(在通常的复杂性假设下) ，这里有一个简短的解释 http://antoinecomeau.blogspot.ca/2014/07/mapping-between-permutations-and.html。

注意: 考虑到 computational complexity of division，该算法的实际运行时间为 O (n ^ 2 log ^ 2(n))。

public static int[] perm(int n, int k)
{
int i, ind, m=k;
int[] permuted = new int[n];
int[] elems = new int[n];


for(i=0;i<n;i++) elems[i]=i;
           

for(i=0;i<n;i++)
{
ind=m%(n-i);
m=m/(n-i);
permuted[i]=elems[ind];
elems[ind]=elems[n-i-1];
}
           

return permuted;
}
   

public static int inv(int[] perm)
{
int i, k=0, m=1;
int n=perm.length;
int[] pos = new int[n];
int[] elems = new int[n];
           

for(i=0;i<n;i++) {pos[i]=i; elems[i]=i;}
           

for(i=0;i<n-1;i++)
{
k+=m*pos[perm[i]];
m=m*(n-i);
pos[elems[n-i-1]]=pos[perm[i]];
elems[pos[perm[i]]]=elems[n-i-1];
}
           

return k;
}

小开

问题解决了。然而，我不确定这么多年过去了，你还需要这个解决方案。哈哈，我刚加入这个网站，所以..。检查我的 Java 置换类。您可以基于索引来获得符号排列，或者给出一个符号排列，然后获得索引。

这是我的预备课程

/**
****************************************************************************************************************
* Copyright 2015 Fred Pang fred@pnode.com
****************************************************************************************************************
* A complete list of Permutation base on an index.
* Algorithm is invented and implemented by Fred Pang fred@pnode.com
* Created by Fred Pang on 18/11/2015.
****************************************************************************************************************
* LOL this is my first Java project. Therefore, my code is very much like C/C++. The coding itself is not
* very professional. but...
*
* This Permutation Class can be use to generate a complete list of all different permutation of a set of symbols.
* nPr will be n!/(n-r)!
* the user can input       n = the number of items,
*                          r = the number of slots for the items,
*                          provided n >= r
*                          and a string of single character symbols
*
* the program will generate all possible permutation for the condition.
*
* Say if n = 5, r = 3, and the string is "12345", it will generate sll 60 different permutation of the set
* of 3 character strings.
*
* The algorithm I used is base on a bin slot.
* Just like a human or simply myself to generate a permutation.
*
* if there are 5 symbols to chose from, I'll have 5 bin slot to indicate which symbol is taken.
*
* Note that, once the Permutation object is initialized, or after the constructor is called, the permutation
* table and all entries are defined, including an index.
*
* eg. if pass in value is 5 chose 3, and say the symbol string is "12345"
* then all permutation table is logically defined (not physically to save memory).
* It will be a table as follows
*  index  output
*      0   123
*      1   124
*      2   125
*      3   132
*      4   134
*      5   135
*      6   143
*      7   145
*      :     :
*      58  542
*      59  543
*
* all you need to do is call the "String PermGetString(int iIndex)" or the "int[] PermGetIntArray(int iIndex)"
* function or method with an increasing iIndex, starting from 0 to getiMaxIndex() - 1. It will return the string
* or the integer array corresponding to the index.
*
* Also notice that in the input string is "12345" of  position 01234, and the output is always in accenting order
* this is how the permutation is generated.
*
* ***************************************************************************************************************
* ====  W a r n i n g  ====
* ***************************************************************************************************************
*
* There is very limited error checking in this class
*
* Especially the  int PermGetIndex(int[] iInputArray)  method
* if the input integer array contains invalid index, it WILL crash the system
*
* the other is the string of symbol pass in when the object is created, not sure what will happen if the
* string is invalid.
* ***************************************************************************************************************
*
*/
public class Permutation
{
private boolean bGoodToGo = false;      // object status
private boolean bNoSymbol = true;
private BinSlot slot;                   // a bin slot of size n (input)
private int nTotal;                     // n number for permutation
private int rChose;                     // r position to chose
private String sSymbol;                 // character string for symbol of each choice
private String sOutStr;
private int iMaxIndex;                  // maximum index allowed in the Get index function
private int[] iOutPosition;             // output array
private int[] iDivisorArray;            // array to do calculation


public Permutation(int inCount, int irCount, String symbol)
{
if (inCount >= irCount)
{
// save all input values passed in
this.nTotal = inCount;
this.rChose = irCount;
this.sSymbol = symbol;


// some error checking
if (inCount < irCount || irCount <= 0)
return;                                 // do nothing will not set the bGoodToGo flag


if (this.sSymbol.length() >= inCount)
{
bNoSymbol = false;
}


// allocate output storage
this.iOutPosition = new int[this.rChose];


// initialize the bin slot with the right size
this.slot = new BinSlot(this.nTotal);


// allocate and initialize divid array
this.iDivisorArray = new int[this.rChose];


// calculate default values base on n & r
this.iMaxIndex = CalPremFormula(this.nTotal, this.rChose);


int i;
int j = this.nTotal - 1;
int k = this.rChose - 1;


for (i = 0; i < this.rChose; i++)
{
this.iDivisorArray[i] = CalPremFormula(j--, k--);
}
bGoodToGo = true;       // we are ready to go
}
}


public String PermGetString(int iIndex)
{
if (!this.bGoodToGo) return "Error: Object not initialized Correctly";
if (this.bNoSymbol) return "Error: Invalid symbol string";
if (!this.PermEvaluate(iIndex)) return "Invalid Index";


sOutStr = "";
// convert string back to String output
for (int i = 0; i < this.rChose; i++)
{
String sTempStr = this.sSymbol.substring(this.iOutPosition[i], iOutPosition[i] + 1);
this.sOutStr = this.sOutStr.concat(sTempStr);
}
return this.sOutStr;
}


public int[] PermGetIntArray(int iIndex)
{
if (!this.bGoodToGo) return null;
if (!this.PermEvaluate(iIndex)) return null ;
return this.iOutPosition;
}


// given an int array, and get the index back.
//
//  ====== W A R N I N G ======
//
// there is no error check in the array that pass in
// if any invalid value in the input array, it can cause system crash or other unexpected result
//
// function pass in an int array generated by the PermGetIntArray() method
// then return the index value.
//
// this is the reverse of the PermGetIntArray()
//
public int PermGetIndex(int[] iInputArray)
{
if (!this.bGoodToGo) return -1;
return PermDoReverse(iInputArray);
}




public int getiMaxIndex() {
return iMaxIndex;
}


// function to evaluate nPr = n!/(n-r)!
public int CalPremFormula(int n, int r)
{
int j = n;
int k = 1;
for (int i = 0; i < r; i++, j--)
{
k *= j;
}
return k;
}




//  PermEvaluate function (method) base on an index input, evaluate the correspond permuted symbol location
//  then output it to the iOutPosition array.
//
//  In the iOutPosition[], each array element corresponding to the symbol location in the input string symbol.
//  from location 0 to length of string - 1.


private boolean PermEvaluate(int iIndex)
{
int iCurrentIndex;
int iCurrentRemainder;
int iCurrentValue = iIndex;
int iCurrentOutSlot;
int iLoopCount;


if (iIndex >= iMaxIndex)
return false;


this.slot.binReset();               // clear bin content
iLoopCount = 0;
do {
// evaluate the table position
iCurrentIndex = iCurrentValue / this.iDivisorArray[iLoopCount];
iCurrentRemainder = iCurrentValue % this.iDivisorArray[iLoopCount];


iCurrentOutSlot = this.slot.FindFreeBin(iCurrentIndex);     // find an available slot
if (iCurrentOutSlot >= 0)
this.iOutPosition[iLoopCount] = iCurrentOutSlot;
else return false;                                          // fail to find a slot, quit now


this.slot.setStatus(iCurrentOutSlot);                       // set the slot to be taken
iCurrentValue = iCurrentRemainder;                          // set new value for current value.
iLoopCount++;                                               // increase counter
} while (iLoopCount < this.rChose);


// the output is ready in iOutPosition[]
return true;
}


//
// this function is doing the reverse of the permutation
// the input is a permutation and will find the correspond index value for that entry
// which is doing the opposit of the PermEvaluate() method
//
private int PermDoReverse(int[] iInputArray)
{
int iReturnValue = 0;
int iLoopIndex;
int iCurrentValue;
int iBinLocation;


this.slot.binReset();               // clear bin content


for (iLoopIndex = 0; iLoopIndex < this.rChose; iLoopIndex++)
{
iCurrentValue = iInputArray[iLoopIndex];
iBinLocation = this.slot.BinCountFree(iCurrentValue);
this.slot.setStatus(iCurrentValue);                          // set the slot to be taken
iReturnValue = iReturnValue + iBinLocation * this.iDivisorArray[iLoopIndex];
}
return iReturnValue;
}




/*******************************************************************************************************************
*******************************************************************************************************************
* Created by Fred on 18/11/2015.   fred@pnode.com
*
* *****************************************************************************************************************
*/
private static class BinSlot
{
private int iBinSize;       // size of array
private short[] eStatus;    // the status array must have length iBinSize


private BinSlot(int iBinSize)
{
this.iBinSize = iBinSize;               // save bin size
this.eStatus = new short[iBinSize];     // llocate status array
}


// reset the bin content. no symbol is in use
private void binReset()
{
// reset the bin's content
for (int i = 0; i < this.iBinSize; i++) this.eStatus[i] = 0;
}


// set the bin position as taken or the number is already used, cannot be use again.
private void  setStatus(int iIndex) { this.eStatus[iIndex]= 1; }


//
// to search for the iIndex th unused symbol
// this is important to search through the iindex th symbol
// because this is how the table is setup. (or the remainder means)
// note: iIndex is the remainder of the calculation
//
// for example:
// in a 5 choose 3 permutation symbols "12345",
// the index 7 item (count starting from 0) element is "1 4 3"
// then comes the index 8, 8/12 result 0 -> 0th symbol in symbol string = '1'
// remainder 8. then 8/3 = 2, now we need to scan the Bin and skip 2 unused bins
//              current the bin looks 0 1 2 3 4
//                                    x o o o o     x -> in use; o -> free only 0 is being used
//                                      s s ^       skipped 2 bins (bin 1 and 2), we get to bin 3
//                                                  and bin 3 is the bin needed. Thus symbol "4" is pick
// in 8/3, there is a remainder 2 comes in this function as 2/1 = 2, now we have to pick the empty slot
// for the new 2.
// the bin now looks 0 1 2 3 4
//                   x 0 0 x 0      as bin 3 was used by the last value
//                     s s   ^      we skip 2 free bins and the next free bin is bin 4
//                                  therefor the symbol "5" at the symbol array is pick.
//
// Thus, for index 8  "1 4 5" is the symbols.
//
//
private int FindFreeBin(int iIndex)
{
int j = iIndex;


if (j < 0 || j > this.iBinSize) return -1;               // invalid index


for (int i = 0; i < this.iBinSize; i++)
{
if (this.eStatus[i] == 0)       // is it used
{
// found an empty slot
if (j == 0)                 // this is a free one we want?
return i;               // yes, found and return it.
else                        // we have to skip this one
j--;                    // else, keep looking and count the skipped one
}
}
assert(true);           // something is wrong
return -1;              // fail to find the bin we wanted
}


//
// this function is to help the PermDoReverse() to find out what is the corresponding
// value during should be added to the index value.
//
// it is doing the opposite of int FindFreeBin(int iIndex) method. You need to know how this
// FindFreeBin() works before looking into this function.
//
private int BinCountFree(int iIndex)
{
int iRetVal = 0;
for (int i = iIndex; i > 0; i--)
{
if (this.eStatus[i-1] == 0)       // it is free
{
iRetVal++;
}
}
return iRetVal;
}
}
}
// End of file - Permutation.java

这是我的主类，用来演示如何使用这个类。

/*
* copyright 2015 Fred Pang
*
* This is the main test program for testing the Permutation Class I created.
* It can be use to demonstrate how to use the Permutation Class and its methods to generate a complete
* list of a permutation. It also support function to get back the index value as pass in a permutation.
*
* As you can see my Java is not very good. :)
* This is my 1st Java project I created. As I am a C/C++ programmer for years.
*
* I still have problem with the Scanner class and the System class.
* Note that there is only very limited error checking
*
*
*/


import java.util.Scanner;


public class Main
{
private static Scanner scanner = new Scanner(System.in);


public static void main(String[] args)
{
Permutation perm;       // declear the object
String sOutString = "";
int nCount;
int rCount;
int iMaxIndex;


// Get user input
System.out.println("Enter n: ");
nCount = scanner.nextInt();


System.out.println("Enter r: ");
rCount = scanner.nextInt();


System.out.println("Enter Symbol: ");
sOutString = scanner.next();


if (sOutString.length() < rCount)
{
System.out.println("String too short, default to numbers");
sOutString = "";
}


// create object with user requirement
perm = new Permutation(nCount, rCount, sOutString);


// and print the maximum count
iMaxIndex = perm.getiMaxIndex();
System.out.println("Max count is:" + iMaxIndex);


if (!sOutString.isEmpty())
{
for (int i = 0; i < iMaxIndex; i++)
{   // print out the return permutation symbol string
System.out.println(i + " " + perm.PermGetString(i));
}
}
else
{
for (int i = 0; i < iMaxIndex; i++)
{
System.out.print(i + " ->");


// Get the permutation array
int[] iTemp = perm.PermGetIntArray(i);


// print out the permutation
for (int j = 0; j < rCount; j++)
{
System.out.print(' ');
System.out.print(iTemp[j]);
}


// to verify my PermGetIndex() works. :)
if (perm.PermGetIndex(iTemp)== i)
{
System.out.println(" .");
}
else
{   // oops something is wrong :(
System.out.println(" ***************** F A I L E D *************************");
assert(true);
break;
}
}
}
}
}
//
// End of file - Main.java

玩得开心

小开

一个相关的问题是计算逆置换，这种置换将置换向量恢复到原来的顺序，当只有置换阵列是已知的。下面是 O (n)代码(在 PHP 中) :

// Compute the inverse of a permutation
function GetInvPerm($Perm)
{
$n=count($Perm);
$InvPerm=[];
for ($i=0; $i<$n; ++$i)
$InvPerm[$Perm[$i]]=$i;
return $InvPerm;
} // GetInvPerm

大卫 · 斯派特春季软件

小开

我有这样一个问题，我想我可以提供我的 Python 解决方案，它是 O (n ^ 2)。

import copy


def permute(string, num):
''' generates a permutation '''
def build_s(factoradic): # Build string from factoradic in list form
string0 = copy.copy(string)
n = []
for i in range(len(factoradic)):
n.append(string0[factoradic[i]])
del string0[factoradic[i]]
return n


f = len(string)
factoradic = []
while(f != 0): # Generate factoradic number list
factoradic.append(num % f)
num = (num - factoradic[-1])//f
f -= 1


return build_s(factoradic)


s = set()
# Print 120 permutations of this string
for i in range(120):
m = permute(list('abcde'), i)
s.add(''.join(m))


print(len(s)) # Check that we have 120 unique permutations

这非常简单; 在生成数字的阶乘表示之后，我只是从字符串中挑选和删除字符。从字符串中删除是为什么这是一个 O (n ^ 2)解决方案。

安托万的解决方案对性能更有利。

小开

本文提出了一种简单明了的算法 Ranking and unranking permutations in linear time，并对算法进行了说明。它在最多 n 个算术运算中将一个整数映射到一个排列。