IP Girl
  1. IP Girl
  3. Permutation rapide -> nombre -> algorithmes de mappage de permutation
Intereting Posts
Définitions de macro C # dans le préprocesseur Puis-je faire défiler un ScrollView par programmation dans Android? Groovy, alternative à la construction «try-with-resources» Existe-t-il une convention de nommage pour MySQL? Quelles sont les limitations et les inconvénients de Phonegap ou HTML5 par rapport à ceux d’Android Quel algorithme peut être utilisé pour placer des rectangles de différentes tailles dans le plus petit rectangle possible de manière assez optimale? Github: Importer une twig en amont dans une fourche Comment définir mon shell par défaut sur Mac? C # 6.0 fonctionne-t-il pour .NET 4.0? Rafraîchir le fragment au rechargement Comment atsortingbuer plusieurs étiquettes à la fois dans matplotlib? Pourquoi les utilisateurs Java consumnt-ils fréquemment des exceptions en silence? Problème de conception Java: appliquez la séquence d’appels de méthode Déplacer le pointeur de twig sur une autre validation sans extraction Comment puis-je diviser plusieurs mots joints?

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

J’ai n éléments. Par 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 (number) mappe un nombre entre 0 et 5039 sur une permutation unique, et

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

Je ne me soucie pas 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 vient à l’esprit est d’énumérer toutes les permutations et de créer une table de recherche dans les deux directions, de sorte que, une fois les tables créées, f (0) serait O (1) et f (‘1234567’) serait rechercher une chaîne. Cependant, il s’agit d’une faim de mémoire, en particulier lorsque n devient grand.

Quelqu’un peut-il proposer un autre algorithme qui fonctionnerait rapidement et sans inconvénient pour la 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 décrire cela 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 amène caebd à caebd .

  • a , le premier élément, se retrouve à la deuxième position, nous lui assignons donc l’index 1 .
  • b se retrouve à la quasortingème position, qui serait l’index 3, mais c’est le troisième, donc nous l’atsortingbuons 2 .
  • c se retrouve à la première position restante, qui est toujours 0 .
  • d se retrouve à la dernière position restante, qui (sur seulement deux positions restantes) est 1 .
  • e se retrouve à la seule position restante, indexée à 0 .

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

Maintenant, vous savez que, par exemple, dans un nombre binary, «xyz» signifie z + 2y + 4x. Pour un nombre décimal,
c’est z + 10y + 100x. Chaque chiffre est multiplié par un certain poids et les résultats sont additionnés. La tendance évidente 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 compte toujours les chiffres à partir de la droite et commence à 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 poids pour les chiffres suivent ce modèle est que le nombre le plus élevé pouvant être représenté par les chiffres de 0 à k doit être exactement 1 inférieur au nombre le plus faible pouvant être représenté uniquement par le chiffre k + 1. En binary, 0111 doit être inférieur à 1000. En décimal, 099999 doit être inférieur à 100000.

Encodage à base variable
L’espacement entre les nombres suivants étant exactement 1 est la règle importante. En réalisant cela, nous pouvons représenter notre séquence d’index par un nombre de base variable . La base de chaque chiffre est la quantité de possibilités différentes pour ce chiffre. Pour les décimaux, chaque chiffre a 10 possibilités, pour notre système, le chiffre le plus à droite aura une possibilité et le plus à gauche aura n possibilités. Mais comme le chiffre le plus à droite (le dernier numéro de notre séquence) est toujours 0, nous le laissons de côté. Cela signifie que nous sums partis avec 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 concernant les poids w [k] des chiffres exige que la sum de h [i] * w [i], où i va de i = 0 à i = k, soit égale à 1 * w [k + 1]. Dit de manière récurrente, w [k + 1] = w [k] + h [k] * w [k] = w [k] * (h [k] + 1). Le premier poids w [0] devrait toujours être 1. En partant de là, nous avons les valeurs suivantes: 

 kh[k] w[k] 0 1 1 1 2 2 2 3 6 3 4 24 ... ... ... n-1 nn!

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

