Come posso ottenere tutte le permutazioni di xpy?

Question

Mi piacerebbe calcolare tutte le permutazioni di dimensione Y di un insieme di dimensioni X. Cioè se ho avuto (1,2,3) e si vuole tutte le permutazioni di dimensione 2, 3P2, sarebbe (1, 2) (1,3) (2,1) (2,3) (3,1) (3,2).

Sia la GSL e C ++ STL forniscono solo XPX che posso vedere. Qualcuno potrebbe puntare a una libreria C / C ++ che può fare questo o precisare un algoritmo veloce ed efficiente e la memoria?

Sto cercando di risolvere un brevissimo crittogramma. Ho capito due lettere e hanno deciso di fare un attacco di forza bruta. Ho "ouglg ouyakl" e sto controllando ogni permutazione contro un ottimo dizionario. Ho eliminato 2 lettere per cui il suo 24P7 o 1,744,364,160 possibilità che non è poi così male. Ho un programma Perl in esecuzione ora, quindi questo sarà un test interessante della efficienza totale del tempo di programmazione + fase di esecuzione. :)

(No, io non voglio solo la risposta al crittogramma.)

Answer 1

Ho usato questa libreria prima (nota è C ++ ) in codice che aveva bisogno di fare qualcosa di simile. Ha permutazioni e combinazioni, con e senza ripetizione. Per il vostro problema, questo dovrebbe essere sufficiente (non testata ...):

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

È possibile ottenere le combinazioni utilizzando std::next_permutation() su un vector<bool> di bandiere. Prendendo il tuo esempio di raccogliere 2 elementi da (1,2,3), avviare il vettore come (false, true, true). Ripetendo next_permutation() su questo vi darà (true, false, true) allora (true, true, false), prima di ricominciare da capo.

Dal momento che si desidera permutazioni non combinazioni, mappa ogni combinazione per l'insieme di elementi reali (ad esempio (true, false, true) diventa (1, 3)) e quindi generare tutte le permutazioni di questi usando next_permutation() di nuovo.

Answer 3

Non exacly ottengo le tue domande su crittogramma. Ma se si vuole trovare più lunga permutazione (anagramma) di queste parole nel dizionario che si può provare la sua strada.

1. creare maschera di bit di parola. Probabilmente si può usare a 64 bit aritmetica in modo da poter adattare quasi 3 alpahbets all'interno.

a-> primo bit, b-> secondo bit e così via. Se si dispone di parola nel tuo caso "ouglg ouyakl" Questo significa

 abcdefghijklmnopqrstuvxyzabcdefghijklmnopqrstuvxyzabcdefghijklmnop
 100000100011001000001001000000010000100100000100000000000000000000

(spero non ho perso qualcosa) Ora si crea stessi bitmasks per il vostro vocabolario.

E quando si chek contro il vocabolario non resta che fare è

 vocabulary & ( ouglg_ouyakl ^ vocabulary)

e questo trow 0 se la tua parola vocabolario è da ouglg_ouyakl.

A proposito di permutazioni

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 era inapropriate per 24P7

.