среда, 8 апреля 2009 г.

Быстрый перебор всех сочетаний(выборок)

Возникла потребность в "быстром" алгоритме перебора всевозможных размещений K единиц в N разрядах. Немного погуглил, но так и не нашел алгоритмов без дважды вложенных циклов. А ведь хочется получить функцию для "выработки" следующей комбинации на основе предыдущей. Да и хранить единицы и нули желательно не в строках(побайтно), а в многоразрядных числах(побитно). В этом случае, конечно, возникает вопрос разрядности чисел, как ограничение на параметр N ... тогда используем числа разрядности 64, 128, 256 бит и т.д. Например, можно воспользоваться классом big_int в составе библиотеки Boost. Прикинем на глаз всевозможные варианты размещения 3-ёх единиц в 5-ти разрядах и порядок перебора этих вариантов:
1 1 1 0 0
1 1 0 1 0
1 1 0 0 1
1 0 1 1 0
1 0 1 0 1
1 0 0 1 1
0 1 1 1 0
0 1 1 0 1
0 1 0 1 1
0 0 1 1 1
Итого 10 вариантов (число сочетаний из пяти по три). Визуально алгоритм выглядит как пробегающая слева направо единица. Опишем его формально с использованием рекурсии (в данном алгоритме использование рекурсии не желательно, но с ней "красивше"):
1) Если самый правый символ "0",
то находим среди всех единиц самую правую и сдвигаем её на 1 позицию вправо.
2) Если самый правый символ "1",
то отрубаем самый правый символ и отправляем полученную комбинацию (длины N-1 с K-1 единицами) на п.1 алгоритма. В полученном значении находим самую правую единицу и вписываем вырезанную ранее единицу сразу после неё.

При хранении комбинации в многоразрядных переменных нам понадобятся следующие операции:
а) Операция определения значения младшего разряда
(a & 1)
б) Операция сдвига вправо самой младшей единицы, с неприкосновенностью более старших разрядов.
int shiftLast1(int a) {
    return ((a-1) ^ ((a^(a-1)) >> 2));
}
в) Операция дописывания единицы справа от самой младшей единицы.
int add1AfterLast1(int a) {
    return ( a | ( ((a^(a-1)) + 1) >> 2 ) );
}

Теперь метод генерации первой комбинации. K единиц сдвигаются вправо на (N-K) позиций.
int firstSoch(int n, int k) {
    return ( ((1 << k) - 1) << (n - k) );
}

Главный метод для вычисления комбинации реализует описаный нами алгоритм:
int nextSoch(int a)
{
    // в случае последней комбинации вернём нуль
    if ((a & (a+1)) == 0)
    return 0;

    if (a & 1)
        return add1AfterLast1( nextSoch(a >> 1) << 1 );
    else
        return shiftLast1(a);
}

З.Ы.
1) Вместо функций (б) и (в) можно использовать макросы. Думаю функции с одним лишь ретурном компилятор включает "инлайн", тогда разницы с "дефайном" в принципе и нет. (Аккуратнее с вложенным вызовом макросов! - напоролся однако)
2) Аккуратнее с типами констант:
(1 << 48) не равно (0x01000000000000)
(__int64(1) << 48) равно (0x01000000000000)

З.З.Ы.
Если алгоритм вам пригодился или вы имеете интересные замечания/комментарии, как говорится, feel free to comment . . .

2 комментария:

Bratskiy комментирует...

Спасибо огромное. Алгоритм работает и очень понадобился

Анонимный комментирует...

Отличный алгоритм. Спасибо :)