Permutación rápida -> número -> algoritmos de mapeo de permutación

Tengo n elementos. Por el bien de un ejemplo, digamos, 7 elementos, 1234567. ¡Sé que hay 7! = 5040 permutaciones posibles de estos 7 elementos.

Quiero un algoritmo rápido que comprenda dos funciones:

f (número) asigna un número entre 0 y 5039 a una permutación única, y

f '(permutación) mapea la permutación al número a partir del cual se generó.

No me importa la correspondencia entre número y permutación, siempre que cada permutación tenga su propio número único.

Entonces, por ejemplo, podría tener funciones donde

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

El algoritmo más rápido que me viene a la mente es enumerar todas las permutaciones y crear una tabla de búsqueda en ambas direcciones, de modo que, una vez creadas las tablas, f (0) sería O (1) yf ('1234567') sería un búsqueda en una cadena. Sin embargo, esto requiere mucha memoria, particularmente cuando n se vuelve grande.

¿Alguien puede proponer otro algoritmo que funcione rápidamente y sin la desventaja de la memoria?

Para describir una permutación de n elementos, ves que para la posición en la que termina el primer elemento, tienes n posibilidades, por lo que puedes describir esto con un número entre 0 y n-1. Para la posición en la que termina el siguiente elemento, tiene n-1 posibilidades restantes, por lo que puede describir esto con un número entre 0 y n-2.
Etcétera hasta que tenga n números.

Como ejemplo para n = 5, considere la permutación que trae abcdea caebd.

• a, el primer elemento, termina en la segunda posición, por lo que le asignamos el índice 1 .
• btermina en la cuarta posición, que sería el índice 3, pero es la tercera que queda, así que le asignamos 2 .
• ctermina en la primera posición restante, que siempre es 0 .
• dtermina en la última posición restante, que (de solo dos posiciones restantes) es 1 .
• etermina en la única posición restante, indexada en 0 .

Entonces tenemos la secuencia de índice {1, 2, 0, 1, 0} .

Ahora sabe que, por ejemplo, en un número binario, 'xyz' significa z + 2y + 4x. Para un número decimal,
es z + 10y + 100x. Cada dígito se multiplica por algún peso y se suman los resultados. El patrón obvio en el peso es, por supuesto, que el peso es w = b ^ k, con b la base del número yk el índice del dígito. (Siempre contaré los dígitos desde la derecha y comenzando en el índice 0 para el dígito más a la derecha. Del mismo modo, cuando hablo del 'primer' dígito, me refiero al más a la derecha).

La razón por la que los pesos de los dígitos siguen este patrón es que el número más alto que se puede representar con los dígitos del 0 al k debe ser exactamente 1 más bajo que el número más bajo que se puede representar usando solo el dígito k + 1. En binario, 0111 debe ser uno menor que 1000. En decimal, 099999 debe ser uno menor que 100000.

Codificación a base variable
La regla importante es que el espaciado entre números subsiguientes sea exactamente 1. Al darnos cuenta de esto, podemos representar nuestra secuencia de índice mediante un número de base variable . La base de cada dígito es la cantidad de posibilidades diferentes para ese dígito. Para decimal, cada dígito tiene 10 posibilidades, para nuestro sistema el dígito más a la derecha tendría 1 posibilidad y el más a la izquierda tendrá n posibilidades. Pero como el dígito más a la derecha (el último número de nuestra secuencia) es siempre 0, lo dejamos fuera. Eso significa que nos quedamos con las bases 2 an. En general, el dígito k 'tendrá la base b [k] = k + 2. El valor más alto permitido para el dígito k es h [k] = b [k] - 1 = k + 1.

Nuestra regla sobre los pesos w [k] de dígitos requiere que la suma de h [i] * w [i], donde i va de i = 0 a i = k, sea igual a 1 * w [k + 1]. Dicho de forma recurrente, w [k + 1] = w [k] + h [k] * w [k] = w [k] * (h [k] + 1). El primer peso w [0] siempre debe ser 1. A partir de ahí, tenemos los siguientes valores:

