Как пронумеровать неупорядоченные выборки

[math123]

Всем, привет!

Нужно пронумеровать неупорядоченные выборки. Например можно выбрать 2 карты из колоды 52 карты $C(n, k) = C(52, 2) = 1326 $-ю способами. Нужно теперь пронумеровать эти способы, т.е. по числу от 1 до 1326 получить 2 карты и по двум картам получить их номер от 1 до 1326.

Подскажите, в каком направлении двигаться.

[dgwuqtj]

Тут есть готовый алгоритм: http://www.e-maxx-ru.1gb.ru/algo/generating_combinations. Правда, он просто перечисляет сочетания в лексикографическом порядке. По идее, несложно напрямую вычислять сочетание по номеру и номер по сочетанию, если заранее посчитать кусок треугольника Паскаля.

[wrest]

Пусть сочетания отсортированы лексикографически, то есть

N     K1 K2
1     01 02
2     01 03
3     01 04
4     01 05
5     01 06
...
841   21 32
842   21 33
843   21 34
844   21 35
...
1324  50 51
1325  50 52
1326  51 52

Пусть $n$ номер сочетания из списка выше.
Тогда номер первой карты
$c_1(n)=\left\lfloor52.5-\sqrt{0.25+2(1327-n)}\right\rfloor$
Номер второй карты
$c_2(n)=n+c_1(n)+\dfrac12(c_1(n)-53)(c_1(n)-52)-1326$
Наверняка там можно изящней записать всё.

Обратно (номер сочетания по входящим в него картам) тоже можно посчитать.
Сперва сортируем карты по возрастанию, т.е. если даны карты $x,y$ то $c_1=min(x,y)$ и $c_2=max(x,y)$
Ну дальше понятно: считаем смещение $r(c_1)=1327-\dfrac12(c_1-53)(c_1-52)$ где начинаются сочетания с первой картой, к нему прибавляем модуль разности т.е. $|x-y|$ получаем номер сочетания как $n(c_1,c_2)=1326-\dfrac12(c_1-53)(c_1-52)+c_2-c_1$

Ну это легко если сочетание из двух карт.
Если больше чем двух - думать надо.
Но общая тема такая, что сортируем (нумеруем) сочетания в лексикографическом порядке, перед этим в самих сочетаниях сортируя карты по возрастанию.