Le nombre obtenu en convertissant notre séquence sera alors la sum de s [k] * w [k], avec k allant de 0 à n-1. Ici, s [k] est le kième élément (le plus à droite, commençant à 0) de la séquence. Par exemple, prenons notre {1, 2, 0, 1, 0}, avec l’élément le plus à droite enlevé comme mentionné précédemment: {1, 2, 0, 1} . Notre sum est 1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 37 .

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

Décodage à partir d’une base variable
Le décodage est similaire à la conversion en binary ou en 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 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 }

Cela décode correctement notre 37 retour à {1, 2, 0, 1} (la sequence serait {1, 0, 2, 1} dans cet exemple de code, mais peu importe ... tant que vous indexez de manière appropriée). Nous avons juste besoin d'append 0 à droite (rappelez-vous que le dernier élément n'a toujours qu'une possibilité pour sa nouvelle position) pour récupérer notre séquence originale {1, 2, 0, 1, 0}.

Permuter une liste en utilisant 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 peu intuitive que possible, 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 abcde to caebd est normalement représenté par {1, 3, 0, 4, 2}. Chaque index de 0 à 4 (ou en général 0 à n-1) apparaît exactement une fois dans cette représentation.

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

Inverser c'est très similaire: 

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

Passer 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'appliquer à la permutation d'identité {0, 1, 2, ..., n-1}, nous obtenons la permutation inverse , représentée sous la forme commune . ( {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 dans la forme commune sont O (n), alors que l'application d'une permutation dans notre forme est O (n²). Si vous devez appliquer plusieurs fois une permutation, convertissez-la d'abord en représentation commune.

J’ai fait un algorithme dans O (n), vous pouvez obtenir mes fonctions ici: 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

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 (GPLed, C ++) se trouve sur la même page Web.

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

Cependant, avec plus de 8 positions, 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

Problème résolu. Cependant, je ne suis pas sûr que vous ayez toujours 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!/(nr)! * the user can input n = the number of items, * r = the number of slots for the items, * provided n >= r * and a ssortingng of single character symbols * * the program will generate all possible permutation for the condition. * * Say if n = 5, r = 3, and the ssortingng is "12345", it will generate sll 60 different permutation of the set * of 3 character ssortingngs. * * 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 ensortinges are defined, including an index. * * eg. if pass in value is 5 chose 3, and say the symbol ssortingng 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 "Ssortingng PermGetSsortingng(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 ssortingng * or the integer array corresponding to the index. * * Also notice that in the input ssortingng is "12345" of position 01234, and the output is always in accenting order * this is how the permutation is generated. * * *************************************************************************************************************** * ==== W arning ==== * *************************************************************************************************************** * * 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 ssortingng of symbol pass in when the object is created, not sure what will happen if the * ssortingng 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 Ssortingng sSymbol; // character ssortingng for symbol of each choice private Ssortingng 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, Ssortingng 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. // // ====== WARNING ====== // // 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!/(nr)! 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 ssortingng = '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 // xoooox -> in use; o -> free only 0 is being used // ss ^ 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 // ss ^ 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(Ssortingng[] args) { Permutation perm; // declear the object Ssortingng sOutSsortingng = ""; 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: "); sOutSsortingng = scanner.next(); if (sOutSsortingng.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(" ***************** FAILED *************************"); assert(true); break; } } } } } // // End of file - Main.java

S'amuser. 🙂

Vous pouvez encoder des permutations en utilisant 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 * l’encodage du (N-1) -permutation représentée par “…” sur les nombres {0, N-1} – {x}. On dirait une bouchée, voici du 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 sortinger toutes les permutations en les classant et les placer dans un tableau. Après cela, vous seriez ouvert à tous les algorithmes de recherche disponibles.

J’ai été précipité dans ma réponse précédente (supprimé), mais j’ai la réponse réelle cependant. Il est fourni par un concept similaire, le factoradique , et est lié aux permutations (ma réponse concernait les combinaisons, je m’excuse pour cette confusion). Je déteste ne publier que des liens Wikipédia, mais je ne me suis pas rendu compte de ce que j’ai fait il y a quelque temps. 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 pas du nom de celui-ci (vous le trouverez probablement à partir de wikipedia). mais de toute façon j’ai écrit une implémentation en python de ce système d’énumération: http://kks.cabal.fi/Kombinaattori .