k    h[k] w[k]    

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

(La relación general w [k-1] = k! Se demuestra fácilmente por inducción).

El número que obtenemos al convertir nuestra secuencia será la suma de s [k] * w [k], con k corriendo de 0 a n-1. Aquí s [k] es el k'th (más a la derecha, comenzando en 0) elemento de la secuencia. Como ejemplo, tomemos nuestro {1, 2, 0, 1, 0}, con el elemento más a la derecha eliminado como se mencionó anteriormente: {1, 2, 0, 1} . Nuestra suma es 1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 37 .

Tenga en cuenta que si tomamos la posición máxima para cada índice, tendríamos {4, 3, 2, 1, 0}, y eso se convierte en 119. Dado que los pesos en nuestra codificación numérica se eligieron para no omitir cualquier número, todos los números del 0 al 119 son válidos. Hay precisamente 120 de estos, que es n! para n = 5 en nuestro ejemplo, precisamente el número de permutaciones diferentes. Para que pueda ver que nuestros números codificados especifican completamente todas las permutaciones posibles.

La decodificación desde la decodificación de base variable
es similar a la conversión a binario o decimal. El algoritmo común es este:

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

Para nuestro número de base variable:

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
}

Esto decodifica correctamente nuestro 37 de nuevo a {1, 2, 0, 1} ( sequenceestaría {1, 0, 2, 1}en este ejemplo de código, pero lo que sea ... siempre que indexe adecuadamente). Solo necesitamos agregar 0 en el extremo derecho (recuerde que el último elemento siempre tiene solo una posibilidad para su nueva posición) para recuperar nuestra secuencia original {1, 2, 0, 1, 0}.

Permutación de una lista usando una secuencia de índice
Puede usar el siguiente algoritmo para permutar una lista de acuerdo con una secuencia de índice específica. Es un algoritmo O (n²), desafortunadamente.

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

Representación común de permutaciones
Normalmente, no representaría una permutación tan poco intuitiva como lo hemos hecho, sino simplemente por la posición absoluta de cada elemento después de que se aplica la permutación. Nuestro ejemplo {1, 2, 0, 1, 0} para abcdea caebdnormalmente está representado por {1, 3, 0, 4, 2}. Cada índice de 0 a 4 (o en general, de 0 a n-1) ocurre exactamente una vez en esta representación.

Aplicar una permutación en esta forma es fácil:

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

Invertirlo es muy similar:

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

Conversión de nuestra representación a la representación común
Tenga en cuenta que si tomamos nuestro algoritmo para permutar una lista usando nuestra secuencia de índice y lo aplicamos a la permutación de identidad {0, 1, 2, ..., n-1}, obtenemos el permutación inversa , representada en la forma común. ( {2, 0, 4, 1, 3} en nuestro ejemplo).

Para obtener la premutación no invertida, aplicamos el algoritmo de permutación que acabo de mostrar:

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

O simplemente puede aplicar la permutación directamente, utilizando el algoritmo de permutación 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]];
}

Tenga en cuenta que todos los algoritmos para tratar las permutaciones en la forma común son O (n), mientras que aplicar una permutación en nuestra forma es O (n²). Si necesita aplicar una permutación varias veces, primero conviértala a la representación común.

Encontré un algoritmo O (n), aquí hay una breve explicación http://antoinecomeau.blogspot.ca/2014/07/mapping-between-permutations-and.html

public static int[] perm(int n, int k)
{
    int i, ind, m=k;
    int[] permuted = new int[n];
    int[] elems = new int[n];

    for(i=0;i<n;i++) elems[i]=i;

    for(i=0;i<n;i++)
    {
            ind=m%(n-i);
            m=m/(n-i);
            permuted[i]=elems[ind];
            elems[ind]=elems[n-i-1];
    }

    return permuted;
}

