Szybka permutacja -> liczba -> algorytmy mapowania permutacji

Mam n elementów. Dla przykładu, powiedzmy 7 elementów 1234567. Wiem, że jest ich 7! = 5040 możliwych permutacji tych 7 elementów.

Chcę mieć szybki algorytm składający się z dwóch funkcji:

f (liczba) odwzorowuje liczbę od 0 do 5039 na unikalną permutację, a

f '(permutacja) odwzorowuje permutację z powrotem na liczbę, z której została wygenerowana.

Nie obchodzi mnie zgodność między liczbą a permutacją, pod warunkiem, że każda permutacja ma swój własny unikalny numer.

Na przykład mógłbym mieć funkcje, w których

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

Najszybszym algorytmem, jaki przychodzi na myśl, jest wyliczenie wszystkich permutacji i utworzenie tabeli przeglądowej w obu kierunkach, tak aby po utworzeniu tabel f ​​(0) było O (1) if ('1234567') było wyszukiwanie na łańcuchu. Jednak jest to głodne pamięci, szczególnie gdy n staje się duże.

Czy ktoś może zaproponować inny algorytm, który działałby szybko i bez wad pamięci?

Aby opisać permutację n elementów, widzisz, że dla pozycji, na której kończy się pierwszy element, masz n możliwości, więc możesz to opisać liczbą od 0 do n-1. Dla pozycji, na której kończy się następny element, masz jeszcze n-1 możliwości, więc możesz to opisać liczbą od 0 do n-2.
Et cetera, dopóki nie masz n liczb.

Jako przykład dla n = 5, rozważ permutację, która prowadzi abcdedo caebd.

• a, pierwszy element, kończy się na drugiej pozycji, więc przypisujemy mu indeks 1 .
• bkończy na czwartej pozycji, która byłaby indeksem 3, ale jest to trzecia pozostała pozycja, więc przypisujemy jej 2 .
• ckończy się na pierwszej pozostałej pozycji, która zawsze wynosi 0 .
• dkończy na ostatniej pozostającej pozycji, która (z tylko dwóch pozostałych pozycji) wynosi 1 .
• ekończy się na jedynej pozostałej pozycji, indeksowanej na 0 .

Mamy więc sekwencję indeksów {1, 2, 0, 1, 0} .

Teraz wiesz, że na przykład w liczbie binarnej „xyz” oznacza z + 2y + 4x. Dla liczby dziesiętnej
jest to z + 10y + 100x. Każda cyfra jest mnożona przez jakąś wagę, a wyniki są sumowane. Oczywistym wzorem w wadze jest oczywiście to, że waga wynosi w = b ^ k, gdzie b jest podstawą liczby, a k jest indeksem cyfry. (Zawsze będę liczył cyfry od prawej strony i zaczynając od indeksu 0 dla najbardziej prawej cyfry. Podobnie, gdy mówię o „pierwszej” cyfrze, mam na myśli skrajną prawą cyfrę.)

Powód dlaczego ciężary dla cyfr śledzić tego wzoru jest to, że największa liczba, które mogą być reprezentowane przez cyfry od 0 do k musi być dokładnie 1 niższy od najniższego numeru, który może być reprezentowany przez tylko za pomocą cyfr k + 1. W systemie dwójkowym 0111 musi być o jeden mniejszy niż 1000. W systemie dziesiętnym 099999 musi być o jeden mniejszy niż 100000.

Kodowanie do zmiennej o podstawie
Odstępy między kolejnymi liczbami wynoszące dokładnie 1 to ważna zasada. Zdając sobie z tego sprawę, możemy przedstawić naszą sekwencję indeksów za pomocą liczby o zmiennej podstawie . Podstawą dla każdej cyfry jest ilość różnych możliwości dla tej cyfry. Dla ułamka dziesiętnego każda cyfra ma 10 możliwości, w naszym systemie cyfra po prawej stronie miałaby 1 możliwość, a cyfra po lewej stronie miałaby n możliwości. Ale ponieważ skrajna prawa cyfra (ostatnia liczba w naszej sekwencji) zawsze wynosi 0, pomijamy ją. Oznacza to, że mamy podstawy od 2 do n. Ogólnie k-ta cyfra będzie miała podstawę b [k] = k + 2. Najwyższą dopuszczalną wartością dla cyfry k jest h [k] = b [k] - 1 = k + 1.

