Comment obtenir le nombre de combinaisons suivantes pour un ensemble donné?

Question

• J'ai modifié le texte original afin d'économiser du temps et de la santé aux lecteurs potentiels. Peut-être que quelqu'un va l'utiliser.

Je sais que c'est basique. Probablement comme très, très basique.
Comment obtenir toutes les combinaisons possibles d'ensemble donné. E.g.
string set = "abc";
Je vous attendre à obtenir:
a b c aa ab ac aaa AAB aac aba abb abc aca PBR selon baa ... bab
et la liste est longue (si est fixé aucune limite pour la longueur).

Je cherche un code très propre pour cela - tout ce que j'ai trouvé était sale et ne fonctionnait pas correctement. La même chose que je peux dire à propos du code que j'ai écrit.

J'ai besoin d'un tel code car j'écris une implémentation en force brute (md5) en travaillant sur plusieurs threads. Le modèle est qu'il existe un processus Parent qui alimente les threads avec des morceaux de leurs propres combinaisons, de sorte qu'ils travaillent sur eux-mêmes.
Exemple: le premier thread reçoit un package de 100 permutations, le second reçoit le suivant 100 etc.
Faites-moi savoir si je devrais poster le programme final n'importe où.

EDIT # 2 Encore une fois merci les gars.
Grâce à vous, j'ai terminé mon application Slave/Master Brute-Force implémentée avec MPICH2 (oui, je peux travailler sous Linux et Windows par exemple pour le réseau) et comme la journée est presque finie ici, et j'ai déjà gaspillé un Beaucoup de temps (et de soleil) Je vais procéder à ma prochaine tâche ... :)
Vous m'avez montré que la communauté StackOverflow est géniale - merci!

Answer 1

Voici un code C++ qui génère des permutations d'un ensemble de puissance jusqu'à une longueur donnée.

La fonction getPowPerms prend un ensemble de caractères (comme vecteur de chaînes) et une longueur maximale, et retourne un vecteur de chaînes permutés:

#include <iostream> 
using std::cout; 
#include <string> 
using std::string; 
#include <vector> 
using std::vector; 

vector<string> getPowPerms(const vector<string>& set, unsigned length) { 
    if(length == 0) return vector<string>(); 
    if(length == 1) return set; 

    vector<string> substrs = getPowPerms(set,length-1); 
    vector<string> result = substrs; 
    for(unsigned i = 0; i < substrs.size(); ++i) { 
    for(unsigned j = 0; j < set.size(); ++j) { 
     result.push_back(set[j] + substrs[i]); 
    } 
    } 

    return result; 
} 

int main() { 
    const int MAX_SIZE = 3; 
    string str = "abc"; 

    vector<string> set;  // use vector for ease-of-access    
    for(unsigned i = 0; i < str.size(); ++i) set.push_back(str.substr(i,1)); 

    vector<string> perms = getPowPerms(set, MAX_SIZE); 
    for(unsigned i = 0; i < perms.size(); ++i) cout << perms[i] << '\n'; 
} 

Lorsqu'il est exécuté, cet exemple imprime

a b c aa ba ca ab bb cb ... acc bcc ccc 

Mise à jour: Je ne sais pas si cela est utile, mais voici une fonction "générateur" appelée next qui crée l'élément suivant dans la liste étant donné l'élément actuel.

Peut-être que vous pouvez générer les premiers N articles et les envoyer quelque part, puis générer les prochains N articles et les envoyer ailleurs.

string next(const string& cur, const string& set) { 
    string result = cur; 
    bool carry = true; 
    int loc = cur.size() - 1; 
    char last = *set.rbegin(), first = *set.begin(); 
    while(loc >= 0 && carry) { 
    if(result[loc] != last) {    // increment    
     int found = set.find(result[loc]); 
     if(found != string::npos && found < set.size()-1) { 
     result[loc] = set.at(found+1); 
     } 
     carry = false; 
    } else {        // reset and carry   
     result[loc] = first; 
    } 
    --loc; 
    } 
    if(carry) {        // overflow    
    result.insert(result.begin(), first); 
    } 
    return result; 
} 

int main() { 
    string set = "abc"; 
    string cur = "a"; 
    for(int i = 0; i < 20; ++i) { 
    cout << cur << '\n';  // displays a b c aa ab ac ba bb bc ... 
    cur = next(cur, set); 
    } 
} 

Answer 2

Ce que vous voulez s'appelle Permutation.

Vérifiez cela pour un Permutation implementation en java

Answer 3

Une autre version de permutation est dans la bibliothèque standard de Python bien que vous avez interrogé en C++.

http://docs.python.org/library/itertools.html#itertools.permutations

Mais votre liste contient une séquence d'infinitif d'un chaque caractère, donc je pense que la méthode comment commander ceux-ci devraient être définis d'abord, et indiquer clairement votre algorithme.

Answer 4

Je ne peux pas vous donner le code, mais ce dont vous avez besoin est un algorithme récursif est ici un code pseudo

