快速排列 – >数字 – >置换映射algorithm
我有n个元素。 举例来说，我们说7个元素1234567.我知道有7个元素！ 这7个元素可能有5040个排列组合。
我想要一个包含两个函数的快速algorithm：
f（数字）将0到5039之间的数字映射到一个唯一的排列，
f'（排列）将排列映射回其生成的数字。
我并不关心数字与排列之间的对应关系，只要每个排列都有自己独特的数字。
所以，例如，我可能有function在哪里
f(0) = '1234567' f'('1234567') = 0 想到的最快的algorithm是枚举所有排列并在两个方向上创build一个查找表，所以一旦创build表，f（0）将是O（1），f（'1234567'）将是在一个string上查找。 但是，这是一个饥饿的记忆，特别是当n变大的时候。
任何人都可以提出另一种algorithm，快速工作，没有内存的缺点？
为了描述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 + 2y + 4x。 对于十进制数字，
它是z + 10y + 100x。 每个数字乘以一定的权重，并将结果相加。 权重的明显模式当然是权重是w = b ^ k，其中b是数字的基数，k是数字的指数。 （我总是会从右边的数字开始计数，从最右边的数字开始到索引0，同样，当我谈到“第一个”时，我指的是最右边的数字。
数字的权重之所以遵循这种模式，是因为从0到k的数字所能表示的最高数字必须恰好低于只能用数字k + 1表示的最低数字。 在二进制中，0111必须小于1000.十进制中，099999必须小于100000。
编码为可变基础
后续数字之间的间隔正好是1是重要的规则。 意识到这一点，我们可以用一个可变基数来表示我们的索引序列。 每个数字的基数是该数字的不同可能性的数量。 对于小数每个数字有10个可能性，对于我们的系统，最右边的数字有1个可能性，最左边的数字有n个可能性。 但是由于最右边的数字（我们序列中的最后一个数字）始终为0，所以我们将其忽略。 这意味着我们剩下的基地2至n。 通常，第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.从那里开始，我们有以下值：
kh[k] w[k] 0 1 1 1 2 2 2 3 6 3 4 24 ... ... ... n-1 nn!
（一般关系w [k-1] = k！很容易通过归纳certificate。）
我们从转换我们的序列中得到的数字就是s [k] * w [k]的和，k从0到n-1。 这里s [k]是序列的第k个元素（最右边，从0开始）。 作为一个例子，取如我们之前提到的{ 1，2，0，1}，剥去最右边的元素{ 1,2,0,1,0 } 。 我们的总和是1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 37 。
请注意，如果我们对每个索引采取最大的位置，我们将有{4,3,2,1,0}，并将其转换为119.由于我们的数字编码中的权重被select，所以我们不跳过任何数字，所有数字0到119是有效的。 正好有120个这是n！ 在我们的例子中n = 5，正好是不同排列的数目。 所以你可以看到我们编码的数字完全指定了所有可能的排列。
从可变基地解码
解码类似于转换为二进制或十进制。 常用的algorithm是这样的：
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 }
这正确地解码我们回到{1，2，0，1}（在这个代码示例中， sequence将是{1, 0, 2, 1} ，但无论…只要您适当地索引）。 我们只需要在右端添加0（记住，最后一个元素总是只有一个可能的位置）来取回原始序列{1,2,0,1,0}。
使用索引序列来排列列表
您可以使用下面的algorithm根据特定的索引序列对列表进行置换。 这是一个O（n²）algorithm，不幸的。
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; }
常见的排列组合
通常情况下，您不会像我们所做的那样直观地表示排列，而仅仅是排列后的每个元素的绝对位置。 我们的例子{ caebd }用于caebd abcde通常由{ caebd }表示。 在这种表示中，从0到4（或通常0到n-1）的每个索引恰好出现一次。
以这种forms应用排列很简单：
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]]; }
从我们的代表转换到共同的代表
请注意，如果我们使用我们的algorithm来使用我们的索引序列对列表进行置换，并将其应用于身份置换{0,1,2，…，n-1}，则我们得到以常用forms表示的逆置换。 （在我们的例子中是{2，0，4，1，3} ）。
为了得到非反转前处理，我们使用我刚刚展示的置换algorithm：
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]; }
或者，您可以直接使用逆置换algorithm来应用置换：
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]]; }
注意，所有用于处理常见forms的排列的algorithm是O（n），而在我们的forms中应用排列是O（n2）。 如果您需要多次应用排列，请首先将其转换为常用表示。
我在O（n）中做了一个algorithm，你可以在这里find我的函数： 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%(ni); m=m/(ni); permuted[i]=elems[ind]; elems[ind]=elems[ni-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*(ni); pos[elems[ni-1]]=pos[perm[i]]; elems[pos[perm[i]]]=elems[ni-1]; } return k; }
每个元素可以在七个位置之一。 为了描述一个元素的位置，你需要三位。 这意味着您可以将所有元素的位置存储在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 * log（n），参见fxtbook的第10.1.1节（“Lehmer代码（反转表）”，p.232ff）： http ://www.jjj.de/fxt/ #fxtbook跳转到第10.1.1.1节（“用大数组计算”，第235页）快速方法。 （GPLed，C ++）代码在同一个网页上。
问题解决了。 但是，我不确定你在这些年后还是需要解决scheme。 大声笑，我只是join这个网站，所以…检查我的Java排列类。 您可以基于索引来获得符号排列，或者给出符号排列然后获得索引。
这是我的总理class
/** **************************************************************************************************************** * 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!/(nr)! * 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 arning ==== * *************************************************************************************************************** * * 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. // // ====== WARNING ====== // // 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!/(nr)! 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 // xoooox -> in use; o -> free only 0 is being used // ss ^ 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 // ss ^ 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(" ***************** FAILED *************************"); assert(true); break; } } } } } // // End of file - Main.java
玩的开心。 🙂
我在之前的回答中很仓促（删除），但我确实有实际的答案。 它是由一个类似的概念， factoradic ，并与排列相关（我的答案有关的组合，我为此混淆道歉）。 我讨厌发布维基百科链接，但是我之前做过的写作是由于某种原因无法理解的。 所以，如果要求的话，我可以稍后扩展。
您可以使用recursionalgorithm对置换进行编码。 如果N置换（数字{0，…，N-1}的某些sorting）的forms为{x，…}，那么将其编码为x + N *（N-1） – 数字{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]++; } }
这个algorithm是O（n ^ 2）。 如果任何人有O（n）algorithm，奖励点。
多么有趣的问题！
如果你所有的元素都是数字，你可能要考虑把它们从string转换成实际的数字。 然后你可以把所有的排列顺序排列，然后把它们放在一个数组中。 在那之后，你会开放任何各种searchalgorithm。
有一本关于这个的书。 对不起，但我不记得它的名字（你可能会从维基百科中find它）。 但无论如何，我写了一个该枚举系统的python实现： http : //kks.cabal.fi/Kombinaattori有些是在芬兰，但只是复制代码和名称variables…
