¿Cómo consigo todas las permutaciones de xpy?

Question

Me gustaría calcular todas las permutaciones de tamaño Y de un conjunto de tamaño X. Es decir, si tuviera (1,2,3) y quiere todas las permutaciones de tamaño 2, 3P2, que serían (1, 2) (1,3) (2,1) (2,3) (3,1) (3,2).

Tanto la GSL y STL C ++ sólo proporcionan xPx que puedo ver. Podría alguien me punto en una biblioteca de C / C ++ que pueden hacer esto o explicar un algoritmo rápido y eficiente y la memoria?

Estoy tratando de resolver un criptograma muy corto. He descubierto dos cartas y he decidido hacer un ataque de fuerza bruta. Tengo "ouyakl ouglg" y estoy comprobando cada permutación contra un muy buen diccionario. He eliminado 2 letras por lo que su 24P7 o 1,744,364,160 posibilidades que no es tan malo. Tengo un programa Perl se ejecuta ahora, para que esta será una prueba interesante de la eficiencia total de tiempo de programación + tiempo de ejecución. :)

(No, yo no sólo quiero la respuesta a la criptograma.)

Answer 1

He usado esta biblioteca antes (nota es C ++ ) en el código que tenía que hacer algo similar. Tiene permutaciones y combinaciones, con y sin repetición. Para su problema, esto debería ser suficiente (no probado ...):

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

Usted puede obtener las combinaciones utilizando std::next_permutation() en un vector<bool> de banderas. Tomando su ejemplo de recoger 2 elementos de (1,2,3), inicie su vector como (false, true, true). Repitiendo next_permutation() en esto le dará (true, false, true) continuación (true, true, false), antes de empezar de nuevo.

Puesto que desea permutaciones no combinaciones, asignar cada combinación para el conjunto de elementos reales (por ejemplo (true, false, true) se convierte en (1, 3)) y luego generar todas las permutaciones de estos usando next_permutation() de nuevo.

Answer 3

Yo no entiendo exacly pregunta sobre criptograma. Pero si usted quiere encontrar la permutación más larga (anagrama) de estas palabras en su diccionario que puede probar su camino.

1. crear máscara de bits de palabra. Probablemente se puede usar la aritmética 64 bits para que pueda caber casi 3 alpahbets interior.

a-> primer bit, b-> segundo bit y así sucesivamente. Si tiene palabra en su caso "ouyakl ouglg" Significa esto

 abcdefghijklmnopqrstuvxyzabcdefghijklmnopqrstuvxyzabcdefghijklmnop
 100000100011001000001001000000010000100100000100000000000000000000

(espero no haber perdido algo) Ahora se crea mismas máscaras de bits para su vocabulario.

Y cuando usted chek contra vocabulario sólo hay que hacer es

 vocabulary & ( ouglg_ouyakl ^ vocabulary)

y esto trows 0 si su palabra del vocabulario es de ouglg_ouyakl.

Sobre permutaciones

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: Soluton prevous era inadecuadoas para 24P7

.