n 個の要素があります。例として、7 つの要素、1234567 としましょう。7 つあることはわかっています。= これらの 7 つの要素の可能な 5040 順列。
2 つの関数で構成される高速なアルゴリズムが必要です。
f(数値) は、0 から 5039 までの数値を一意の順列にマップし、
f'(permutation) は、順列を生成元の数値にマップします。
各順列に独自の番号がある場合、番号と順列の対応は気にしません。
したがって、たとえば、次のような関数があるかもしれません
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最初の要素である が 2 番目の位置になるため、インデックス1を割り当てます。bインデックス 3 となる 4 番目の位置になりますが、残り 3 番目であるため、2を割り当てます。c常に0である最初の残りの位置で終了します。d(残りの 2 つの位置のうち) 1である最後の残りの位置で終了します。e0でインデックス付けされた唯一の残りの位置で終了します。したがって、インデックス シーケンスは{1, 2, 0, 1, 0}です。
たとえば、2 進数では、「xyz」は z + 2y + 4x を意味することがわかりました。10 進数の場合は、
z + 10y + 100x です。各桁に重みが掛けられ、結果が合計されます。重みの明らかなパターンはもちろん、重みが w = b^k であり、b が数値の基数、k が数字のインデックスであることです。(私は常に右から数字を数え、一番右の数字のインデックス 0 から始めます。同様に、「最初の」数字について話すときは、一番右の数字を意味します。)
数字の重みがこのパターンに従う理由は、0 から k までの数字で表すことができる最大の数は、数字 k+1 のみを使用して表すことができる最小の数よりも正確に 1 小さい必要があるためです。2 進数では、0111 は 1000 より 1 小さい値でなければなりません。10 進数では、099999 は 100000 より 1 小さい値でなければなりません。
variable-base へのエンコード
後続の数値の間隔が正確に 1 であることが重要なルールです。これを実現すると、インデックス シーケンスを可変基数で表すことができます。各桁のベースは、その桁のさまざまな可能性の量です。10 進数の場合、各桁には 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 である必要があります。そこから開始すると、次の値になります。
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 番目 (右端、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 であり、正確には異なる順列の数です。したがって、エンコードされた数値がすべての可能な順列を完全に指定していることがわかります。
変数ベースからの
デコード デコードは、2 進数または 10 進数への変換に似ています。一般的なアルゴリズムは次のとおりです。
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}ですが、適切にインデックスを作成している限りは何でも構いません)。元のシーケンス {1, 2, 0, 1, 0} に戻すには、右端に 0 を追加するだけです (最後の要素には新しい位置の可能性が常に 1 つしかないことに注意してください)。
インデックス シーケンス
を使用したリストの並べ替え 以下のアルゴリズムを使用して、特定のインデックス シーケンスに従ってリストを並べ替えることができます。残念ながら、これは O(n²) アルゴリズムです。
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;
}
順列の一般的な表現
通常は、これまで行ってきたように直観的に順列を表現することはなく、順列が適用された後の各要素の絶対位置によって単純に表現します。abcdeこの例のtoの {1, 2, 0, 1, 0}caebdは、通常 {1, 3, 0, 4, 2} で表されます。0 から 4 (または一般的には 0 から n-1) の各インデックスは、この表現では 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} )。
反転されていないプレミューテーションを取得するには、先ほど示した順列アルゴリズムを適用します。
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(n²) であることに注意してください。順列を複数回適用する必要がある場合は、最初にそれを共通の表現に変換します。
複雑さは n*log(n) まで下げることができます。fxtbook のセクション 10.1.1 ("The Lehmer code (inversion table)"、p.232ff) を参照してください: http://www.jjj.de/fxt/ #fxtbook 高速な方法については、セクション 10.1.1.1 (「大きな配列を使用した計算」p.235) にスキップしてください。(GPLed、C++) コードは同じ Web ページにあります。
問題が解決しました。ただし、この数年後もまだソリューションが必要かどうかはわかりません。LOL、私はこのサイトに参加したばかりなので... Java Permutation Classをチェックしてください。インデックスに基づいてシンボル順列を取得するか、シンボル順列を指定してからインデックスを取得できます。
ここに私のPremutationクラスがあります
/**
****************************************************************************************************************
* 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
楽しむ。:)
これはたまたま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
各要素は、7 つの位置のいずれかに配置できます。1 つの要素の位置を記述するには、3 ビットが必要です。つまり、すべての要素の位置を 32 ビット値に格納できます。この表現ではすべての要素を同じ位置に配置できるため、効率的とは言えませんが、ビットマスキングはかなり高速になるはずです。
ただし、8 つ以上のポジションがある場合は、もっと気の利いたものが必要になります。
再帰的アルゴリズムを使用して順列をエンコードできます。N順列（番号{0、..、N-1}のいくつかの順序）が{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]++;
}
}
このアルゴリズムはO（n ^ 2）です。誰かがO（n）アルゴリズムを持っている場合のボーナスポイント。
なんて面白い質問でしょう。
すべての要素が数値である場合は、それらを文字列から実際の数値に変換することを検討することをお勧めします。次に、すべての順列を並べ替えて並べ替え、配列に配置することができます。その後、さまざまな検索アルゴリズムのいずれかを利用できるようになります。
これについて書かれた本があります。申し訳ありませんが、その名前は覚えていません (おそらくウィキペディアから見つけることができます)。とにかく、私はその列挙システムの python 実装を書きました: http://kks.cabal.fi/Kombinaattori 一部はフィンランド語ですが、コードをコピーして変数に名前を付けるだけです ...
私は以前の回答（削除）で急いでいましたが、実際の回答はあります。これは、同様の概念であるfactoradicによって提供され、順列に関連しています (組み合わせに関連する私の回答、その混乱をお詫びします)。ウィキペディアのリンクを投稿するのは嫌いですが、少し前に書いた記事は何らかの理由で理解できません。したがって、リクエストがあれば、後でこれを拡張できます。