Permutação rápida -> número -> algoritmos de mapeamento de permutação

Eu tenho n elementos. A título de exemplo, digamos, 7 elementos, 1234567. Eu sei que existem 7! = 5040 permutações possíveis destes 7 elementos.

Eu quero um algoritmo rápido compreendendo duas funções:

f (número) mapeia um número entre 0 e 5039 para uma permutação única, e

f '(permutação) mapeia a permutação de volta para o número a partir do qual ela foi gerada.

Eu não me importo com a correspondência entre número e permutação, desde que cada permutação tenha seu próprio número exclusivo.

Então, por exemplo, posso ter funções onde

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

O algoritmo mais rápido que vem à mente é enumerar todas as permutações e criar uma tabela de pesquisa em ambas as direções, de modo que, uma vez que as tabelas sejam criadas, f (0) seria O (1) e f ('1234567') seria um pesquisa em uma string. No entanto, isso exige muita memória, principalmente quando n se torna grande.

Alguém pode propor outro algoritmo que funcione rapidamente e sem a desvantagem de memória?

Para descrever uma permutação de n elementos, você vê que para a posição em que o primeiro elemento termina, você tem n possibilidades, portanto, pode descrever isso com um número entre 0 e n-1. Para a posição em que o próximo elemento termina, você tem n-1 possibilidades restantes, então você pode descrever isso com um número entre 0 e n-2.
Et cetera até que você tenha n números.

Como exemplo para n = 5, considere a permutação que traz abcdepara caebd.

• a, o primeiro elemento, termina na segunda posição, então atribuímos a ele o índice 1 .
• btermina na quarta posição, que seria o índice 3, mas é o terceiro restante, então o atribuímos 2 .
• ctermina na primeira posição restante, que é sempre 0 .
• dtermina na última posição restante, que (de apenas duas posições restantes) é 1 .
• etermina na única posição restante, indexada em 0 .

Portanto, temos a sequência de índice {1, 2, 0, 1, 0} .

Agora você sabe que, por exemplo, em um número binário, 'xyz' significa z + 2y + 4x. Para um número decimal,
é z + 10y + 100x. Cada dígito é multiplicado por algum peso e os resultados são somados. O padrão óbvio do peso é, claro, que o peso é w = b ^ k, com b a base do número ek o índice do dígito. (Sempre contarei os dígitos da direita e começando no índice 0 para o dígito mais à direita. Da mesma forma, quando falo sobre o 'primeiro' dígito, quero dizer o mais à direita.)

A razão pela qual os pesos dos dígitos seguem esse padrão é que o número mais alto que pode ser representado pelos dígitos de 0 a k deve ser exatamente 1 menor do que o número mais baixo que pode ser representado usando apenas o dígito k + 1. Em binário, 0111 deve ser menor que 1000. Em decimal, 099999 deve ser menor que 100000.

Codificação para base variável
O espaçamento entre os números subsequentes sendo exatamente 1 é a regra importante. Percebendo isso, podemos representar nossa sequência de índice por um número de base variável . A base para cada dígito é a quantidade de possibilidades diferentes para aquele dígito. Para decimal, cada dígito tem 10 possibilidades, para nosso sistema o dígito mais à direita teria 1 possibilidade e o mais à esquerda teria n possibilidades. Mas como o dígito mais à direita (o último número em nossa sequência) é sempre 0, nós o deixamos de fora. Isso significa que ficamos com as bases 2 a n. Em geral, o k'ésimo dígito terá base b [k] = k + 2. O maior valor permitido para o dígito k é h [k] = b [k] - 1 = k + 1.

Nossa regra sobre os pesos w [k] dos dígitos requer que a soma de h [i] * w [i], onde i vai de i = 0 a i = k, seja igual a 1 * w [k + 1]. Declarado de forma recorrente, w [k + 1] = w [k] + h [k] * w [k] = w [k] * (h [k] + 1). O primeiro peso w [0] deve ser sempre 1. A partir daí, temos os seguintes valores:

k    h[k] w[k]    

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

(A relação geral w [k-1] = k! É facilmente provada por indução.)

O número que obtemos ao converter nossa sequência será então a soma de s [k] * w [k], com k variando de 0 a n-1. Aqui s [k] é o elemento k'th (mais à direita, começando em 0) da sequência. Como exemplo, tome nosso {1, 2, 0, 1, 0}, com o elemento mais à direita retirado conforme mencionado antes: {1, 2, 0, 1} . Nossa soma é 1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 37 .

Observe que se tomarmos a posição máxima para cada índice, teremos {4, 3, 2, 1, 0}, e isso se converte em 119. Uma vez que os pesos em nossa codificação numérica foram escolhidos para que não pulemos quaisquer números, todos os números de 0 a 119 são válidos. Existem precisamente 120 deles, que é n! para n = 5 em nosso exemplo, exatamente o número de permutações diferentes. Portanto, você pode ver nossos números codificados especificando completamente todas as permutações possíveis.

Decodificação de base variável A
decodificação é semelhante à conversão para binário ou decimal. O algoritmo comum é 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 nosso número de base variável:

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
}

Isso decodifica corretamente nosso 37 de volta para {1, 2, 0, 1} ( sequenceseria {1, 0, 2, 1}neste exemplo de código, mas tanto faz ... contanto que você indexe adequadamente). Precisamos apenas adicionar 0 na extremidade direita (lembre-se de que o último elemento sempre tem apenas uma possibilidade para sua nova posição) para recuperar nossa sequência original {1, 2, 0, 1, 0}.

