C++ Girl
  1. C++ Girl
  3. Algorithme de permutation récursive C ++ pour les chaînes -> ne pas ignorer les doublons
Intereting Posts
Paramètres de mouvement de lissage Comment implémenter la covariance des classes de modèles en C ++? constexpr définissant un membre de données statique de type littéral déclaré const Qu’est-ce qu’un comportement indéterminé en C ++? En quoi est-ce différent du comportement indéfini? Problèmes, notamment MATLAB «engine.h» pour le code C ++ Pourquoi certaines fonctions de ne sont-elles pas dans l’espace de noms std? Quel est le moyen sûr de remplir un tableau multidimensionnel en utilisant std :: fill? éviter de spécifier des parameters de modèle redondants contenant un pointeur de fonction basé sur un modèle Déplacer le constructeur pour la classe dérivée Quand utiliser async_write_some et async_write ActiveMQ-CPP et Visual Studio 2003 Comment résoudre un appel de fonction «ambigu»? En C ++, quels sont les avantages d’utiliser des exceptions et try / catch au lieu de simplement renvoyer un code d’erreur? Une définition de fonction n’est-elle pas autorisée ici avant un jeton ‘{‘? Quand exactement l’opérateur d’incrément postfix est-il évalué dans une expression complexe?

Algorithme de permutation récursive C ++ pour les chaînes -> ne pas ignorer les doublons

Je ne parviens pas à trouver une instruction simple pour ignorer les doublons pour ce code de permutation récursif. J’ai regardé partout et ne semble trouver que des exemples en utilisant swap ou java. De ce que je comprends, je pense que je dois mettre une ligne juste après la boucle.

Je vous remercie! 

#include "genlib.h" #include "simpio.h" #include  #include  void ListPermutations(ssortingng prefix, ssortingng rest); int main() { cout << "Enter some letters to list permutations: "; string str = GetLine(); cout << endl << "The permutations are: " << endl; ListPermutations("", str); return 0; } void ListPermutations(string prefix, string rest) { if (rest == "") { cout << prefix << endl; } else { for (int i = 0; i < rest.length(); i++) { if (prefix != "" && !prefix[i]) continue; // <--- I tried adding this, but it doesn't work cout << endl<< "prefix: " << prefix << " | rest: " << rest << endl; string newPrefix = prefix + rest[i]; string newRest = rest.substr(0, i) + rest.substr(i+1); ListPermutations(newPrefix, newRest); } } }

cela devrait fonctionner: votre algorithme est bon, je n’ai ajouté qu’un test: si un caractère unique est déjà utilisé à un poste. Si oui, aucune autre permutation n’est faite car toutes les permutations avec ce caractère dans cette position sont déjà faites. 

 void ListPermutations(ssortingng prefix, ssortingng rest) { if (rest == "") { cout << prefix << endl; } else { for (int i = 0; i < rest.length(); i++) { //test if rest[i] is unique. bool found = false; for (int j = 0; j < i; j++) { if (rest[j] == rest[i]) found = true; } if(found) continue; string newPrefix = prefix + rest[i]; string newRest = rest.substr(0, i) + rest.substr(i+1); ListPermutations(newPrefix, newRest); } } }

vous pouvez également sortinger la chaîne avant d'effectuer des permutations, le résultat sera le même.

En C ++ pour générer une permutation, utilisez std :: next_permutation

Il gérera bien les entrées en double et fera le bon choix

Ignorer la disponibilité de std :: next_permutation, car votre commentaire sur la réponse précédente …

Si vous voulez générer toutes les permutations uniques , vous devrez les avoir en ordre à un moment donné. La meilleure façon de procéder consiste à les mettre tous dans un vecteur, à les sortinger, puis à supprimer les entrées adjacentes en double lors de l’impression. Mais c’est beaucoup plus lent que nécessaire.

Vous devrez commencer par sortinger votre chaîne, de sorte que des permutations identiques soient générées les unes après les autres. Ensuite, dans votre boucle For, assurez-vous de ne pas insérer de lettres en double dans “rest”. quelque chose comme: 

  char lastAdditionToPrefix = '\0'; for (int i = 0; i < rest.length(); i++) { if (rest[i] == lastAdditionToPrefix) continue; lastAdditionToPrefix = rest[i]; cout << endl<< "prefix: " << prefix << " | rest: " << rest << endl; ...

Je ne suis pas convaincu que ce changement corrigera complètement votre code, mais il est plus proche que vous ne l'êtes pour le moment. edit: ceci, plus le sorting de l'entrée dans main (), fonctionnera

Testé et fonctionne bien. L’idée est que pour chaque niveau de stack, à l’emplacement i, rappelez-vous si un personnage a déjà été à cet emplacement. 

 using namespace std; void doPermutation(vector &input, int index) { bool used[26] = {false}; if(index == input.size()) { copy(input.begin(), input.end(), ostream_iterator(cout, "") ); cout << endl; } else { int i, j; for(i =index; i < input.size(); i++ ) { if(used[ input[i]-'a'] == false) { swap(input[i], input[index]); doPermutation(input, index+1); swap(input[i], input[index]); used[input[i]-'a'] = true; } } } } void permutation(vector& input) { doPermutation(input, 0); } int main() { cout << "Hello World" << endl; const char* inp = "alla"; vector input(inp, inp + 4 ); permutation(input); return 0; }

La différence pour les algorithmes avec ou sans duplication serait lorsque vous l’échangez, assurez-vous que le caractère que vous souhaitez échanger n’a pas été échangé auparavant. Utilisez la carte de hachage pour garder une trace de ce que vous avez déjà échangé.

Voir le code C # ci-dessous. 

  private void PermuteUniqueHelper(int[] nums, int index, List> res) { var used = new Dictionary(); if (index == nums.Length) { res.Add(new List(nums)); return; } for (int i = index; i < nums.Length; i++) { if (!used.ContainsKey(nums[i])) { swap(nums[i], nums[index]); this.PermuteUniqueHelper(nums, index + 1, res); swap(nums[i], nums[index]); used.Add(nums[i], true); } } }