public static int inv(int[] perm)
{
    int i, k=0, m=1;
    int n=perm.length;
    int[] pos = new int[n];
    int[] elems = new int[n];

    for(i=0;i<n;i++) {pos[i]=i; elems[i]=i;}

    for(i=0;i<n-1;i++)
    {
            k+=m*pos[perm[i]];
            m=m*(n-i);
            pos[elems[n-i-1]]=pos[perm[i]];
            elems[pos[perm[i]]]=elems[n-i-1];
    }

    return k;
}

La complejidad se puede reducir a n * log (n), consulte la sección 10.1.1 ("El código de Lehmer (tabla de inversión)", p.232ff) del fxtbook: http://www.jjj.de/fxt/ #fxtbook pase a la sección 10.1.1.1 ("Computación con arreglos grandes" p.235) para el método rápido. El código (GPL, C ++) está en la misma página web.

Problema resuelto. Sin embargo, no estoy seguro de que sigas necesitando la solución después de estos años. LOL, me acabo de unir a este sitio, así que ... Revisa mi clase de permutación de Java. Puede basarse en un índice para obtener una permutación de símbolo, o dar una permutación de símbolo y luego obtener el índice.

Aquí está mi clase de premutación

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

y aquí está mi clase principal para mostrar cómo usar la clase.

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

Que te diviertas. :)

Cada elemento puede estar en una de siete posiciones. Para describir la posición de un elemento, necesitaría tres bits. Eso significa que puede almacenar la posición de todos los elementos en un valor de 32 bits. Eso está lejos de ser eficiente, ya que esta representación incluso permitiría que todos los elementos estén en la misma posición, pero creo que el enmascaramiento de bits debería ser razonablemente rápido.

Sin embargo, con más de 8 posiciones necesitarás algo más ingenioso.

Esto pasa a ser una función incorporada en 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

Puede codificar permutaciones utilizando un algoritmo recursivo. Si una N-permutación (algún orden de los números {0, .., N-1}) tiene la forma {x, ...} entonces codifíquela como x + N * la codificación del (N-1) -permutación representada por "..." en los números {0, N-1} - {x}. Suena como un bocado, aquí hay un código:

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

Este algoritmo es O (n ^ 2). Puntos de bonificación si alguien tiene un algoritmo O (n).

¡Qué pregunta tan interesante!

Si todos sus elementos son números, es posible que desee considerar convertirlos de cadenas en números reales. Entonces podrá ordenar todas las permutaciones colocándolas en orden y colocándolas en una matriz. Después de eso, estará abierto a cualquiera de los diversos algoritmos de búsqueda que existen.

Me apresuré en mi respuesta anterior (eliminada), aunque tengo la respuesta real. Lo proporciona un concepto similar, el factorádico , y está relacionado con las permutaciones (mi respuesta se relaciona con las combinaciones, pido disculpas por esa confusión). Odio publicar enlaces de wikipedia, pero lo que escribí hace un tiempo es ininteligible por alguna razón. Entonces, puedo ampliar esto más adelante si se solicita.

Hay un libro escrito sobre esto. Lo siento, pero no recuerdo el nombre (probablemente lo encontrará en wikipedia). pero de todos modos escribí una implementación de Python de ese sistema de enumeración: http://kks.cabal.fi/Kombinaattori Parte de ella está en finlandés, pero solo copie el código y las variables de nombre ...

Tenía esta pregunta exacta y pensé en proporcionar mi solución de Python. Es 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 bastante sencillo; después de generar la representación factorádica del número, solo selecciono y elimino los caracteres de la cadena. Eliminar de la cadena es la razón por la que esta es una solución O (n ^ 2).

La solución de Antoine es mejor para el rendimiento.

Una cuestión relacionada es calcular la permutación inversa, una permutación que restaurará los vectores permutados al orden original cuando solo se conoce la matriz de permutación. Aquí está el código O (n) (en 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

Software de primavera de David Spector