Permutation rapide -> nombre -> algorithmes de cartographie de permutation

J'ai n éléments. À titre d'exemple, disons, 7 éléments, 1234567. Je sais qu'il y en a 7! = 5040 permutations possibles de ces 7 éléments.

Je veux un algorithme rapide comprenant deux fonctions:

f (nombre) associe un nombre entre 0 et 5039 à une permutation unique, et

f '(permutation) associe la permutation au nombre à partir duquel elle a été générée.

Je me fiche de la correspondance entre le nombre et la permutation, à condition que chaque permutation ait son propre numéro unique.

Ainsi, par exemple, je pourrais avoir des fonctions où

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

L'algorithme le plus rapide qui me vient à l'esprit est d'énumérer toutes les permutations et de créer une table de recherche dans les deux sens, de sorte qu'une fois les tables créées, f (0) serait O (1) et f ('1234567') serait un recherche sur une chaîne. Cependant, cela demande de la mémoire, en particulier lorsque n devient grand.

Quelqu'un peut-il proposer un autre algorithme qui fonctionnerait rapidement et sans inconvénient de mémoire?

Pour décrire une permutation de n éléments, vous voyez que pour la position à laquelle le premier élément se termine, vous avez n possibilités, vous pouvez donc le décrire avec un nombre compris entre 0 et n-1. Pour la position à laquelle se termine l'élément suivant, vous avez n-1 possibilités restantes, vous pouvez donc la décrire avec un nombre compris entre 0 et n-2.
Et cetera jusqu'à ce que vous ayez n nombres.

À titre d'exemple pour n = 5, considérons la permutation qui conduit abcdeà caebd.

• a, le premier élément, se termine à la deuxième position, nous lui attribuons donc l'indice 1 .
• bfinit à la quatrième position, qui serait l'indice 3, mais c'est la troisième qui reste, donc nous lui attribuons 2 .
• cse termine à la première position restante, qui est toujours 0 .
• dse termine à la dernière position restante, qui (sur seulement deux positions restantes) est 1 .
• ese retrouve à la seule position restante, indexée à 0 .

Nous avons donc la séquence d'index {1, 2, 0, 1, 0} .

Vous savez maintenant que par exemple dans un nombre binaire, «xyz» signifie z + 2y + 4x. Pour un nombre décimal,
c'est z + 10y + 100x. Chaque chiffre est multiplié par un poids et les résultats sont additionnés. Le modèle évident dans le poids est bien sûr que le poids est w = b ^ k, avec b la base du nombre et k l'indice du chiffre. (Je compterai toujours les chiffres à partir de la droite et en commençant à l'index 0 pour le chiffre le plus à droite. De même, quand je parle du «premier» chiffre, je veux dire le plus à droite.)

La raison pour laquelle les pondérations des chiffres suivent ce modèle est que le nombre le plus élevé qui peut être représenté par les chiffres de 0 à k doit être exactement 1 inférieur au nombre le plus bas qui peut être représenté en utilisant uniquement le chiffre k + 1. En binaire, 0111 doit être un inférieur à 1000. En décimal, 099999 doit être un inférieur à 100000.

Encodage en base variable
L'espacement entre les nombres suivants étant exactement de 1 est la règle importante. En réalisant cela, nous pouvons représenter notre séquence d'index par un nombre à base variable . La base de chaque chiffre correspond au nombre de possibilités différentes pour ce chiffre. Pour la décimale, chaque chiffre a 10 possibilités, pour notre système le chiffre le plus à droite aurait 1 possibilité et le plus à gauche aurait n possibilités. Mais comme le chiffre le plus à droite (le dernier nombre de notre séquence) est toujours 0, nous l'oublions. Cela signifie qu'il nous reste les bases 2 à n. En général, le kème chiffre aura la base b [k] = k + 2. La valeur la plus élevée autorisée pour le chiffre k est h [k] = b [k] - 1 = k + 1.

Notre règle sur les poids w [k] des chiffres exige que la somme de h [i] * w [i], où i va de i = 0 à i = k, soit égale à 1 * w [k + 1]. En termes récurrents, w [k + 1] = w [k] + h [k] * w [k] = w [k] * (h [k] + 1). Le premier poids w [0] doit toujours être 1. À partir de là, nous avons les valeurs suivantes:

k    h[k] w[k]    

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

(La relation générale w [k-1] = k! Est facilement prouvée par récurrence.)

Le nombre que nous obtenons en convertissant notre séquence sera alors la somme de s [k] * w [k], avec k allant de 0 à n-1. Ici, s [k] est le k'e élément (le plus à droite, commençant à 0) de la séquence. À titre d'exemple, prenons notre {1, 2, 0, 1, 0}, avec l'élément le plus à droite retiré comme mentionné précédemment: {1, 2, 0, 1} . Notre somme est 1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 37 .

Notez que si nous prenons la position maximale pour chaque index, nous aurions {4, 3, 2, 1, 0}, et cela se convertit en 119. Puisque les poids de notre encodage numérique ont été choisis de manière à ne pas sauter tous les nombres, tous les nombres de 0 à 119 sont valides. Il y en a précisément 120, soit n! pour n = 5 dans notre exemple, précisément le nombre de permutations différentes. Ainsi, vous pouvez voir nos nombres encodés spécifier complètement toutes les permutations possibles.

Décodage à partir de la base de variables Le
décodage est similaire à la conversion en binaire ou décimal. L'algorithme commun est le suivant:

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

Pour notre numéro à 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
}

