#java #bit-manipulation #combinations #combinatorics
#java #манипулирование битами #комбинации #комбинаторика
Вопрос:
Рассмотрим всю комбинацию длины 3 следующего массива целых чисел {1,2,3}.
Я хотел бы просмотреть всю комбинацию длины 3, используя следующий алгоритм из Википедии
// find next k-combination
bool next_combination(unsigned longamp; x) // assume x has form x'01^a10^b in binary
{
unsigned long u = x amp; -x; // extract rightmost bit 1; u = 0'00^a10^b
unsigned long v = u x; // set last non-trailing bit 0, and clear to the right; v=x'10^a00^b
if (v==0) // then overflow in v, or x==0
return false; // signal that next k-combination cannot be represented
x = v (((v^x)/u)>>2); // v^x = 0'11^a10^b, (v^x)/u = 0'0^b1^{a 2}, and x ← x'100^b1^a
return true; // successful completion
}
Каким должно быть мое начальное значение для этого алгоритма для всей комбинации {1,2,3}?
Когда я получу результат алгоритма, как мне восстановить комбинацию?
Я попробовал следующую прямую адаптацию, но я новичок в побитовой арифметике и не могу сказать, правильно ли это.
// find next k-combination, Java
int next_combination(int x)
{
int u = x amp; -x;
int v = u x;
if (v==0)
return v;
x = v (((v^x)/u)>>2);
return x;
}
Комментарии:
1. Вы пробовали, скажем, запускать код? Примечание.B. алгоритм Википедии использует
xкак входной, так и выходной параметр. В Java их нет.2. @MattBall Когда я запускаю код, он возвращает целое число. Я не знаю, как это интерпретировать и как перевести в комбинацию. Я отредактирую свою адаптацию Java. Это была первая попытка, просто проанализировать алгоритм wiki в режиме отладки. Спасибо, что указали на это.
3. @Mr.Wizard Я продолжаю по вашему предложению. Спасибо.
Ответ №1:
Я нашел класс, который точно решает эту проблему. Смотрите класс CombinationGenerator здесь
https://bitbucket.org/rayortigas/everyhand-java/src/9e5f1d7bd9ca/src/Combinatorics.java
Чтобы восстановить комбинацию, выполните
for(Long combination : combinationIterator(10,3))
toCombination(toPermutation(combination);
Спасибо всем за ваш вклад.
Ответ №2:
Я написал класс для обработки общих функций для работы с биномиальным коэффициентом, который относится к типу проблемы, к которой относится ваша проблема. Он выполняет следующие задачи:
-
Выводит все K-индексы в удобном формате для любого N выбора K в файл. K-индексы могут быть заменены более описательными строками или буквами. Этот метод делает решение такого типа задач довольно тривиальным.
-
Преобразует K-индексы в соответствующий индекс записи в отсортированной таблице биномиальных коэффициентов. Этот метод намного быстрее, чем более старые опубликованные методы, которые основаны на итерации. Это делается с помощью математического свойства, присущего треугольнику Паскаля. В моей статье говорится об этом. Я считаю, что я первый, кто обнаружил и опубликовал этот метод, но я могу ошибаться.
-
Преобразует индекс в отсортированной таблице биномиальных коэффициентов в соответствующие K-индексы. Я полагаю, что это может быть быстрее, чем ссылка, которую вы нашли.
-
Использует метод Mark Dominus для вычисления биномиального коэффициента, который с гораздо меньшей вероятностью переполняется и работает с большими числами.
-
Класс написан на .NET C # и предоставляет способ управления объектами, связанными с проблемой (если таковые имеются), с использованием общего списка. Конструктор этого класса принимает значение bool с именем InitTable, которое при значении true создаст общий список для хранения объектов, которыми нужно управлять. Если это значение равно false, то оно не создаст таблицу. Таблицу не нужно создавать для выполнения 4 вышеуказанных методов. Для доступа к таблице предоставляются методы доступа.
-
Существует связанный тестовый класс, который показывает, как использовать класс и его методы. Он был тщательно протестирован в 2 случаях, и известных ошибок нет.
Чтобы прочитать об этом классе и загрузить код, см. Таблицу биномиального коэффициента.
Преобразовать этот класс в Java не должно быть сложно.