Schnelle Permutation -> Zahl -> Permutations-Mapping-Algorithmen

Ich habe n Elemente. Als Beispiel nennen wir 7 Elemente, 1234567. Ich weiß, dass es 7 gibt! = 5040 Permutationen dieser 7 Elemente möglich.

Ich möchte einen schnellen Algorithmus mit zwei Funktionen:

f (Zahl) ordnet eine Zahl zwischen 0 und 5039 einer eindeutigen Permutation zu, und

f '(Permutation) ordnet die Permutation der Zahl zu, aus der sie generiert wurde.

Die Entsprechung zwischen Nummer und Permutation ist mir egal, vorausgesetzt, jede Permutation hat ihre eigene eindeutige Nummer.

So könnte ich zum Beispiel Funktionen haben, bei denen

f(0) = '1234567'
f'('1234567') = 0

Der schnellste Algorithmus, der mir in den Sinn kommt, besteht darin, alle Permutationen aufzulisten und eine Nachschlagetabelle in beide Richtungen zu erstellen, sodass f (0) nach dem Erstellen der Tabellen O (1) und f ('1234567') a ist Suche auf einer Zeichenfolge. Dies ist jedoch speicherhungrig, insbesondere wenn n groß wird.

Kann jemand einen anderen Algorithmus vorschlagen, der schnell und ohne den Speichernachteil funktioniert?

Um eine Permutation von n Elementen zu beschreiben, sehen Sie, dass Sie für die Position, an der das erste Element endet, n Möglichkeiten haben, sodass Sie dies mit einer Zahl zwischen 0 und n-1 beschreiben können. Für die Position, an der das nächste Element landet, haben Sie n-1 verbleibende Möglichkeiten, sodass Sie dies mit einer Zahl zwischen 0 und n-2 beschreiben können.
Und so weiter, bis Sie n Zahlen haben.

Betrachten Sie als Beispiel für n = 5 die Permutation, die abcdezu bringt caebd.

• aDas erste Element landet an der zweiten Position, daher weisen wir ihm Index 1 zu .
• blandet an der vierten Position, die Index 3 wäre, aber es ist die dritte verbleibende Position, also weisen wir sie 2 zu .
• clandet an der ersten verbleibenden Position, die immer 0 ist .
• dendet an der letzten verbleibenden Position, die (von nur zwei verbleibenden Positionen) 1 ist .
• elandet an der einzigen verbleibenden Position, indiziert bei 0 .

Wir haben also die Indexsequenz {1, 2, 0, 1, 0} .

Jetzt wissen Sie, dass zum Beispiel in einer Binärzahl 'xyz' z + 2y + 4x bedeutet. Für eine Dezimalzahl ist
es z + 10y + 100x. Jede Ziffer wird mit einem gewissen Gewicht multipliziert und die Ergebnisse werden summiert. Das offensichtliche Muster im Gewicht ist natürlich, dass das Gewicht w = b ^ k ist, wobei b die Basis der Zahl und k der Index der Ziffer ist. (Ich zähle immer die Ziffern von rechts und beginne bei Index 0 für die am weitesten rechts stehende Ziffer. Wenn ich über die 'erste' Ziffer spreche, meine ich auch die am weitesten rechts stehende.)

Der Grund, warum die Gewichte für Ziffern diesem Muster folgen, ist, dass die höchste Zahl, die durch die Ziffern von 0 bis k dargestellt werden kann, genau 1 niedriger sein muss als die niedrigste Zahl, die nur durch Verwendung der Ziffer k + 1 dargestellt werden kann. In der Binärdatei muss 0111 eins niedriger als 1000 sein. In der Dezimalzahl muss 099999 eins niedriger als 100000 sein.

Codierung auf Variablenbasis
Der Abstand zwischen nachfolgenden Zahlen von genau 1 ist die wichtige Regel. Wenn wir dies erkennen, können wir unsere Indexsequenz durch eine Zahl mit variabler Basis darstellen . Die Basis für jede Ziffer ist die Anzahl der verschiedenen Möglichkeiten für diese Ziffer. Für die Dezimalstelle hat jede Ziffer 10 Möglichkeiten, für unser System hätte die Ziffer ganz rechts 1 Möglichkeit und die Ziffer ganz links n Möglichkeiten. Da die am weitesten rechts stehende Ziffer (die letzte Zahl in unserer Sequenz) immer 0 ist, lassen wir sie weg. Das heißt, wir haben die Basen 2 bis n. Im Allgemeinen hat die k'te Ziffer die Basis b [k] = k + 2. Der höchste zulässige Wert für die Ziffer k 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 = 0 nach i = k geht, gleich 1 * w [k + 1] ist. Wiederholt ausgedrückt ist w [k + 1] = w [k] + h [k] * w [k] = w [k] * (h [k] + 1). Das erste Gewicht w [0] sollte immer 1 sein. Von dort aus haben wir folgende 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! Kann leicht durch Induktion bewiesen werden.)