Permutando uma lista usando uma sequência de índice
Você pode usar o algoritmo a seguir para permutar uma lista de acordo com uma sequência de índice específica. É um algoritmo O (n²), infelizmente.

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

Representação comum de permutações
Normalmente, você não representaria uma permutação de forma tão não intuitiva como fizemos, mas simplesmente pela posição absoluta de cada elemento após a aplicação da permutação. Nosso exemplo {1, 2, 0, 1, 0} para abcdeto caebdé normalmente representado por {1, 3, 0, 4, 2}. Cada índice de 0 a 4 (ou em geral, 0 a n-1) ocorre exatamente uma vez nesta representação.

Aplicar uma permutação neste formulário é 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];
}

Invertê-lo é muito semelhante:

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

Convertendo de nossa representação para a representação comum
Observe que se pegarmos nosso algoritmo para permutar uma lista usando nossa sequência de índice e aplicá-lo à permutação de identidade {0, 1, 2, ..., n-1}, obteremos o permutação inversa , representada na forma comum. ( {2, 0, 4, 1, 3} em nosso exemplo).

Para obter a pré-mutação não invertida, aplicamos o algoritmo de permutação que acabei 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];
}

Ou você pode apenas aplicar a permutação diretamente, usando o algoritmo de permutação 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]];
}

Observe que todos os algoritmos para lidar com permutações na forma comum são O (n), enquanto a aplicação de uma permutação em nossa forma é O (n²). Se você precisar aplicar uma permutação várias vezes, primeiro converta-a para a representação comum.

Encontrei um algoritmo O (n), aqui está uma breve explicação 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;
}

A complexidade pode ser reduzida a n * log (n), consulte a seção 10.1.1 ("O código Lehmer (tabela de inversão)", p.232ff) do fxtbook: http://www.jjj.de/fxt/ #fxtbook pule para a seção 10.1.1.1 ("Computação com matrizes grandes" p.235) para obter o método rápido. O código (GPLed, C ++) está na mesma página da web.

Problema resolvido. No entanto, não tenho certeza se você ainda precisa da solução após esses anos. LOL, acabei de entrar neste site, então ... Verifique minha classe de permutação Java. Você pode se basear em um índice para obter uma permutação de símbolo ou fornecer uma permutação de símbolo e obter o índice.

Aqui está minha aula de pré-mutação

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

e aqui está minha aula principal para mostrar como usar a aula.

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

Diverta-se. :)

Cada elemento pode estar em uma das sete posições. Para descrever a posição de um elemento, você precisaria de três bits. Isso significa que você pode armazenar a posição de todos os elementos em um valor de 32 bits. Isso está longe de ser eficiente, já que essa representação permitiria até que todos os elementos estivessem na mesma posição, mas acredito que o mascaramento de bits deve ser razoavelmente rápido.

No entanto, com mais de 8 posições, você precisará de algo mais bacana.

Essa é uma função integrada em 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

Você pode codificar permutações usando um algoritmo recursivo. Se uma N-permutação (alguma ordem dos números {0, .., N-1}) é da forma {x, ...} então codifique-a como x + N * a codificação do (N-1) -permutação representada por "..." nos números {0, N-1} - {x}. Parece um bocado, aqui está um 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 é O (n ^ 2). Pontos de bônus se alguém tiver um algoritmo O (n).

Que pergunta interessante!

Se todos os seus elementos forem números, você pode querer considerar convertê-los de strings em números reais. Então, você seria capaz de classificar todas as permutações, colocando-as em ordem e colocando-as em uma matriz. Depois disso, você estará aberto a qualquer um dos vários algoritmos de pesquisa que existem.

Fui precipitado na minha resposta anterior (excluída), mas tenho a resposta real. É fornecido por um conceito semelhante, o fatorádico , e está relacionado a permutações (minha resposta relacionada a combinações, peço desculpas por essa confusão). Eu odeio apenas postar links da Wikipedia, mas eu escrevi que fiz há algum tempo é ininteligível por algum motivo. Então, posso expandir isso mais tarde, se solicitado.

Existe um livro escrito sobre isso. Desculpe, mas não me lembro o nome dele (provavelmente você vai encontrá-lo na wikipedia). mas de qualquer maneira eu escrevi uma implementação python desse sistema de enumeração: http://kks.cabal.fi/Kombinaattori Parte dele está em finlandês, mas apenas copie o código e as variáveis ​​de nome ...

Eu tinha exatamente essa pergunta e pensei em fornecer minha solução Python. É 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

É muito simples; depois de gerar a representação fatorádica do número, eu apenas escolho e removo os caracteres da string. Excluir da string é o motivo pelo qual esta é uma solução O (n ^ 2).

A solução de Antoine é melhor para desempenho.

Uma questão relacionada é calcular a permutação inversa, uma permutação que restaurará os vetores permutados à ordem original quando apenas a matriz de permutação for conhecida. Aqui está o código O (n) (em PHP):

// Compute the inverse of a permutation
function GetInvPerm($Perm)
    {
    $n=count($Perm);
    $InvPerm=[];
    for ($i=0; $i<$n; ++$i)
        $InvPerm[$Perm[$i]]=$i;
    return $InvPerm;
    } // GetInvPerm

David Spector Springtime Software