Cela décode correctement nos 37 en {1, 2, 0, 1} (ce sequenceserait {1, 0, 2, 1}dans cet exemple de code, mais peu importe ... tant que vous indexez correctement). Il suffit d'ajouter 0 à l'extrémité droite (rappelez-vous que le dernier élément n'a toujours qu'une seule possibilité pour sa nouvelle position) pour récupérer notre séquence d'origine {1, 2, 0, 1, 0}.

Permutation d'une liste à l'aide d'une séquence d'index
Vous pouvez utiliser l'algorithme ci-dessous pour permuter une liste en fonction d'une séquence d'index spécifique. C'est un algorithme O (n²), malheureusement.

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

Représentation commune des permutations
Normalement, vous ne représenteriez pas une permutation de manière aussi imprudente que nous l'avons fait, mais simplement par la position absolue de chaque élément après l'application de la permutation. Notre exemple {1, 2, 0, 1, 0} pour abcdeto caebdest normalement représenté par {1, 3, 0, 4, 2}. Chaque indice de 0 à 4 (ou en général de 0 à n-1) apparaît exactement une fois dans cette représentation.

L'application d'une permutation sous cette forme est facile:

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

L'inverser est très similaire:

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

Conversion de notre représentation à la représentation commune
Notez que si nous prenons notre algorithme pour permuter une liste en utilisant notre séquence d'index, et l'appliquons à la permutation d'identité {0, 1, 2, ..., n-1}, nous obtenons le permutation inverse , représentée sous la forme courante. ( {2, 0, 4, 1, 3} dans notre exemple).

Pour obtenir la prémutation non inversée, nous appliquons l'algorithme de permutation que je viens de montrer:

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 vous pouvez simplement appliquer la permutation directement, en utilisant l'algorithme de permutation inverse:

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

Notez que tous les algorithmes pour traiter les permutations sous la forme courante sont O (n), tandis que l'application d'une permutation sous notre forme est O (n²). Si vous devez appliquer une permutation plusieurs fois, convertissez-la d'abord en représentation commune.

J'ai trouvé un algorithme O (n), voici une brève explication 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 complexité peut être ramenée à n * log (n), voir section 10.1.1 ("Le code Lehmer (table d'inversion)", p.232ff) du fxtbook: http://www.jjj.de/fxt/ #fxtbook passez à la section 10.1.1.1 ("Calcul avec de grands tableaux" p.235) pour la méthode rapide. Le code (GPL, C ++) se trouve sur la même page Web.

