permutazione veloce -> Numero -> algoritmi di mappatura permutazione
https://stackoverflow.com/questions/1506078
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Non ho n elementi. Per il bene di un esempio, diciamo, 7 elementi, 1234567. So che ci sono 7! = 5040 permutazioni possibili di questi 7 elementi.
Voglio un algoritmo veloce che comprende due funzioni:
f (numero) associa un numero compreso tra 0 e 5039 ad una permutazione unico, e
f '(permutazione) mappa la permutazione di nuovo al numero che è stato generato da.
Non mi interessa la corrispondenza fra numero e permutazione, fornendo ogni permutazione ha il proprio numero unico.
Così, per esempio, potrei avere funzioni in cui
f(0) = '1234567'
f'('1234567') = 0
L'algoritmo più veloce che viene in mente è quello di elencare tutte le permutazioni e creare una tabella di ricerca in entrambe le direzioni, in modo che, una volta che si creano le tabelle, f (0) sarebbe O (1) e f ( '1234567') sarebbe una ricerca su una stringa. Tuttavia, questa è la memoria fame, in particolare quando n diventa grande.
Chiunque può proporre un altro algoritmo che avrebbe funzionato in modo rapido e senza lo svantaggio di memoria?
Soluzione
Per descrivere una permutazione di n elementi, si vede che per la posizione che il primo elemento finisce a, si ha n possibilità, in modo da poter descrivere questo con un numero compreso tra 0 e n-1. Per la posizione che l'elemento successivo finisce in, si dispone di n-1 possibilità rimanenti, in modo da poter descrivere questo con un numero compreso tra 0 e n-2.
Et cetera fino ad avere i numeri n.
Come esempio per n = 5, si consideri la permutazione che porta a abcde caebd.
-
a, il primo elemento, finisce nella seconda posizione, in modo da assegnare ad esso index 1 . -
btermina alla quarta posizione, che sarebbe indice 3, ma è il terzo rimanente, in modo da assegnare ad esso 2 . -
ctermina alla prima posizione rimanente, che è sempre 0 . -
dfinisce l'ultima posizione rimanente, che (su due sole posizioni rimanenti) è 1 . -
efinisce nella posizione unica rimasta, indicizzati da 0 .
Così abbiamo la sequenza di indice di {1, 2, 0, 1, 0} .
Ora si sa che ad esempio in un numero binario, 'xyz' significa z + 2y + 4x. Per un numero decimale,
è z + 10Y + 100x. Ogni cifra viene moltiplicata per un certo peso, ed i risultati sono sommati. Il modello evidente nel peso è naturalmente che il peso è w = b ^ k, con b la base del numero e l'indice k della cifra. (Sarò sempre contare cifre da destra e a partire dall'indice 0 per la cifra più a destra. Allo stesso modo, quando parlo di 'prima' cifre intendo il più a destra).
motivo perché i pesi per le cifre seguono questo schema è che il maggior numero che può essere rappresentato dalle cifre da 0 a k deve essere esattamente 1 inferiore al numero minimo che può essere rappresentato da utilizzando solo cifre, k + 1. In binario, 0111 deve essere uno inferiore 1000. In decimale, 099.999 deve essere uno inferiore 100000.
Codifica alla variabile-base
La spaziatura tra i numeri successivi essendo esattamente 1 è la regola importante. Comprendendo questo, siamo in grado di rappresentare la nostra sequenza di indice da un numero variabile-base . La base di ogni cifra è la quantità di diverse possibilità per quella cifra. Per ogni cifra decimale ha 10 possibilità, per il nostro sistema la cifra più a destra avrebbe 1 possibilità e la sinistra avrà n possibilità. Ma dal momento che la cifra all'estrema destra (l'ultimo numero della nostra sequenza) è sempre 0, lo lasciamo fuori. Ciò significa che siamo lasciati con basi da 2 a n. In generale, la cifra k'th avrà base b [k] = k + 2. Il valore massimo consentito per cifre k è H [k] = b [k] -. 1 = k + 1
La nostra regola sui pesi w [k] di cifre richiede che la somma di h [i] * w [i], dove i va da i = 0 per i = k, è uguale a 1 * w [k + 1]. Detto in modo ricorrente, w [k + 1] = w [k] + h [k] * w [k] = w [k] * (h [k] + 1). Il primo peso w [0] deve essere sempre 1. A partire da lì, abbiamo i seguenti valori:
k h[k] w[k]
0 1 1
1 2 2
2 3 6
3 4 24
... ... ...
n-1 n n!
(La relazione generale w [k-1] = k! È facilmente dimostrata per induzione.)
Il numero che otteniamo da convertire la nostra sequenza sarà quindi la somma di s [k] * w [k], con k che va da 0 a n-1. Qui s [k] è la k'th (più a destra, da 0) elemento della sequenza. A titolo di esempio, prendere il nostro {1, 2, 0, 1, 0}, con l'elemento più a destra si tolse come accennato prima: {1, 2, 0, 1} . La nostra somma è 1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 37 .
Si noti che se prendiamo la posizione massima per ogni indice, avremmo {4, 3, 2, 1, 0}, e che converte in 119. Dal momento che i pesi della nostra codifica numero sono stati scelti in modo da don 't omettere i numeri, tutti i numeri da 0 a 119 sono validi. Ci sono precisamente 120 di questi, che è n! per n = 5 nel nostro esempio, precisamente il numero di differenti permutazioni. Così si può vedere i nostri numeri codificati specificano completamente tutte le possibili permutazioni.
Decodifica dalla variabile-base
Decodifica è simile alla conversione in binario o decimale. L'algoritmo comune è questa:
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;
}
Per il nostro numero variabile-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
}
Questa decodifica correttamente il nostro 37 torna a {1, 2, 0, 1} (sequence sarebbe {1, 0, 2, 1} in questo esempio di codice, ma qualunque cosa ... fino a quando si indice in modo appropriato). Abbiamo solo bisogno di aggiungere 0 alla fine a destra (ricordate l'ultimo elemento ha sempre una sola possibilità per la sua nuova posizione) per tornare la nostra sequenza originale {1, 2, 0, 1, 0}.
permutando un elenco utilizzando una sequenza di indice
È possibile utilizzare l'algoritmo di seguito per permutare un elenco in base ad una specifica sequenza di indice. Si tratta di un O (n²) algoritmo, purtroppo.
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;
}
Rappresentanza Comune di permutazioni
Normalmente non rappresenterebbe una permutazione come unintuitively come abbiamo fatto, ma semplicemente la posizione assoluta di ciascun elemento dopo la permutazione è applicato. Il nostro esempio {1, 2, 0, 1, 0} per abcde a caebd è normalmente rappresentato da {1, 3, 0, 4, 2}. Ogni indice da 0 a 4 (o, in generale, da 0 a n-1) si verifica una sola volta in questa rappresentazione.
L'applicazione di una permutazione in questa forma è semplice:
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];
}
L'inversione è molto simile:
for (int i = 0; i < n; i++)
{
list[i] = permuted[permutation[i]];
}
La conversione dalla nostra rappresentanza alla rappresentazione comune
Si noti che se prendiamo il nostro algoritmo per permutare un elenco utilizzando la nostra sequenza di indice, e applicarlo alla permutazione identità {0, 1, 2, ..., n-1}, otteniamo il inversa permutazione, rappresentata in forma comune. ( {2, 0, 4, 1, 3} nel nostro esempio).
Per ottenere il premutation non invertita, applichiamo l'algoritmo di permutazione ho appena mostrato:
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];
}
Oppure si può semplicemente applicare la permutazione direttamente, utilizzando l'algoritmo di permutazione inversa:
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]];
}
Si noti che tutti gli algoritmi per trattare con permutazioni in forma comune sono O (n), mentre si applica una permutazione il nostro modulo è O (n²). Se è necessario applicare una permutazione più volte, prima convertirlo alla rappresentazione comune.
Altri suggerimenti
Ho trovato un (n) algoritmo O, ecco una breve spiegazione 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;
}
La complessità può essere portato fino a n * log (n), vedere la sezione 10.1.1 ( "Il codice di Lehmer (tavola di inversione)", p.232ff) del fxtbook: http://www.jjj.de/fxt/#fxtbook passare alla sezione 10.1.1.1 ( "calcolo con grandi array" p.235) per il metodo veloce. L'(GPL una, C ++) il codice è sulla stessa pagina web.
Ogni elemento può essere in una delle sette posizioni. Per descrivere la posizione di un elemento, si avrebbe bisogno di tre bit. Ciò significa che è possibile memorizzare la posizione di tutti gli elementi di un valore a 32 bit. Questo è lontano da essere efficace, dal momento che tale rappresentazione sarebbe nemmeno permettere tutti gli elementi per essere nella stessa posizione, ma credo che il bit-mascheramento deve essere ragionevolmente veloce.
Tuttavia, con più di 8 posizioni avrete bisogno di qualcosa di più elegante.
Questo sembra essere una funzione incorporata nella 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
Problema risolto. Tuttavia, non sono sicuro hai ancora bisogno la soluzione dopo questi anni. LOL, ho appena entra in questo sito, in modo da ... Controllare il mio Java permutazione di classe. È possibile basare su un indice per ottenere una permutazione simbolo, o dare una permutazione simbolo quindi ottenere l'indice.
Ecco la mia classe 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
e qui è la mia classe principale di mostrare come utilizzare la classe.
/*
* 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
Buon divertimento. :)
È possibile codificare permutazioni utilizzando un algoritmo ricorsivo. Se un N-permutazione (alcune ordinamento dei numeri {0, .., N-1}) è della forma {x, ...} lo codifica come x + N * la codifica del (N-1) -permutation rappresentato da "..." sui numeri {0, N-1} - {x}. Suona come un boccone, ecco qualche codice:
// 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]++;
}
}
Questo algoritmo è O (n ^ 2). I punti di bonus se qualcuno ha una (n) algoritmo O.
Che domanda interessante!
Se tutti gli elementi sono numeri, si potrebbe prendere in considerazione la loro conversione da stringhe in numeri reali. Poi si sarebbe in grado di risolvere tutte le permutazioni dalla loro messa a punto, e metterli in un array. Dopo di che, si sarebbe aperto a qualsiasi dei vari algoritmi di ricerca là fuori.
Sono stato precipitoso nella mia risposta precedente (cancellato), io ho la risposta reale però. Esso è fornito da un concetto simile, il factoradic , ed è relativo a permutazioni (la mia risposta correlato a combinazioni, mi scuso per questo confusione). Odio postare solo link di wikipedia, ma interessante resoconto che ho fatto poco fa è incomprensibile per qualche motivo. Quindi, posso espandere su questo più tardi, se richiesto.
C'è un libro scritto su questo. Ci dispiace, ma non mi ricordo il nome di essa (lo troverete molto probabilmente da wikipedia). ma in ogni caso ho scritto un'implementazione pitone di quel sistema di enumerazione: http://kks.cabal.fi/Kombinaattori Alcuni di essi è in finlandese, ma è sufficiente copiare le variabili di codice e nome ...
Una questione collegata sta calcolando la permutazione inversa, una permutazione che ripristinerà vettori permutati ordine originale quando solo la matrice di permutazione è noto. Ecco il codice O (n) (in 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 Software
Ho avuto questa domanda esatta e ho pensato di fornire la mia soluzione Python. E '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
E 'piuttosto semplice; dopo aver generato la rappresentazione factoradic del numero, basta scegliere e rimuovere i caratteri dalla stringa. L'eliminazione dalla stringa è il motivo per cui questo è un (n ^ 2) soluzione O.
La soluzione di Antoine è migliore per le prestazioni.
