Chaque permutation possible d'une chaîne ou de la combinaison, y compris des caractères répétés en Java
J'ai essayé de générer une liste de tous les 4 chaîne de caractères qui peut être constitué de tout un ensemble de caractères. J'ai utilisé une fonction pour générer tous les 4 combinaison de caractères à partir d'un ensemble de caractères, mais chaque personnage est seulement utilisé une fois. J'ai besoin de toutes les combinaisons possibles à l'aide d'un jeu de caractères par exemple:
String[] elements = {"a", "b", "c", "1", "2", "3"};
int[] indices;
CombinationGenerator x = new CombinationGenerator (elements.length, 4);
StringBuffer combination;
while (x.hasMore ()) {
combination = new StringBuffer ();
indices = x.getNext ();
for (int i = 0; i < indices.length; i++) {
combination.append (elements[indices[i]]);
}
System.out.println (combination.toString ());
}
À l'aide de la CombinationGenerator classe de ici,
ce sera le retour de tous unique de 4 combinaison de caractères tels que:
'abcd' , 'abc1', 'acb2', 'acb1'
Mais, je veux que chaque chaîne possible qui pourrait être créé en utilisant les caractères indiqués. Par exemple:
'aaaa', 'aaab', 'abc1', 'aac1', '11c2'
J'ai essayé tous les récursive et permutation méthode que j'ai été en mesure de trouver ou de trouver mais je suis perplexe sur l'obtention de plus qu'à générer toutes les combinaisons, comme ci-dessus, puis générer toutes les permutations de chaque combinaison, mais je ne peux pas travailler sur la façon de créer un ensemble de combinaisons à l'aide des caractères répétés.
D'aide, ou même seulement de la théorie sur la façon dont il pourrait être fait serait utile.
Vous devez vous connecter pour publier un commentaire.
Vous allez avoir à être plus précis sur exactement CE que vous voulez que votre fonction pour obtenir. Il existe de nombreuses définitions différentes de "combinaisons" et vous n'avez pas précisé si vous voulez ordonné ou désordonné combinaisons.
Mathématiquement, si vous avez de n éléments et que vous voulez une LISTE de k d'entre eux (commandé avec des répétitions), qui vous donne
combinaisons. (6 ^ 4 = 1296 combinaisons dans votre exemple d'origine, ce qui est beaucoup!). Toutefois, si vous avez des éléments n et veulent un MULTISET de k d'entre eux (non ordonnée avec des répétitions), qui vous donne
combinaisons et il est beaucoup plus difficile de les énumérer.
Si k est petit, vous pouvez générer le premier avec un nombre limité de boucles for, mais cela devient lourd très vite que k augmente. Cela est fortement allusion à la nécessité d'une méthode RÉCURSIVE:
Non seulement cette méthode de générer toutes les listes, mais il va énumérer dans l'ordre. Qui est, la sortie sera
à l'aide de votre entrée. Il peut aussi générer toute la longueur des mots (être très prudent avec ce! Seulement avec des mots de longueur 8 je me suis retrouvé avec 1,679,616 combinaisons!).
Si la méthode vous trouble (c'est une méthode récursive, donc c'est un peu dur à suivre) ou si vous voulez une solution à la deuxième combinaison de problème, n'hésitez pas à demander. En outre, cette méthode est quelque peu inefficace car il recalcule les combinaisons pour toutes les sous-listes, il n'est donc pas viable pour les très longues listes. Si tu voulais vraiment l'efficacité serait de stocker le déjà calculé les tuples dans une liste globale.
Si vous voulez en Python, vous n'avez pas besoin de savoir programmer!
Récursive des solutions semble assez simple aussi:
Le code n'est ni propre ni efficace, afin de démontrer la logique.
Vous pouvez traiter vos éléments comme des chiffres. Pensez à la façon dont nous obtenons toutes les combinaisons possibles de "0" - "9" par le comptage. Commencer avec 0000, 0001, 0002, ..., 0010, 0011, etc. Utiliser le même processus, comme si vous aviez une base de 6 numéro du système (ou de base-n, où n est la longueur de votre
elements
tableau.Suppléant à travers toutes les combinaisons dans le dernier chiffre, puis avance le chiffre précédent et répétez. Lors de l'avant-dernier chiffre est passé à travers chaque élément, puis avancer le troisième à dernier chiffre, et ainsi de suite. Lorsque vous avez atteint "3333" vous avez terminé.
Votre code pourrait être quelque chose comme ceci:
Il y a d'autres façons de faire la même chose qui sont plus efficaces, comme le stockage intermédiaire 1, 2, 3-les chaînes de caractères. Il y a aussi des récursive des solutions. Mais c'est l'idée générale, et devrait être assez rapide pour la taille des données que vous utilisez aujourd'hui (vous avez un total de
6^4 = 1296
combinaisons.Voici le code python qui fait ce que vous voulez:
Espère que cette aide
Ce type d'algorithme est appelé descente récursive, dans le cas où vous n'aviez pas coché déjà.
itertools.combinations
n'est pas disponible.