Smart moyen de générer de la permutation et de combinaison de Chaîne
String database[] = {'a', 'b', 'c'};
Je voudrais générer des chaînes de la suite de la séquence, selon database
.
a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc
aaa
...
Je ne peux que penser à un joli "factice" de la solution.
public class JavaApplication21 {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
char[] database = {'a', 'b', 'c'};
String query = "a";
StringBuilder query_sb = new StringBuilder(query);
for (int a = 0; a < database.length; a++) {
query_sb.setCharAt(0, database[a]);
query = query_sb.toString();
System.out.println(query);
}
query = "aa";
query_sb = new StringBuilder(query);
for (int a = 0; a < database.length; a++) {
query_sb.setCharAt(0, database[a]);
for (int b = 0; b < database.length; b++) {
query_sb.setCharAt(1, database[b]);
query = query_sb.toString();
System.out.println(query);
}
}
query = "aaa";
query_sb = new StringBuilder(query);
for (int a = 0; a < database.length; a++) {
query_sb.setCharAt(0, database[a]);
for (int b = 0; b < database.length; b++) {
query_sb.setCharAt(1, database[b]);
for (int c = 0; c < database.length; c++) {
query_sb.setCharAt(2, database[c]);
query = query_sb.toString();
System.out.println(query);
}
}
}
}
}
La solution est assez bête. Il n'est pas à l'échelle-mesure dans le sens que
- Ce que si j'augmente la taille de
database
? - Que faire si mon dernier ciblées imprimer la longueur de la Chaîne doivent être N?
Est-il intelligent de code, ce qui peut générer de l'échelle de mesure de permutation et de combinaison en chaîne dans un vraiment intelligent?
En Python, c'est très simple, haha.
print ''.join(query) for query in itertools.combinations_with_replacement(database, length) for length in range(1,N+1)
OriginalL'auteur Cheok Yan Cheng | 2013-11-15
Vous devez vous connecter pour publier un commentaire.
Vous devriez vérifier cette réponse: Chaque permutation possible d'une chaîne ou de la combinaison, y compris des caractères répétés en Java
Pour obtenir ce code:
Bien que la poursuite de l'amélioration de la mémoire peut être faite, puisque cette solution génère toutes les solution pour la mémoire de la première (le tableau), avant de pouvoir l'imprimer. Mais l'idée est la même, ce qui est d'utiliser l'algorithme récursif.
OriginalL'auteur justhalf
Cela sent comme compter en binaire:
Mon premier réflexe serait d'utiliser un compteur binaire comme une "image" de caractères pour générer les valeurs possibles. Cependant, il existe plusieurs merveilleux de répondre à des questions liées ici qui propose l'utilisation de la récursivité. Voir
aa
est valable de permutation.Je pense qu'au lieu d'utiliser un système binaire, il peut également être facilement fait en utilisant des assises supérieures. depuis qu'il a trois éléments, il peut être fait dans la base de 3
Pas encore évolutive... la Prochaine fois, il a quatre éléments dans
database
. Mais tu deviens de plus près...eh bien, si il a de n éléments dans sa base de données, il peut le faire dans la base de n
"s'il a de n éléments dans sa base de données, il peut le faire dans la base n" -> c'est exactement ce que l'OP a demandé. haha
OriginalL'auteur dj_segfault
Java mise en œuvre de votre permutation générateur:-
OriginalL'auteur Vikram Bhat
Ok, donc la meilleure solution pour permutations est la récursivité. Disons que vous avez eu n lettres différentes dans la chaîne. Qui permettrait de produire de n sous-problèmes, une pour chaque série de permutations en commençant par chaque lettre. Créer une méthode
permutationsWithPrefix(String thePrefix, String theString)
qui permettra de résoudre ces problèmes. Créer une autre méthodelistPermutations(String theString)
une mise en œuvre serait quelque chose commeOriginalL'auteur Jesse Nelson
je suis tombé sur cette question comme l'une des questions de l'entrevue. Voici la solution que j'ai mis en œuvre pour résoudre ce problème en utilisant la récursivité.
OriginalL'auteur DeepInJava
Pour toute personne à la recherche pour les non-récursive options, voici un exemple pour les permutations (peut facilement être adapté à
char
.numberOfAgents
est le nombre de colonnes et de l'ensemble de nombres est0
ànumberOfActions
:OriginalL'auteur BlueMoon93
OriginalL'auteur Rathina Moorthy Nataraj