Comment obtenir le tableau 2D de combinaisons possibles

Vous pouvez parcourir les combinaisons une à une comme sur des roulettes par l'utilisation d'un tableau pour enregistrer la taille de chaque intérieur tableau, et un compteur de tableau qui garde la trace de membre à l'utilisation de chaque intérieur du tableau. Quelque chose comme cette méthode:

/**
* Produce a List<String> which contains every combination which can be
* made by taking one String from each inner String array within the
* provided two-dimensional String array.
* @param twoDimStringArray a two-dimensional String array which contains
* String arrays of variable length.
* @return a List which contains every String which can be formed by taking
* one String from each String array within the specified two-dimensional
* array.
*/
public static List<String> combinations(String[][] twoDimStringArray) {
//keep track of the size of each inner String array
int sizeArray[] = new int[twoDimStringArray.length];
//keep track of the index of each inner String array which will be used
//to make the next combination
int counterArray[] = new int[twoDimStringArray.length];
//Discover the size of each inner array and populate sizeArray.
//Also calculate the total number of combinations possible using the
//inner String array sizes.
int totalCombinationCount = 1;
for(int i = 0; i < twoDimStringArray.length; ++i) {
sizeArray[i] = twoDimStringArray[i].length;
totalCombinationCount *= twoDimStringArray[i].length;
}
//Store the combinations in a List of String objects
List<String> combinationList = new ArrayList<String>(totalCombinationCount);
StringBuilder sb;  //more efficient than String for concatenation
for (int countdown = totalCombinationCount; countdown > 0; --countdown) {
//Run through the inner arrays, grabbing the member from the index
//specified by the counterArray for each inner array, and build a
//combination string.
sb = new StringBuilder();
for(int i = 0; i < twoDimStringArray.length; ++i) {
sb.append(twoDimStringArray[i][counterArray[i]]);
}
combinationList.add(sb.toString());  //add new combination to list
//Now we need to increment the counterArray so that the next
//combination is taken on the next iteration of this loop.
for(int incIndex = twoDimStringArray.length - 1; incIndex >= 0; --incIndex) {
if(counterArray[incIndex] + 1 < sizeArray[incIndex]) {
++counterArray[incIndex];
//None of the indices of higher significance need to be
//incremented, so jump out of this for loop at this point.
break;
}
//The index at this position is at its max value, so zero it
//and continue this loop to increment the index which is more
//significant than this one.
counterArray[incIndex] = 0;
}
}
return combinationList;
}

Comment la méthode fonctionne

Si vous imaginez que le compteur de tableau, d'être comme une horloge numérique la lecture alors que la première Chaîne combinaison voit le compteur de tableau à tous les zéros, de sorte que la première Chaîne est faite par prendre le zéro de l'élément (premier membre de chaque intérieur tableau.

Pour obtenir la combinaison suivante le compteur de tableau est incrémenté de un. Donc, la moins significative, de l'index de compteur est augmenté de un. Si ce qui provoque sa valeur à devenir égale à la longueur de l'intérieur de la matrice, il représente alors l'index est mis à zéro, et le prochain indice d'une plus grande importance est accrue. Séparé de la taille de la matrice de magasins de la longueur de chaque intérieur tableau, de sorte que le compteur de boucle de tableau sait quand un indice a atteint son maximum.

Par exemple, si la taille de la matrice a:

[3][3][2][1]

et le compteur de tableau a:

[0][2][1][0]

puis l'incrément ferait le moins significatif (le plus à droite) indice égal à 1, ce qui est sa valeur maximale. De sorte que l'index sera remis à zéro et le prochain indice de plus grande importance (le deuxième à partir de la droite) augmente de 2. Mais c'est aussi le maximum de l'indice, donc il s'est mis à zéro, et nous nous dirigeons vers le prochain indice de la plus grande importance. Qu'est accrue de trois, ce qui est sa valeur maximale, donc il s'est mis à zéro, et nous nous dirigeons vers le plus significatif (le plus à gauche) de l'indice. Qui se fait augmenté à 1, ce qui est inférieur au maximum de sorte que le compteur incrémenté tableau devient:

[1][0][0][0]

Qui signifie que le prochain Chaîne de combinaison est faite en prenant le second membre de la première intérieure de tableau, et le premier membre de la cours des trois prochaines intérieur des tableaux.

Avertissements et notes

J'ai écrit ce juste maintenant en une quarantaine de minutes, et c'est la moitié d'une heure du matin, ce qui signifie que, même s'il semble faire exactement ce qui est nécessaire, il y a très probablement des bugs ou des morceaux de code qui pourrait être optimisé. Assurez-vous donc de l'unité de la tester à fond si sa performance est critique.

Remarque qu'elle retourne une Liste plutôt qu'un tableau de Chaîne parce que je pense que Java Collections sont infiniment préférable à l'utilisation de tableaux dans la plupart des cas. Aussi, si vous avez besoin d'un jeu de résultats avec pas de doublons, vous pouvez simplement modifier la Liste pour un Jeu qui va automatiquement supprimer les doublons et vous laisse avec un ensemble unique.

Si vous avez vraiment besoin le résultat sous la forme d'un tableau de Chaîne, n'oubliez pas que vous pouvez utiliser le List<String>.toArray(String[]) méthode pour convertir simplement de la Liste retournée à ce que vous avez besoin.

OriginalL'auteur Bobulous

Devrait être simple à faire avec la récursivité.

Permettez-moi de reformuler un peu, de sorte que la terminologie est moins déroutant.

Nous appellerons String[] Liste des jetons, qui est une liste de Jetons

Vous disposez maintenant d'une Liste de Liste de jetons, vous voulez obtenir un Jeton de chaque Liste de jetons disponibles, et de trouver toutes les combinaisons.

Ce que vous devez faire est, donné une liste de TokenList

• Si la Liste est de n'avoir qu'un TokenList, le contenu de la Liste de jetons est lui-même toutes les combinaisons
• Les autres, faire une liste de sous-en excluant le premier élément de la Liste, et de trouver toutes les combinaisons de sous-liste. Lorsque vous avez les combinaisons, la réponse est tout simplement de la boucle par le biais de votre première liste de jetons, et de générer toutes les combinaisons à l'aide de chaque jeton dans la liste des jetons, et le résultat de combinaisons.

Je suis seulement de donner un pseudo code:

List<String> allCombinations(List<TokenList> listOfTokenList) {
if (length of strings == 1) {
return strings[0];
}
List<String> subListCombinations 
= allCombination(listOfTokenList.subList(1));  //sublist from index 1 to the end
List<String> result;
for each (token in listOfTokenList[0]) {
for each (s in subListCombination) {
result.add(token + s);
}
}
return result;
}

OriginalL'auteur Adrian Shum

En Python, on utilise itertools.du produit et de l'argument de déballage (appliquer)

>>> import itertools
>>> S=[['1','2','3'],['A','B'],['!']]
>>> ["".join(x) for x in itertools.product(*S)]
['1A!', '1B!', '2A!', '2B!', '3A!', '3B!']

OriginalL'auteur Larry Stewart