L'idée est simple, concaténer chaque chaîne dans votre jeu avec chaque autre chaîne, puis permute la cordes. ajoutez toutes vos plus petites cordes à votre ensemble et refaites la même chose avec le nouvel ensemble. Continuer à aller jusqu'à ce que vous êtes fatigué :)

peut-être un peu déroutant, mais penser un peu;)

set = { "a", "b", "c"} 

build_combinations(set) 
{ 
    new_set={} 
    for(Element in set){ 
    new_set.add(Element); 
    for(other_element in set) 
     new_element = concatinate(Element, other_element); 
     new_set.add(new_element); 
    } 

    new_set = permute_all_elements(new_set); 

return build_combinations(new_set); 
} 

Cela évidemment causer un débordement de pile parce qu'il n'y a pas de condition de terminaison :) alors mis en la fonction build_combinations quelle que soit la condition que vous aimez (peut-être la taille de l'ensemble?) pour terminer la récursion

Answer 5

C++ a une fonction next_permutation(), mais je ne pense pas que ce soit ce que vous voulez.

Vous devriez être capable de le faire assez facilement avec une fonction récursive. par exemple.

void combinations(string s, int len, string prefix) { 
    if (len<1) { 
    cout << prefix << endl; 
    } else { 
    for (int i=0;i<s.size();i++) { 
     combinations(s, len-1, prefix + s[i]) 
    } 
    } 
} 

EDIT: Pour la partie thread, je suppose que vous travaillez sur un mot de passe brute forcer?

Si oui, je suppose que la partie de test de mot de passe est ce que vous voulez accélérer plutôt que la génération de mot de passe.

Par conséquent, vous pouvez simplement créer un processus parent qui génère toutes les combinaisons, puis tous k e mot de passe est donnée au fil k mod N (où N est le nombre de threads) pour vérifier.

Answer 6

est ici une étrange façon et normalement pas l'idéal de le faire, mais bon, ça marche, et il n'utilise pas récursion :-)

void permutations(char c[], int l) // l is the length of c 
{ 
    int length = 1; 
    while (length < 5) 
    { 
     for (int j = 0; j < int(pow(double(l), double(length))); j++) // for each word of a particular length 
     { 
      for (int i = 0; i < length; i++) // for each character in a word 
      { 
       cout << c[(j/int(pow(double(l), double(length - i - 1))) % l)]; 
      } 
      cout << endl; 
     } 
     length++; 
    } 
} 

Answer 7

Je sais que vous avez une très bonne réponse déjà (en fait plusieurs ceux), mais je pensais un peu à ce problème et je suis venu avec un algorithme assez propre que je pourrais aussi bien partager. Fondamentalement, vous pouvez le faire en commençant par une liste de symboles, puis en ajoutant chaque symbole à l'autre symbole pour faire deux mots de symbole, puis en ajoutant chaque symbole à chaque mot. Cela pourrait ne pas beaucoup de sens comme ça, alors voilà à quoi il ressemble:

Commencez par « a », « b » et « c » comme les symboles et les ajouter à une liste:

a 
b 
c 

Ajouter 'a', 'b' et 'c' à chaque mot de la liste.La liste ressemble alors à:

a 
b 
c 
aa 
ab 
ac 
ba 
bb 
bc 
ca 
cb 
cc 

Puis append « a », « b » et « c » à chaque nouveau mot dans la liste afin que la liste ressemblera à ceci:

a 
b 
c 
aa 
ab 
ac 
ba 
bb 
bc 
ca 
cb 
cc 
aaa 
aab 
aac 
aba 
abb 
... and so on 

Vous pouvez faites-le facilement en utilisant un itérateur et laissez simplement l'itérateur continuer depuis le début.

Ce code imprime chaque mot ajouté à la liste.

void permutations(string symbols) 
{ 
    list<string> l; 
    // add each symbol to the list 
    for (int i = 0; i < symbols.length(); i++) 
    { 
     l.push_back(symbols.substr(i, 1)); 
     cout << symbols.substr(i, 1) << endl; 
    } 
    // infinite loop that looks at each word in the list 
    for (list<string>::iterator it = l.begin(); it != l.end(); it++) 
    { 
     // append each symbol to the current word and add it to the end of the list 
     for (int i = 0; i < symbols.length(); i++) 
     { 
      string s(*it); 
      s.push_back(symbols[i]); 
      l.push_back(s); 
      cout << s << endl; 
     } 
    } 
} 

Answer 8

un exemple Python:

import itertools 
import string 

characters = string.ascii_lowercase 
max_length = 3 
count = 1 
while count < max_length+1: 
    for current_tuple in itertools.product(characters, repeat=count): 
     current_string = "".join(current_tuple) 
     print current_string 
    count += 1 

La sortie est exactement ce que vous attendez d'obtenir: abc aa ab ac aaa AAB aac aba abb abc aca PBR selon baa ... bab (la exemple utilise le jeu complet de caractères ASCII en minuscules, changez "characters = ['a', 'b', 'c']" pour réduire la taille de la sortie)