Come ottenere il numero di avanti le combinazioni per il set?

Question

• Ho modificato testo originale per salvare i potenziali lettori po ' di tempo e di salute.Forse qualcuno si sarà effettivamente utilizzare questo.

So che è roba di base.Probabilmente piace molto, molto di base.
Come ottenere tutte le combinazioni possibili di un dato insieme.E. g.
set di corde = "abc";
Mi aspetto di ottenere:
a b c aa ab ac aaa aab aac aba abb abc aca acb acc baa bab ...
e l'elenco potrebbe continuare (se non ci sono limiti di lunghezza è impostato).

Sto cercando un codice pulito per tutto quello che ho trovato è stato una sorta di sporco e non funziona correttamente.Lo stesso posso dire di codice che ho scritto.

Ho bisogno di un codice di questo tipo perché sto scrivendo la forza bruta (md5) attuazione di lavorare su più thread.Il motivo è che non c'è processo principale che alimenta il thread con i pezzi delle loro combinazioni, in modo che potessero lavorare su questi su di loro.
Esempio:primo thread ottiene pacchetto di 100 permutazioni, la seconda ottiene prossimi 100 etc.
Fammi sapere se dovrei postare il programma definitivo ovunque.

EDIT #2 Ancora una volta grazie a voi ragazzi.
Grazie a voi ho finito il mio Slave/Master di Forza Bruta applicazione implementata con MPICH2 (sì, può funzionare sotto linux e windows di fronte per esempio di rete), e siccome la giornata è quasi finita qui, e ho già sprecato un sacco di tempo (e il sole) mi accingo con il mio prossimo compito ...:)
Lei mi ha mostrato che StackOverflow comunità è fantastico, grazie!

Answer 1

Ecco un po 'di codice C ++ che genera le permutazioni di una potenza impostato per una data lunghezza.

Il getPowPerms funzione accetta un insieme di caratteri (come vettore di stringhe) ed una lunghezza massima, e restituisce un vettore di stringhe permutati:

#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';
}

Quando viene eseguito, questo esempio stampe

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

Aggiornamento: non sono sicuro se questo è utile, ma qui è un "generatore" funzione chiamata next che crea l'elemento successivo nella lista data la voce corrente.

Forse si potrebbe generare i primi N articoli e inviarli da qualche parte, quindi generare i prossimi N articoli e inviarli da qualche altra parte.

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

C++ ha una funzione next_permutation(), ma non credo che è quello che vuoi.

Si dovrebbe essere in grado di farlo abbastanza facilmente con una funzione ricorsiva.ad es.

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:Per la filettatura parte, presumo che si sta lavorando su una password brute forcer?

Se è così, credo che la password di test è ciò che si desidera accelerare piuttosto che di generazione di password.

Pertanto, si può semplicemente creare un processo padre che genera tutte le combinazioni, quindi ogni kth password è dato al thread k mod N (dove N è il numero di thread) per il controllo.

Answer 3

Un'altra versione di permutazione è nella libreria standard di Python, anche se è messa in discussione in C ++.

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

Ma l'elenco contiene una sequenza infinita di ogni personaggio, quindi penso che il metodo come ordinare quelli dovrebbero essere definiti prima, e indicare chiaramente il vostro algoritmo.

Answer 4

Non posso dare il codice, ma quello che vi serve è un algoritmo ricorsivo ecco alcune pseudo codice

L'idea è semplice, concatinate ogni stringa nel set con ogni altra stringa, quindi permutare le corde. aggiungere tutte le corde più piccoli per l'unità e fare di nuovo la stessa cosa con il nuovo set. Andare avanti fino a che sono stanchi:)

Potrebbe essere un po 'di confusione, ma pensarci un po';)

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);
}

Questo ovviamente causare un overflow dello stack, perché non v'è alcuna condizione di terminazione :) così si può mettere nelle build_combinations funzione che cosa mai condizionare ti piace (forse dimensioni del set?) Per terminare la ricorsione

Answer 5

Ecco un modo strano e normalmente non è l'ideale di farlo, ma hey, funziona, e non fa uso di ricorsione: -)

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 6

Lo so che hai una buona risposta perfettamente già (quelli più in realtà), ma stavo pensando un po 'su questo problema e mi si avvicinò con un algoritmo piuttosto pulito che potrei anche condividere.

In sostanza, è possibile farlo partendo da un elenco dei simboli, e poi aggiungendo ogni simbolo di ogni altro simbolo per fare due parole simbolo, e quindi aggiungendo ogni simbolo ad ogni parola. Che potrebbe non avere molto senso come quello, quindi ecco come si presenta:

Inizia con 'a', 'b' e 'c' come i simboli e aggiungerli a un elenco:

a
b
c

Append 'a', 'b' e 'c' di ogni parola nella lista. La lista si presenta quindi come:

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

Poi aggiungere 'a', 'b' e 'c' per ogni nuova parola nella lista in modo che la lista sarà simile a questa:

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

È possibile farlo facilmente utilizzando un iteratore e lasciare che l'iteratore andare avanti fin dall'inizio.

Questo codice stampa fuori ogni parola che viene aggiunto alla lista.

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 7

un esempio di 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

L'uscita è esattamente ciò che ci si aspetta di ottenere: a b c aa ab ac aaa aab aac aba abb abc aca ACB acc baa bab ... (L'esempio utilizza i caratteri ASCII intero minuscole impostare, cambiare "caratteri = [ 'a', 'b', 'c']" per ridurre la dimensione di output)

Answer 8

Quello che vuoi è chiamato permutazione.

Controlla questo per un Permutazione implementazione in java