Статья:
Генерация случайных сочетаний. Генерация сочетания по его порядковому номеру

Автор(ы): Герасимов Василий Александрович
Дата: 04.07.2011
Статья посвящена методам генерации случайных сочетаний. Рассматривается два таких метода – генерация сочетания методом случайной перестановки и генерация сочетания по его порядковому номеру. Приводится библиотека функций на языке C++, реализующих описанные методы. Сравнивается производительность разработанных методов. Также рассмотрено интересное следствие работы алгоритма генерации сочетания по его порядковому номеру — компактное хранение последовательностей элементов.

Авторы:
Герасимов Василий Александрович

Аннотация:
Статья посвящена методам генерации случайных сочетаний. Рассматривается два таких метода – генерация сочетания методом случайной перестановки и генерация сочетания по его порядковому номеру. Приводится библиотека функций на языке C++, реализующих описанные методы. Сравнивается производительность разработанных методов. Также рассмотрено интересное следствие работы алгоритма генерации сочетания по его порядковому номеру — компактное хранение последовательностей элементов.

Генерация сочетания по его порядковому номеру
Супер! То что нужно, а можно ещё генерацию сочетания по номеру с заданным алфавитом?
Или вообще вот такое: тут

Автор: nen777w
Дата: 20.12.10

Здравствуйте, nen777w, Вы писали:

N>Генерация сочетания по его порядковому номеру
N>Супер! То что нужно, а можно ещё генерацию сочетания по номеру с заданным алфавитом?
N>Или вообще вот такое: тут

Автор: nen777w
Дата: 20.12.10

Да, если алфавит записать в STL-последовательность и передать итераторы begin() и end() в функцию для генерации сочетания — из последовательности будут выбраны элементы, которые входят в сочетание.
Например:
char alhabet[] = {'a', 'b', 'c', '#', '\n'};
char combination[sizeof(alhabet)/sizeof(alhabet[0])];
unsigned int comb_num = 2; // Номер сочетания
unsigned int k = 3;
CombinationFromNumber(comb_num, k, alhabet, alhabet+sizeof(alhabet)/sizeof(alhabet[0]), combination); // Получим сочетание номер 2 из 5-ти по 3-м из алфавита alhabet. Сочетание запишется в combination (валидны первые k символов)

Можно вызвать другой вариант функции, который, положим, не использует итераторы произвольного доступа

правильно ли я понимаю, что генерация по номеру хороша в том случае если случайные числа приходят из дорогого источника -- достоинство этого метода в экономном расходовании случайных бит.

Интуция подсказывает, что на практике, при дешевом источнике случайных бит, лучший способ это частичная (ленивая) перестановка -- то есть сделать не весь shuffle, а только его нужную часть?

Здравствуйте, dilmah, Вы писали:

D>правильно ли я понимаю, что генерация по номеру хороша в том случае если случайные числа приходят из дорогого источника -- достоинство этого метода в экономном расходовании случайных бит.

D>Интуция подсказывает, что на практике, при дешевом источнике случайных бит, лучший способ это частичная (ленивая) перестановка -- то есть сделать не весь shuffle, а только его нужную часть?

Да, разумеется, чем дороже генерация случайного числа, тем становится более выгодным применять алгоритм генерации по номеру: ведь он использует генерацию случайного числа лишь однажды в противоположность random_shuffle(), использующему такую генерацию почти столько раз, каков размер передаваемой ему последовательности.

Частичная перестановка, вполне возможно, для некоторого класса задач действительно самое лучшее решение, если, например, вся подпоследовательность нужна не всегда.

Здравствуйте, Герасимов Василий Александрович, Вы писали:

Параметр CombNumber (там, где он присутствует) должен удовлетворять условию 0≤CombNumber≤C(n,k) – это порядковый номер сочетания.

Здесь, я так понял, ошибка — неравенство справа должно быть строгим.