2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Как пронумеровать неупорядоченные выборки
Сообщение31.08.2024, 11:20 


06/07/14
14
Всем, привет!

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

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

 Профиль  
                  
 
 Re: Как пронумеровать неупорядоченные выборки
Сообщение31.08.2024, 11:42 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Как пронумеровать неупорядоченные выборки
Сообщение31.08.2024, 22:25 


05/09/16
12023
Пусть сочетания отсортированы лексикографически, то есть
Код:
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$

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: maximkarimov


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group