Nasza reguła dotycząca wag w [k] cyfr wymaga, aby suma h [i] * w [i], gdzie i przechodzi od i = 0 do i = k, była równa 1 * w [k + 1]. Podane okresowo, w [k + 1] = w [k] + h [k] * w [k] = w [k] * (h [k] + 1). Pierwsza waga w [0] powinna zawsze wynosić 1. Zaczynając od tego punktu mamy następujące wartości:

k    h[k] w[k]    

0    1    1  
1    2    2    
2    3    6    
3    4    24   
...  ...  ...
n-1  n    n!  

(Ogólną zależność w [k-1] = k! Można łatwo udowodnić za pomocą indukcji).

Liczba, którą otrzymamy z konwersji naszego ciągu będzie wówczas sumą s [k] * w [k], gdzie k biegnie od 0 do n-1. Tutaj s [k] jest k-tym (najbardziej po prawej, zaczynając od 0) elementem sekwencji. Jako przykład weźmy nasz {1, 2, 0, 1, 0}, z usuniętym skrajnym prawym elementem, jak wspomniano wcześniej: {1, 2, 0, 1} . Nasza suma to 1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 37 .

Zwróć uwagę, że jeśli weźmiemy maksymalną pozycję dla każdego indeksu, otrzymamy {4, 3, 2, 1, 0}, a to konwertuje do 119. Ponieważ wagi w naszym kodowaniu liczb zostały wybrane tak, aby nie pomijać wszystkie liczby, wszystkie liczby od 0 do 119 są prawidłowe. Jest ich dokładnie 120, czyli n! dla n = 5 w naszym przykładzie jest to dokładnie liczba różnych permutacji. Możesz więc zobaczyć nasze zakodowane liczby całkowicie określające wszystkie możliwe permutacje.

Dekodowanie na podstawie zmiennej
Dekodowanie jest podobne do konwersji do formatu binarnego lub dziesiętnego. Typowy algorytm jest następujący:

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

Dla naszego numeru o zmiennej podstawie:

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
}

To poprawnie dekoduje nasze 37 z powrotem do {1, 2, 0, 1} ( sequencebyłoby to {1, 0, 2, 1}w tym przykładzie kodu, ale cokolwiek ... o ile odpowiednio indeksujesz). Musimy tylko dodać 0 na prawym końcu (pamiętaj, że ostatni element ma zawsze tylko jedną możliwość dla swojej nowej pozycji), aby odzyskać naszą pierwotną sekwencję {1, 2, 0, 1, 0}.

Permutowanie listy przy użyciu sekwencji indeksów
Poniższy algorytm umożliwia permutowanie listy zgodnie z określoną sekwencją indeksów. Niestety jest to algorytm 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;
}

Wspólna reprezentacja permutacji
Normalnie permutacja nie jest przedstawiana tak nieintuicyjnie, jak to zrobiliśmy, ale po prostu przez bezwzględne położenie każdego elementu po zastosowaniu permutacji. Nasz przykład {1, 2, 0, 1, 0} for abcdeto caebdjest zwykle reprezentowany przez {1, 3, 0, 4, 2}. Każdy indeks od 0 do 4 (lub ogólnie od 0 do n-1) występuje dokładnie raz w tej reprezentacji.

Zastosowanie permutacji w tej formie jest łatwe:

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

Odwrócenie jest bardzo podobne:

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

Konwersja z naszej reprezentacji do wspólnej reprezentacji
Zauważ, że jeśli weźmiemy nasz algorytm do permutacji listy przy użyciu naszej sekwencji indeksów i zastosujemy ją do permutacji tożsamości {0, 1, 2, ..., n-1}, otrzymamy odwrotna permutacja, przedstawiona we wspólnej formie. ( W naszym przykładzie {2, 0, 4, 1, 3} ).

Aby uzyskać nieodwróconą premutację, stosujemy algorytm permutacji, który właśnie pokazałem:

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

Lub możesz po prostu zastosować permutację bezpośrednio, używając algorytmu odwrotnej permutacji:

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

Zauważ, że wszystkie algorytmy radzenia sobie z permutacjami we wspólnej formie to O (n), podczas gdy zastosowanie permutacji w naszej postaci to O (n²). Jeśli chcesz zastosować permutację kilka razy, najpierw przekonwertuj ją na wspólną reprezentację.

