Comment puis-je obtenir toutes les permutations de xPy?

Question

Je voudrais calculer toutes les permutations de taille Y d'un ensemble de taille X. C'est si j'avais (1,2,3) et que vous voulez toutes les permutations de taille 2, 3P2, il serait (1, 2) (1,3) (2,1) (2,3) (3,1) (3,2).

Les deux GSL et la STL de C ne fournissent xpx que je peux voir. Quelqu'un pourrait-il me diriger dans une bibliothèque C / C ++ qui peut faire ceci ou sort un algorithme rapide et efficace et de la mémoire?

Je suis en train de résoudre un très court cryptogramme. J'ai compris deux lettres et ont décidé de faire une attaque de force brute. J'ai « ouglg ouyakl » et je vérifie toutes les permutations contre un dictionnaire très bon. Je l'ai éliminé 2 lettres pour ses 24P7 ou 1,744,364,160 possibilités qui n'est pas si mal. J'ai un programme Perl en cours d'exécution maintenant, ce sera donc un test intéressant de l'efficacité totale du temps de programmation + temps d'exécution. :)

(Non, je ne veux pas seulement la réponse au cryptogramme.)

Answer 1

Je l'ai utilisé cette bibliothèque avant (note est C ++ ) dans le code qui avait besoin de faire quelque chose de similaire. Il a permutations et combinaisons, avec et sans répétition. Pour votre problème, cela devrait suffire (non testé ...):

std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);

std::vector<int>::iterator first = v.begin(), middle = v.begin() + 2, last = v.end();

do {
    // do stuff with elements in range first...middle (but dont change them)
} while(next_partial_permutation(first, middle, last));

Answer 2

Vous pouvez obtenir les combinaisons en utilisant std::next_permutation() sur un vector<bool> de drapeaux. Prenant votre exemple de choisir 2 éléments de (1,2,3), démarrez votre vecteur (false, true, true). La répétition next_permutation() sur cela vous donnera (true, false, true) puis (true, true, false), avant de recommencer.

Puisque vous voulez des permutations non combinaisons, chaque combinaison map à l'ensemble des éléments réels (par exemple (true, false, true) devient (1, 3)), puis générer toutes les permutations de ceux-ci à l'aide next_permutation() à nouveau.

Answer 3

Je ne exacly obtenir votre question sur cryptogramme. Mais si vous voulez trouver la plus longue permutation (anagrammes) de ces mots dans votre dictionnaire, vous pouvez essayer son chemin.

1. créer bitmask de parole. Vous pouvez probablement utiliser 64 bits Arithmétique de sorte que vous pouvez adapter presque 3 alpahbets à l'intérieur.

a-> premier bit, b-> second bit et ainsi de suite. Si vous avez mot dans votre cas « ouglg de ouyakl » cela signifie

 abcdefghijklmnopqrstuvxyzabcdefghijklmnopqrstuvxyzabcdefghijklmnop
 100000100011001000001001000000010000100100000100000000000000000000

(espère ne pas raté quelque chose) Maintenant, vous créez même bitmasks pour votre vocabulaire.

Et quand vous chek contre le vocabulaire il vous suffit de faire est

 vocabulary & ( ouglg_ouyakl ^ vocabulary)

et ce trows 0 si votre mot de vocabulaire est de ouglg_ouyakl.

A propos de permutations

for each permutation of numbers fom  1-n // that is 1,2 and 2,1
  for(i=0;i<end;i++)
    for(j=i+1;j<end;j++)
      SET[permutation[i]],SET[permutation[j]]

EDIT: prevous Soluton était inapropriée pour 24P7

.