Schnelle Permutation -> Zahl -> Permutation Mapping-Algorithmen
https://stackoverflow.com/questions/1506078
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe n Elemente. Im Interesse eines Beispiels, sagen wir mal, 7 Elemente, 1234567. Ich weiß, es gibt 7! = 5040 Permutationen möglich diese 7 Elemente.
Ich möchte einen schnellen Algorithmus, der zwei Funktionen:
f (Anzahl) bildet eine Zahl zwischen 0 und 5039 zu einer einzigartigen Permutation und
f '(Permutation) bildet die Permutation auf die Zahl zurück, dass es aus generiert wurde.
Ich kümmere mich nicht um die Übereinstimmung zwischen Zahl und Permutation und bietet jede Permutation eine eigene Nummer hat.
So, zum Beispiel, ich könnte Funktionen haben, wo
f(0) = '1234567'
f'('1234567') = 0
Der schnellste Algorithmus, der in den Sinn kommt, ist alle Permutationen aufzuzählen und eine Lookup-Tabelle in beiden Richtungen erstellen, so dass, sobald die Tabellen erstellt werden, f (0) wäre O (1) und f ( ‚1234567‘) eine Lookup auf einer Schnur wäre. Dies ist jedoch Speicher hungrig, vor allem, wenn n groß wird.
Kann jemand einen anderen Algorithmus vorzuschlagen, die schnell funktionieren würde, und ohne den Speicher Nachteil?
Lösung
eine Permutation von n Elementen zu beschreiben, sehen Sie, dass für die Position, dass das erste Element endet an, Sie haben n Möglichkeiten, so können Sie dies beschreiben mit einer Zahl zwischen 0 und n-1. Für die Position, dass das nächste Element endet an, Sie haben n-1 verbleibenden Möglichkeiten, so können Sie dies mit einer Zahl zwischen 0 und n-2 beschreiben.
Et cetera, bis Sie n Zahlen.
Als Beispiel für n = 5, betrachtet die Permutation, die abcde bringt caebd.
-
a, das erste Element, endet an der zweiten Position nach oben, so ordnen wir es Index 1 . -
bendet an der vierten Position nach oben, der Index 3 sein würde, aber es ist die dritte bleibt, so dass wir weisen Sie 2 . -
cendet an der ersten Restposition nach oben, das ist immer 0 . -
dendet an der letzten verbleibenden Position auf, die (von nur zwei verbleibenden Positionen) ist 1 . -
eendet an der einzig verbliebene Position nach oben, indiziert bei 0 .
So wir die Indexfolge haben {1, 2, 0, 1, 0} .
Jetzt wissen Sie, dass zum Beispiel in einer binären Zahl, ‚xyz‘ bedeutet z + 2j + 4x. Für eine Dezimalzahl,
es ist z + 10Y + 100x. Jede Ziffer wird durch ein Gewicht multipliziert, und die Ergebnisse werden summiert. Die offensichtlichen Muster in dem Gewicht sind natürlich, dass das Gewicht W = b ^ k ist, wobei b die Basis der Zahl und k den Index der Ziffer. (Ich werde immer Ziffern von rechts zählen und ab Index 0 für die rechte Ziffer. Ebenso, wenn ich über die ‚erste‘ Ziffer spreche ich die ganz rechts bedeuten.)
Die Grund , warum die Gewichte für die Ziffern folgen diesem Muster ist, dass die höchste Zahl, die durch die Ziffern von 0 bis k dargestellt werden kann, muss genau 1 niedriger als die niedrigste Zahl, die durch dargestellt werden kann nur mit einstelligen k + 1. Binär 0111 ein niedriger als 1000. In dezimal sein muss, 099.999 muss eine niedriger als 100000.
Codierung auf variabler Basis
Der Abstand zwischen aufeinanderfolgenden Zahlen genau 1 zu sein, ist die wichtige Regel. Aus dieser Erkenntnis können wir unsere Indexfolge durch eine mit variabler Basiszahl repräsentieren . Die Basis für jede Ziffer ist die Menge an verschiedenen Möglichkeiten für diese Ziffer. Für jede Nachkommastelle hat 10 Möglichkeiten, für unser System würde die rechte Ziffer 1 Möglichkeit hat und die ganz links hat n Möglichkeiten werden. Da aber die letzte Ziffer (die letzte Zahl in unserer Sequenz) ist immer 0, lassen wir es aus. Das bedeutet, dass wir 2 bis n mit Basen links. Im Allgemeinen wird die k-te Ziffer Basis b hat [k] = k + 2. Der höchste Wert für k Ziffer erlaubt ist h [k] = b [k] -. 1 = k + 1
Unsere Regel über die Gewichte w [k] von Ziffern erfordert, dass die Summe von h [i] * w [i], wobei i von i bis i = k = 0 geht, ist gleich 1 * w [k + 1]. Angegeben wiederkehrend, w [k + 1] = w [k] + h [k] * w [k] = w [k] * (h [k] + 1). Das erste Gewicht w [0] sollte immer 1. Von dort aus startet, haben wir die folgenden Werte:
k h[k] w[k]
0 1 1
1 2 2
2 3 6
3 4 24
... ... ...
n-1 n n!
(Die allgemeine Beziehung w [k-1] = k! Ist leicht durch Induktion bewiesen.)
Die Zahl, die wir aus der Umwandlung unserer Sequenz erhalten dann die Summe von s sein [k] * w [k], wobei k von 0 bis n-1 läuft. Hier ist s [k] ist das k-te Element der Sequenz (am weitesten rechts, beginnend bei 0). Als Beispiel nimmt unsere {1, 2, 0, 1, 0}, mit dem am weitesten rechts stehende Elemente wie erwähnt abgestreift vor: {1, 2, 0, 1} . Unsere Summe ist 1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 37 .
Beachten Sie, dass, wenn wir die maximale Position für jeden Index nehmen, würden wir haben {4, 3, 2, 1, 0}, und dass Konvertiten zum 119. Da die Gewichte in unserer Zahl Codierung wurden so gewählt, dass wir don ‚t irgendwelche Zahlen überspringen, sind alle Zahlen von 0 bis 119 sind gültig. Es gibt genau 120 davon, das ist n! für n = 5 in diesem Beispiel genau die Anzahl der verschiedenen Permutationen. So können Sie unsere codierten Zahlen sehen vollständig alle möglichen Permutationen angeben.
Das Dekodieren von variabler Basis
Dekodierungs ähnelt binäre oder dezimale zu konvertieren. Der gemeinsame Algorithmus ist dies:
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;
}
Für unsere variabler Basiszahl:
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
}
Dieser dekodiert richtig unsere 37 zurück auf {1, 2, 0, 1} (sequence würde in diesem Codebeispiel {1, 0, 2, 1} werden, aber was auch immer ... solange man Index in angemessener Weise). Wir müssen nur 0 am rechten Ende hinzufügen (erinnern Sie das letzte Element immer nur eine Möglichkeit für seine neue Position hat) unsere ursprüngliche Sequenz zurück zu erhalten {1, 2, 0, 1, 0}.
Permutieren eine Liste einer Indexfolge mit
Sie können den folgenden Algorithmus verwenden, um eine Liste permutieren nach einer bestimmten Index-Sequenz. Es ist ein O (n²) Algorithmus, leider.
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;
}
Gemeinsame Darstellung von Permutationen
Normalerweise würden Sie nicht eine Permutation darstellen als unintuitively wie wir getan haben, sondern einfach durch die absolute Position jedes Elements nach der Permutation angewendet wird. Unser Beispiel {1, 2, 0, 1, 0} für abcde bis caebd wird normalerweise dargestellt durch {1, 3, 0, 4, 2}. Jeder Index von 0 bis 4 (oder im allgemeinen, 0 bis n-1) tritt genau einmal in dieser Darstellung.
eine Permutation in dieser Form Anwendung ist einfach:
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];
}
Invertierung es ist sehr ähnlich:
for (int i = 0; i < n; i++)
{
list[i] = permuted[permutation[i]];
}
Konvertieren von unserer Darstellung auf die gemeinsame Darstellung
Beachten Sie, dass, wenn nehmen wir unseren Algorithmus eine Liste mit unserem Index Sequenz permutieren, und es auf die Identität Permutation {0, 1, 2, ..., n-1}, erhalten wir die inverse Permutation, in der gemeinsamen Form dargestellt. ( {2, 0, 4, 1, 3} in unserem Beispiel).
Um die nichtinvertierten premutation zu erhalten, wenden wir die Permutation Algorithmus ich gerade gezeigt:
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];
}
Oder Sie können einfach die Permutation direkt anwenden, indem die inverse Permutation Algorithmus:
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]];
}
Beachten Sie, dass alle Algorithmen für die mit Permutationen in der gemeinsamen Form beschäftigt, sind O (n), während eine Permutation in unserer Form der Anwendung ist O (n²). Wenn Sie eine Permutation mehrmals anwenden müssen, zunächst wandelt es in der gemeinsamen Darstellung.
Andere Tipps
Ich habe eine O (n) Algorithmus gefunden, hier eine kurze Erklärung 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;
}
Die Komplexität n * log werden kann (n) gebracht, siehe Abschnitt 10.1.1 ( "The Lehmer Code (Inversionstabelle)", p.232ff) des fxtbook: http://www.jjj.de/fxt/#fxtbook Abschnitt 10.1.1.1 ( „Computation mit großen Arrays“ S.235) für die schnelle Methode überspringen. Die (Unterliegt der GPL, C ++) Code ist auf der Web-Seite.
Jedes Element kann in einen der sieben Positionen sein. Um die Position eines Elements zu beschreiben, würden Sie drei Bits benötigen. Das bedeutet, dass Sie die Position aller Elemente in einem 32-Bit-Wert speichern. Das ist weit davon entfernt, effizient, da diese Darstellung auch alle Elemente in der gleichen Position sein, erlauben würde, aber ich glaube, dass die Bit-Maskierung recht schnell sein sollte.
Allerdings mit mehr als 8 Positionen werden Sie etwas mehr raffinierte benötigen.
Dies geschieht, eine eingebaute Funktion in J sein:
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
Problem gelöst. Aber ich bin nicht sicher, dass Sie immer noch die Lösung, die nach diesen Jahren benötigen. LOL, ich diese Seite nur beitreten, so ... Überprüfen Sie meine Java Permutation Klasse. Sie können auf einem Index stützen ein Symbol Permutation zu bekommen, oder ein Symbol Permutation geben dann den Index erhalten.
Hier ist meine Prämutation Klasse
/**
****************************************************************************************************************
* 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
und hier ist meine Hauptklasse für das zeigt, wie die Klasse zu verwenden.
/*
* 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
Haben Sie Spaß. :)
Sie können Permutationen kodieren einen rekursiven Algorithmus. Wenn ein N-Permutation (einige Reihenfolge der Zahlen {0, .., N-1}) der Form {x, ...}, dann kodieren sie als x + N * die Codierung der (N-1) -permutation dargestellt durch "..." auf den Zahlen {0, N-1} - {x}. Klingt wie ein Mund voll, hier ist etwas Code:
// 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]++;
}
}
Dieser Algorithmus ist O (n ^ 2). Bonuspunkte, wenn jemand eine O (n) Algorithmus hat.
Was für eine interessante Frage!
Wenn alle Ihre Elemente sind Zahlen, könnte man sie von Strings tatsächlichen Zahlen zu prüfen, zu konvertieren. Dann würden Sie in der Lage sein, alle Permutationen zu sortieren, indem sie in Ordnung zu bringen, und legen Sie sie in einem Array. Danach würde man zu einem der verschiedenen Suchalgorithmen da draußen offen sein.
ich in meiner vorherigen Antwort voreilig war (gestrichen), ich aber die tatsächliche Antwort habe. Es wird von einem ähnlichen Konzept zur Verfügung gestellt, der factoradic und an Permutationen (meine Antwort zusammenhängt Kombinationen, ich entschuldige mich für diese Verwirrung). Ich hasse es nur wikipedia Links posten, aber ich writeup ich eine Weile habe vor ist aus irgendeinem Grund unverständlich. Also, ich kann später auf diesem erweitern, falls gewünscht.
Es gibt ein Buch darüber geschrieben. Sorry, aber ich erinnere mich nicht an den Namen es (Sie es ziemlich wahrscheinlich aus wikipedia finden). aber trotzdem schrieb ich eine Python-Implementierung dieser Aufzählung System: http://kks.cabal.fi/Kombinaattori Ein Teil davon ist auf Finnisch, aber nur den Code und Namen Variablen kopieren ...
Eine weitere Frage ist die Berechnung der inversen Permutation, eine Permutation, die permutierte Vektoren zu ursprüngliche Reihenfolge wiederhergestellt wird, wenn nur die Permutation Array bekannt ist. Hier ist die O (n) Code (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 Frühling Software
hatte ich genau diese Frage und dachte, ich würde meine bieten Python-Lösung. Es ist 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
Es ist ziemlich geradlinig; nachdem die factoradic Darstellung der Zahl zu erzeugen, I holen und entfernen nur die Zeichen aus der Zeichenfolge. Löschen aus der Zeichenfolge ist, warum dies eine O (n ^ 2) Lösung.
Antoine-Lösung ist besser für die Leistung.
