Como faço para obter todas as permutações de xpy?

Question

Eu gostaria de calcular todas as permutações de tamanho Y de um conjunto de tamanho X. Isto é, se eu tivesse (1,2,3) e quer todas as permutações de tamanho 2, 3P2, seria (1, 2) (1,3) (2,1) (2,3) (3,1) (3,2).

Tanto a GSL e C ++ STL só fornecem XPX que eu possa ver. Poderia alguém ponto-me na biblioteca um C / C ++ que pode fazer isto ou soletrar uma rápida e memória algoritmo eficiente?

Eu estou tentando resolver um curto criptograma. Eu descobri duas cartas e decidiram fazer um ataque de força bruta. Eu tenho "ouyakl ouglg" e estou verificando cada permutação contra um muito bom dicionário. Eu eliminei 2 letras pelo que a sua 24P7 ou 1,744,364,160 possibilidades que não é tão ruim. Eu tenho um programa Perl correndo agora, de modo que este será um teste interessante da eficiência total de programar tempo tempo + prazo. :)

(Não, eu não só quero a resposta para o criptograma.)

Answer 1

Eu usei esta biblioteca antes (nota é C ++ ) no código que precisava fazer algo similar. Tem permutações e combinações, com e sem repetição. Para o seu problema, isso deve ser suficiente (não testado ...):

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

Você pode obter as combinações usando std::next_permutation() em um vector<bool> de bandeiras. Tomar o seu exemplo de escolher 2 elementos da (1,2,3), iniciar o seu vector como (false, true, true). Repetindo next_permutation() sobre isso lhe dará (true, false, true) então (true, true, false), antes de começar de novo.

Desde que você quer permutações não combinações, mapear cada combinação com o conjunto de elementos reais (por exemplo (true, false, true) torna-se (1, 3)) e, em seguida, gerar todas as permutações destes utilizando next_permutation() novamente.

Answer 3

Eu não exacly obter a sua pergunta sobre o criptograma. Mas se você quiser encontrar mais longo permutação (anagrama) desta palavras no dicionário, você pode tentar o seu caminho.

1. criar máscara de bits de palavra. Provavelmente, você pode usar 64 arithmetics bit para que possa caber quase 3 alpahbets dentro.

a-> primeiro bit, b-> segundo bit e assim por diante. Se você tem palavra no seu "ouglg ouyakl" caso isso significa

 abcdefghijklmnopqrstuvxyzabcdefghijklmnopqrstuvxyzabcdefghijklmnop
 100000100011001000001001000000010000100100000100000000000000000000

(espero não ter perdido alguma coisa) Agora você cria mesmos bitmasks para o seu vocabulário.

E quando você chek contra vocabulário que você apenas tem que fazer é

 vocabulary & ( ouglg_ouyakl ^ vocabulary)

E este trows 0 se sua palavra do vocabulário é de ouglg_ouyakl.

Sobre permutações

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 foi inapropriate para 24P7

.