Znalazłem algorytm O (n), oto krótkie wyjaśnienie 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;
}

Złożoność można sprowadzić do n * log (n), patrz sekcja 10.1.1 ("Kod Lehmera (tabela inwersji)", str.232ff) książki fxtbook: http://www.jjj.de/fxt/ #fxtbook przejdź do sekcji 10.1.1.1 („Obliczenia z użyciem dużych tablic” s. 235), aby uzyskać informacje na temat szybkiej metody. Kod (na licencji GPL, C ++) znajduje się na tej samej stronie internetowej.

Problem rozwiązany. Jednak nie jestem pewien, czy po tych latach nadal potrzebujesz rozwiązania. LOL, właśnie dołączyłem do tej witryny, więc ... Sprawdź moją klasę permutacji Java. Możesz oprzeć się na indeksie, aby uzyskać permutację symbolu, lub podać permutację symbolu, a następnie uzyskać indeks.

Oto moja klasa premutacji

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

a oto moja klasa główna za pokazanie, jak korzystać z tej klasy.

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

Baw się dobrze. :)

Każdy element może znajdować się w jednej z siedmiu pozycji. Aby opisać położenie jednego elementu, potrzebne byłyby trzy bity. Oznacza to, że możesz przechowywać pozycje wszystkich elementów w wartości 32-bitowej. To dalekie od wydajności, ponieważ taka reprezentacja pozwoliłaby nawet wszystkim elementom znajdować się w tej samej pozycji, ale uważam, że maskowanie bitów powinno być stosunkowo szybkie.

Jednak przy więcej niż 8 pozycjach potrzebujesz czegoś fajniejszego.

Tak się składa, że ​​jest to funkcja wbudowana w 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

Możesz kodować permutacje za pomocą algorytmu rekurencyjnego. Jeśli permutacja N (pewna kolejność liczb {0, .., N-1}) ma postać {x, ...}, zakoduj ją jako x + N * kodowanie (N-1) -permutacja reprezentowana przez „...” na liczbach {0, N-1} - {x}. Brzmi jak kęs, oto kod:

// 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]++;
  }
}

Ten algorytm to O (n ^ 2). Dodatkowe punkty, jeśli ktoś ma algorytm O (n).

Co za interesujące pytanie!

Jeśli wszystkie elementy są liczbami, możesz rozważyć konwersję ich z łańcuchów na liczby rzeczywiste. Wtedy byłbyś w stanie posortować wszystkie permutacje, porządkując je i umieszczając w tablicy. Potem byłbyś otwarty na dowolny z różnych algorytmów wyszukiwania.

Moja poprzednia odpowiedź była pochopna (usunięta), ale mam prawdziwą odpowiedź. Dostarcza go podobna koncepcja, czynnikadyczny i jest powiązany z permutacjami (moja odpowiedź dotyczy kombinacji, przepraszam za to zamieszanie). Nienawidzę po prostu publikować linków do Wikipedii, ale napisałem, że napisałem jakiś czas temu, jest z jakiegoś powodu niezrozumiały. W razie potrzeby mogę to później rozwinąć.

Jest o tym napisana książka. Przepraszam, ale nie pamiętam jego nazwy (prawdopodobnie znajdziesz ją na Wikipedii). ale w każdym razie napisałem implementację w Pythonie tego systemu wyliczania: http://kks.cabal.fi/Kombinaattori Część z nich jest po fińsku, ale po prostu skopiuj zmienne kodu i nazwy ...

Miałem dokładnie to pytanie i pomyślałem, że przedstawię moje rozwiązanie w Pythonie. To jest 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

To całkiem proste; po wygenerowaniu czynnikadycznej reprezentacji liczby po prostu wybieram i usuwam znaki z ciągu. Usunięcie z ciągu jest powodem, dla którego jest to rozwiązanie O (n ^ 2).

Rozwiązanie Antoine jest lepsze pod względem wydajności.

Powiązane pytanie to obliczenie permutacji odwrotnej, permutacji, która przywróci permutowane wektory do pierwotnego porządku, gdy znana jest tylko tablica permutacji. Oto kod O (n) (w 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

Oprogramowanie David Spector Springtime