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

StackOverflow https://stackoverflow.com/questions/1663949

  •  12-09-2019
  •  | 
  •  

Вопрос

Я хотел бы вычислить все перестановки размера 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», и я проверяю каждую перестановку по очень хорошему словарю.Я исключил две буквы, так что это 24P7 или 1 744 364 160 возможностей, что не так уж и плохо.Сейчас у меня работает программа на Perl, так что это будет интересный тест общей эффективности времени программирования + времени выполнения.:)

(Нет, мне не просто нужен ответ на криптограмму.)

Это было полезно?

Решение

я использовал этот ранее (обратите внимание, что это 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));

Другие советы

Вы можете получить комбинации, используя 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() снова.

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

  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.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top