Problème résolu. Cependant, je ne suis pas sûr que vous ayez encore besoin de la solution après ces années. LOL, je viens de rejoindre ce site, alors ... Vérifiez ma classe de permutation Java. Vous pouvez vous baser sur un index pour obtenir une permutation de symbole, ou donner une permutation de symbole puis obtenir l'index.

Voici ma classe de prémutation

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

et voici ma classe principale pour montrer comment utiliser la classe.

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

S'amuser. :)

Chaque élément peut être dans l'une des sept positions. Pour décrire la position d'un élément, vous auriez besoin de trois bits. Cela signifie que vous pouvez stocker la position de tous les éléments dans une valeur 32 bits. C'est loin d'être efficace, puisque cette représentation permettrait même à tous les éléments d'être dans la même position, mais je pense que le masquage de bits devrait être raisonnablement rapide.

Cependant, avec plus de 8 postes, vous aurez besoin de quelque chose de plus astucieux.

Cela se trouve être une fonction intégrée dans 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

Vous pouvez encoder des permutations à l'aide d'un algorithme récursif. Si une N-permutation (un certain ordre des nombres {0, .., N-1}) est de la forme {x, ...} alors codez-la comme x + N * le codage du (N-1) -permutation représentée par "..." sur les nombres {0, N-1} - {x}. Cela ressemble à une bouchée, voici un code:

// perm[0]..perm[n-1] must contain the numbers in {0,..,n-1} in any order.
int permToNumber(int *perm, int n) {
  // base case
  if (n == 1) return 0;

  // fix up perm[1]..perm[n-1] to be a permutation on {0,..,n-2}.
  for (int i = 1; i < n; i++) {
    if (perm[i] > perm[0]) perm[i]--;
  }

  // recursively compute
  return perm[0] + n * permToNumber(perm + 1, n - 1);
}

// number must be >=0, < n!
void numberToPerm(int number, int *perm, int n) {
  if (n == 1) {
    perm[0] = 0;
    return;
  }
  perm[0] = number % n;
  numberToPerm(number / n, perm + 1, n - 1);

  // fix up perm[1] .. perm[n-1]
  for (int i = 1; i < n; i++) {
    if (perm[i] >= perm[0]) perm[i]++;
  }
}

Cet algorithme est O (n ^ 2). Points bonus si quelqu'un a un algorithme O (n).

Quelle question intéressante!

Si tous vos éléments sont des nombres, vous pouvez envisager de les convertir de chaînes en nombres réels. Ensuite, vous pourrez trier toutes les permutations en les mettant dans l'ordre et les placer dans un tableau. Après cela, vous seriez ouvert à l'un des différents algorithmes de recherche disponibles.

J'étais précipité dans ma réponse précédente (supprimée), j'ai la réponse réelle cependant. Il est fourni par un concept similaire, la factoradique , et est lié aux permutations (ma réponse relative aux combinaisons, je m'excuse pour cette confusion). Je déteste simplement publier des liens wikipedia, mais j'ai écrit que je l'ai fait il y a quelque temps est inintelligible pour une raison quelconque. Donc, je peux développer cela plus tard si demandé.

Il y a un livre écrit à ce sujet. Désolé, mais je ne me souviens plus du nom de celui-ci (vous le trouverez très probablement sur wikipedia). mais de toute façon j'ai écrit une implémentation python de ce système d'énumération: http://kks.cabal.fi/Kombinaattori Une partie est en finnois, mais copiez simplement le code et les variables de nom ...

J'avais cette question exacte et j'ai pensé que je fournirais ma solution Python. C'est 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

C'est assez simple; après avoir généré la représentation factorielle du nombre, je viens de choisir et de supprimer les caractères de la chaîne. La suppression de la chaîne est la raison pour laquelle il s'agit d'une solution O (n ^ 2).

La solution d'Antoine est meilleure pour la performance.

Une question connexe est le calcul de la permutation inverse, une permutation qui restaurera les vecteurs permutés dans l'ordre d'origine lorsque seul le tableau de permutation est connu. Voici le code 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

Logiciel de printemps de David Spector