Die Zahl, die wir durch Konvertieren unserer Sequenz erhalten, ist dann die Summe von s [k] * w [k], wobei k von 0 bis n-1 läuft. Hier ist s [k] das k'te (ganz rechts, beginnend bei 0) Element der Sequenz. Nehmen Sie als Beispiel unser {1, 2, 0, 1, 0}, wobei das Element ganz rechts wie oben erwähnt entfernt wurde: {1, 2, 0, 1} . Unsere Summe ist 1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 37 .

Beachten Sie, dass wir, wenn wir die maximale Position für jeden Index einnehmen, {4, 3, 2, 1, 0} haben und dies in 119 konvertiert. Da die Gewichte in unserer Zahlencodierung so gewählt wurden, dass wir nicht überspringen beliebige Zahlen, alle Zahlen 0 bis 119 sind gültig. Es gibt genau 120 davon, was n ist! für n = 5 in unserem Beispiel genau die Anzahl der verschiedenen Permutationen. So können Sie sehen, dass unsere codierten Zahlen alle möglichen Permutationen vollständig spezifizieren.

Dekodierung von variabler Basis Die
Dekodierung ähnelt der Konvertierung in binär oder dezimal. Der übliche Algorithmus ist folgender:

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 variable Basisnummer:

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
}

Dies dekodiert unsere 37 korrekt zurück zu {1, 2, 0, 1} ( sequencewäre {1, 0, 2, 1}in diesem Codebeispiel, aber was auch immer ... solange Sie entsprechend indizieren). Wir müssen nur 0 am rechten Ende hinzufügen (denken Sie daran, dass das letzte Element immer nur eine Möglichkeit für seine neue Position hat), um unsere ursprüngliche Sequenz {1, 2, 0, 1, 0} wiederherzustellen.

Permutieren einer Liste mithilfe einer Indexsequenz Mit
dem folgenden Algorithmus können Sie eine Liste gemäß einer bestimmten Indexsequenz permutieren. Es ist leider ein O (n²) -Algorithmus.

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;
}

Allgemeine Darstellung von Permutationen
Normalerweise würden Sie eine Permutation nicht so intuitiv darstellen wie bisher, sondern einfach durch die absolute Position jedes Elements nach dem Anwenden der Permutation. Unser Beispiel {1, 2, 0, 1, 0} für abcdebis caebdwird normalerweise durch {1, 3, 0, 4, 2} dargestellt. Jeder Index von 0 bis 4 (oder im Allgemeinen 0 bis n-1) kommt in dieser Darstellung genau einmal vor.

Das Anwenden einer Permutation in dieser Form 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];
}

Das Umkehren ist sehr ähnlich:

for (int i = 0; i < n; i++)
{
    list[i] = permuted[permutation[i]];
}

Konvertieren von unserer Darstellung in die allgemeine Darstellung
Beachten Sie, dass wir die erhalten, wenn wir unseren Algorithmus verwenden, um eine Liste mithilfe unserer Indexsequenz zu permutieren und sie auf die Identitätspermutation {0, 1, 2, ..., n-1} anzuwenden inverse Permutation, dargestellt in der gemeinsamen Form. ( {2, 0, 4, 1, 3} in unserem Beispiel).

Um die nicht invertierte Prämutation zu erhalten, wenden wir den gerade gezeigten Permutationsalgorithmus an:

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 die Permutation einfach direkt anwenden, indem Sie den inversen Permutationsalgorithmus verwenden:

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 den Umgang mit Permutationen in der gemeinsamen Form O (n) sind, während das Anwenden einer Permutation in unserer Form O (n²) ist. Wenn Sie eine Permutation mehrmals anwenden müssen, konvertieren Sie sie zuerst in die allgemeine Darstellung.

