Come posso ottenere tutte le permutazioni di xpy?
-
12-09-2019 - |
Domanda
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.)
Soluzione
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));
Altri suggerimenti
È 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.
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.
- 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
.