Как получить все перестановки xPy?

Я хотел бы рассчитать все перестановки размера Y набора размера X. То есть, если бы у меня было (1,2,3) и мне нужны все перестановки размера 2, 3P2, это было бы (1,2) ( 1,3) (2,1) (2,3) (3,1) (3,2).

И GSL, и C++ STL предоставляют только xPx, которые я вижу. Может ли кто-нибудь указать мне на библиотеку C/C++, которая может это сделать, или объяснить быстрый и эффективный алгоритм памяти?

Я пытаюсь решить очень короткую криптограмму. Я вычислил две буквы и решил провести атаку грубой силы. У меня есть "ouglg ouyakl", и я проверяю каждую перестановку по очень хорошему словарю. Я исключил 2 буквы, так что это 24P7 или 1 744 364 160 вариантов, что не так уж плохо. У меня сейчас запущена программа на Perl, так что это будет интересный тест общей эффективности времени программирования + времени выполнения. :)

(Нет, я не просто хочу получить ответ на криптограмму.)


c c++ permutation
person Schwern    schedule 02.11.2009    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Я уже использовал эту библиотеку (обратите внимание, что это C++) в коде что нужно было сделать что-то подобное. Он имеет перестановки и комбинации, с повторением и без повторения. Для вашей проблемы этого должно быть достаточно (непроверено...):

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));
person Greg Rogers    schedule 02.11.2009
comment
Спасибо, так бы и было! К счастью, я оптимизировал задачу до 21P4 * 100, с чем Perl справляется примерно за 10 минут. - person Schwern; 03.11.2009

arrow_upward
0
arrow_downward

Вы можете получить комбинации, используя std::next_permutation() на vector<bool> флагах. Взяв ваш пример выбора 2 элементов из (1,2,3), начните свой вектор как (false, true, true). Повторяя next_permutation(), вы получите (true, false, true), затем (true, true, false), прежде чем начать заново.

Поскольку вам нужны перестановки, а не комбинации, сопоставьте каждую комбинацию с набором фактических элементов (например, (true, false, true) становится (1, 3)) и затем снова сгенерируйте все перестановки, используя next_permutation().

person Sumudu Fernando    schedule 02.11.2009

arrow_upward
0
arrow_downward

Я не совсем понимаю ваш вопрос о криптограмме. Но если вы хотите найти самую длинную перестановку (анаграмму) этих слов в своем словаре, вы можете попробовать его способ.

  1. создать битовую маску вашего слова. Вы, вероятно, можете использовать 64-битную арифметику, чтобы уместить почти 3 алфавита внутри.

a-> первый бит, b-> второй бит и так далее. Если в вашем случае "ouglg ouyakl" есть слово, это означает

 abcdefghijklmnopqrstuvxyzabcdefghijklmnopqrstuvxyzabcdefghijklmnop
 100000100011001000001001000000010000100100000100000000000000000000

(надеюсь, я ничего не пропустил) Теперь вы создаете такие же битмаски для своего словаря.

И когда вы проверяете словарный запас, вам просто нужно сделать следующее:

 vocabulary & ( ouglg_ouyakl ^ vocabulary)

и это возвращает 0, если ваше словарное слово взято из ouglg_ouyakl.

О перестановках

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]]

РЕДАКТИРОВАТЬ: предыдущее решение было неподходящим для 24P7.

person Luka Rahne    schedule 02.11.2009