Ich habe einen 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 kann auf n * log (n) reduziert werden, siehe Abschnitt 10.1.1 ("Der Lehmer-Code (Inversionstabelle)", S.232ff) des fxtbooks: http://www.jjj.de/fxt/ #fxtbook Fahren Sie mit Abschnitt 10.1.1.1 ("Berechnung mit großen Arrays", S. 235) für die schnelle Methode fort. Der (GPLed, C ++) Code befindet sich auf derselben Webseite.

Problem gelöst. Ich bin mir jedoch nicht sicher, ob Sie die Lösung nach diesen Jahren noch benötigen. LOL, ich trete gerade dieser Site bei, also ... Überprüfen Sie meine Java-Permutationsklasse. Sie können auf einem Index basieren, um eine Symbolpermutation zu erhalten, oder eine Symbolpermutation angeben und dann den Index abrufen.

Hier ist meine Prämutationsklasse

/**
 ****************************************************************************************************************
 * Copyright 2015 Fred Pang [email protected]
 ****************************************************************************************************************
 * A complete list of Permutation base on an index.
 * Algorithm is invented and implemented by Fred Pang [email protected]
 * 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.   [email protected]
     *
     * *****************************************************************************************************************
     */
    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, um zu zeigen, wie man die Klasse benutzt.

/*
 * 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

Habe Spaß. :) :)

Jedes Element kann sich an einer von sieben Positionen befinden. Um die Position eines Elements zu beschreiben, benötigen Sie drei Bits. Das heißt, Sie können die Position aller Elemente in einem 32-Bit-Wert speichern. Das ist alles andere als effizient, da diese Darstellung sogar ermöglichen würde, dass sich alle Elemente an derselben Position befinden, aber ich glaube, dass die Bitmaskierung relativ schnell sein sollte.

Bei mehr als 8 Positionen benötigen Sie jedoch etwas raffinierteres.

Dies ist zufällig eine in J integrierte Funktion :

   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

Sie können Permutationen mit einem rekursiven Algorithmus codieren. Wenn eine N-Permutation (eine Reihenfolge der Zahlen {0, .., N-1}) die Form {x, ...} hat, codiere sie als x + N * die Codierung von (N-1) -Permutation dargestellt durch "..." auf den Zahlen {0, N-1} - {x}. Klingt nach einem Schluck, hier ist ein 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 einen O (n) -Algorithmus hat.

Was für eine interessante Frage!

Wenn alle Ihre Elemente Zahlen sind, können Sie sie von Zeichenfolgen in tatsächliche Zahlen konvertieren. Dann können Sie alle Permutationen sortieren, indem Sie sie in die richtige Reihenfolge bringen und in einem Array platzieren. Danach sind Sie offen für die verschiedenen Suchalgorithmen.

Ich war in meiner vorherigen Antwort voreilig (gelöscht), aber ich habe die eigentliche Antwort. Es wird von einem ähnlichen Konzept bereitgestellt, dem Faktoradischen , und bezieht sich auf Permutationen (meine Antwort bezog sich auf Kombinationen, ich entschuldige mich für diese Verwirrung). Ich hasse es, nur Wikipedia-Links zu posten, aber ich schreibe, dass ich es vor einiger Zeit getan habe, ist aus irgendeinem Grund unverständlich. Daher kann ich dies später auf Anfrage erweitern.

Es gibt ein Buch darüber geschrieben. Entschuldigung, aber ich erinnere mich nicht an den Namen (Sie werden ihn höchstwahrscheinlich aus Wikipedia finden). Trotzdem habe ich eine Python-Implementierung dieses Aufzählungssystems geschrieben: http://kks.cabal.fi/Kombinaattori Einiges davon ist auf Finnisch, aber kopieren Sie einfach den Code und die Namensvariablen ...

Ich hatte genau diese Frage und dachte, ich würde meine Python-Lösung bereitstellen. 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 einfach; Nachdem ich die faktoradische Darstellung der Zahl generiert habe, wähle ich einfach die Zeichen aus der Zeichenfolge aus und entferne sie. Das Löschen aus der Zeichenfolge ist der Grund, warum dies eine O (n ^ 2) -Lösung ist.

Die Lösung von Antoine ist besser für die Leistung.

Eine verwandte Frage ist die Berechnung der inversen Permutation, eine Permutation, die permutierte Vektoren in der ursprünglichen Reihenfolge wiederherstellt, wenn nur das Permutationsarray bekannt ist. Hier ist der 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ühlingssoftware