빠른 순열 -> 숫자 -> 순열 매핑 알고리즘
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 + 2y + 4x를 의미한다는 것을 알았습니다.십진수의 경우,
z + 10y + 100x입니다.각 숫자에 가중치를 곱하고 그 결과를 합산합니다.가중치의 명백한 패턴은 물론 가중치가 w = b^k라는 것입니다. 여기서 b는 숫자의 밑이고 k는 숫자의 인덱스입니다.(저는 항상 오른쪽부터 숫자를 세고 가장 오른쪽 숫자의 경우 인덱스 0부터 시작합니다.마찬가지로 '첫 번째' 숫자에 관해 말할 때는 가장 오른쪽 숫자를 의미합니다.)
그만큼 이유 숫자에 대한 가중치가 이 패턴을 따르는 이유는 0부터 k까지의 숫자로 표현할 수 있는 가장 높은 숫자가 숫자 k+1로만 표현할 수 있는 가장 낮은 숫자보다 정확히 1 낮아야 하기 때문입니다.이진수에서 0111은 1000보다 1 작아야 합니다.10진수로 표현하면 099999는 100000보다 1이 작아야 합니다.
변수 기반으로 인코딩
후속 숫자 사이의 간격이 정확히 1이 되는 것이 중요한 규칙입니다.이를 실현하면 인덱스 시퀀스를 다음과 같이 표현할 수 있습니다. 가변 베이스 수.각 숫자의 기본은 해당 숫자에 대한 다양한 가능성의 양입니다.십진수의 경우 각 숫자에는 10개의 가능성이 있으며, 우리 시스템의 경우 가장 오른쪽 숫자에는 1개의 가능성이 있고 가장 왼쪽에는 n개의 가능성이 있습니다.그러나 가장 오른쪽 숫자(시퀀스의 마지막 숫자)는 항상 0이므로 생략합니다.이는 2부터 n까지의 베이스가 남았다는 뜻입니다.일반적으로 k번째 숫자는 b[k] = k + 2를 기본으로 합니다.숫자 k에 허용되는 가장 높은 값은 h[k] = b[k] - 1 = k + 1입니다.
숫자의 가중치 w[k]에 대한 규칙에서는 i = 0에서 i = 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번째(가장 오른쪽, 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} 이 코드 예제에서는 그렇지만 무엇이든 ...적절하게 색인을 생성하는 한).원래 시퀀스 {1, 2, 0, 1, 0}을 다시 가져오려면 오른쪽 끝에 0을 추가하기만 하면 됩니다(마지막 요소에는 항상 새 위치에 대한 가능성이 하나만 있다는 점을 기억하세요).
인덱스 시퀀스를 사용하여 목록 순열
아래 알고리즘을 사용하여 특정 인덱스 순서에 따라 목록을 변경할 수 있습니다.불행히도 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;
}
순열의 일반적인 표현
일반적으로 순열을 우리가 했던 것처럼 직관적이지 않게 표현하지 않고 단순히 순열이 적용된 후 각 요소의 절대 위치로 표현합니다.우리의 예는 {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(n²)입니다.순열을 여러 번 적용해야 하는 경우 먼저 이를 공통 표현으로 변환하세요.
다른 팁
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)로 내려갈 수 있습니다. Fxtbook의 10.1.1 ( "Lehmer Code (반전 테이블)", p.232ff)를 참조하십시오. http://www.jjj.de/fxt/#fxtbook빠른 방법은 10.1.1.1 절 ( "큰 배열로 계산"p.235)으로 건너 뜁니다. (GPLED, C ++) 코드는 동일한 웹 페이지에 있습니다.
각 요소는 7개의 위치 중 하나에 있을 수 있습니다.한 요소의 위치를 설명하려면 3비트가 필요합니다.즉, 모든 요소의 위치를 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
재미있어. :)
재귀 알고리즘을 사용하여 순열을 인코딩 할 수 있습니다. 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) 알고리즘이있는 경우 보너스 포인트.
정말 흥미로운 질문입니다!
모든 요소가 숫자 인 경우 문자열에서 실제 숫자로 변환하는 것을 고려할 수 있습니다. 그런 다음 순서대로 정렬하여 모든 순열을 정렬하여 배열에 배치 할 수 있습니다. 그 후, 당신은 다양한 검색 알고리즘에 열려있을 것입니다.
나는 나의 이전 대답에서 성급했지만 (삭제). 그러나 나는 실제 대답을 가지고있다. 비슷한 개념으로 제공됩니다 팩터 신적, 순열과 관련이 있습니다 (조합과 관련된 내 대답은 혼란에 대해 사과드립니다). 나는 Wikipedia 링크를 게시하는 것을 싫어하지만 잠시 전에 한 글은 어떤 이유로 든 이해할 수 없습니다. 따라서 요청하면 나중에 이것을 확장 할 수 있습니다.
이것에 대해 쓰여진 책이 있습니다. 죄송하지만 그 이름을 기억하지 못합니다 (Wikipedia에서 알게 될 것입니다). 그러나 어쨌든 나는 그 열거 시스템의 파이썬 구현을 썼습니다. 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
David Spector Springtime 소프트웨어
나는이 정확한 질문이 있었고 파이썬 솔루션을 제공 할 것이라고 생각했습니다. 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) 솔루션 인 이유입니다.
Antoine의 솔루션은 성능에 더 좋습니다.
