快速排列 -> 数字 -> 排列映射算法
https://stackoverflow.com/questions/1506078
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我有 n 个元素。举个例子，假设有 7 个元素，即 1234567。我知道有7个！= 这 7 个元素有 5040 种可能的排列。
我想要一个包含两个函数的快速算法：
f(number) 将 0 到 5039 之间的数字映射到唯一的排列，并且
f'（排列）将排列映射回其生成的数字。
我不关心数字和排列之间的对应关系，只要每个排列都有自己唯一的数字。
因此，例如，我可能有以下功能
f(0) = '1234567'
f'('1234567') = 0
我想到的最快的算法是枚举所有排列并在两个方向创建一个查找表，这样，一旦创建了表，f(0) 将是 O(1)，而 f('1234567') 将是在字符串上查找。然而，这会消耗内存，特别是当 n 变大时。
任何人都可以提出另一种可以快速运行并且没有内存缺点的算法吗？
解决方案
来描述一个排列的n元素，你会看到的位置，第一个元素结束了，你必须n可能性，所以你可以描述这一数量在0和n-1。对于该位置的下一个元素结束了，你有n-1剩余的可能性，所以你可以描述这一数量在0和n-2。
等等，直到你有n号码。
作为一个例子n=5，考虑排列，带来了 abcde 要 caebd.
a, 的第一个元素，结束了在第二位置，以便我们将它分配指数 1.b结束了第四位置，它将指标3，但这是第三个剩余的一个，所以我们将它分配 2.c结束了在第一个余下的位置，这是总是 0.d结束了在最后剩下的位置，(出的仅有的两个剩余的位置) 1.e结束了在唯一剩下的位置，编制索引 0.
因此，我们有指数序列 {1, 2, 0, 1, 0}.
现在，你知道，例如在二进制数字，'xyz'意味着z+2s+4倍。对于一个小号，
这是z+10y+100.每个数字乘以一些重，结果总结。明显的模式在的重量当然是重量w=b^k，b的基数和k索引的数字。(我将永远计数字的权利，并开始在index0右边的数字。同样地，当我们谈论"第一个"数字我指的是右边.)
的 的原因 为什么砝码为数字跟这个模式是，最高数量，可以由数字从0至k必须完全1低于最低的数字，可以通过表示只有使用数字k+1。在二，0111必须是一个低于1000。在小数，099999必须是一个低于100000.
编码至可变的基础
之间的间隔随后的数字是正1的重要规则。意识到这一点，我们可以代表我们的指数序列的通过 可变的基数.基于每个数字是数量的不同的可能性，该数字。用十进制的每个数字都有10的可能性，对于我们的系统右边的数字会有1的可能性，并最左将有n可能性。但是，由于最右边的数字(最后一个号码在我们顺序)是总是0,我们离开它。这意味着我们留下了碱2n.在一般情况下，第k个数字将基b[k]=k+2。值最高允许数字k h[k]=b[k]-1=k+1。
我们的规则有关的权w[k]的数字要求的总和h[i]*w[i]，在那里我从i=0至i=k，等于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一个列表中使用索引的序列
你可以用下面的算法重排列根据具体的指标顺序。这是一个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;
}
共同表示的排列
通常情况下你会不代表一个置换为unintuitively，因为我们已经做了，但仅仅通过的绝对位置的每一个元件后排列是适用的。我们的例子{1, 2, 0, 1, 0} 对于 abcde 要 caebd 通常是由{1, 3, 0, 4, 2}.每个指数，从0至4(或在一般情况下，0至n-1)的发生正是曾经在这表示。
申请一个置换在这种形式很简单：
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} 在我们的例子)。
获得非倒premutation，我们适用的换算法，我刚才表明：
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)。如果你需要申请一个置换好几次，第一次将其转换为常见的表示。
其他提示
我找到了一个 O(n) 算法，这是一个简短的解释 http://antoinecomeau.blogspot.ca/2014/07/mapping- Between-permutations-and.html
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;
}
在复杂性可以降低到的n * log（n）的，见10.1.1 所述fxtbook的（以下简称 “莱默代码（反转表）”，p.232ff）： http://www.jjj.de/fxt/#fxtbook 跳到章节10.1.1.1用于快速方法（“计算与大阵列” p.235）。 的（GPL的，C ++）码是在同一网页上。
每个元素可以在七个位置之一。为了描述一个元素的位置，你需要三位。这意味着你可以存储在一个32位值的所有元素的位置。这远远不是有效的，因为这表示会甚至让所有元素在同一个位置，但我相信该位掩码应该是相当快的。
然而，有超过8个位置，你需要更多的东西漂亮。
这恰好是在内置函数Ĵ：
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
问题解决了。但是，我不知道你还需要这些年后的溶液。 LOL，我刚刚加入这个网站，所以... 检查我的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
有乐趣。 ：）
可以使用递归算法编码排列。如果正置换（数字的一些排序{0，...，N-1}）的形式是{X，...}的编码，然后它为x + N *的编码的（N-1）上的数字表示为-permutation “...”{0，N-1} - {X}。听起来拗口，这里的一些代码：
// 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）的算法。积分
什么一个有趣的问题！
如果您所有的元素都是数字，你可能要考虑从字符串将它们转换为实际的数字。然后，你就可以通过把它们放在顺序排序的所有排列，并将它们放置在一个数组。在此之后，你会开放给任何的各种搜索算法在那里。
我是在我以前的答案（删除）匆忙，我确实有实际的答案虽然。它是由一个类似的概念， factoradic 提供，且与排列（我的答案相关对组合，我该道歉的混乱）。我不想只是张贴维基百科的链接，但我再去编写自己我做了一段时间以前是无法理解的某些原因。所以，我在此以后，如果要求扩大。
有是写此一本书。很抱歉，但我不记得它的名字（你会发现它很可能是从维基百科）。 但无论如何，我写了枚举系统的Python实现： http://kks.cabal.fi/Kombinaattori 有些是在芬兰，而只是复制代码，并将其命名变量...
一个相关的问题是计算逆置换，这将在仅排列阵列是已知的排列的矢量恢复到原来的顺序的置换。这里是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
大卫Spector的 春天软件
我有这个确切的问题并认为我会提供我的蟒蛇的解决方案。这是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
它相当直接的前进；后产生的factoradic代表性的数目，我只是挑选和删除的字符串。删除的字符串是为什么这个是O(n^2)的解决方案。
安东尼的解决方案是最好的业绩。
不隶属于 StackOverflow
