| Математика. Генерация номера сочетания по самому сочетанию. ID:29024 |
Пн, 6 декабря 2004 10:04 [#] [») |
|
|
Приветствую!
Использую немного измененный алгоритм генерации сочетаний, приведенный на
http://www.srcc.msu.su/num_anal/lib_na/cat/pa/pa10i.htm
Теперь интересует обратная задача.
Т.е. по виду сочетания, определить его номер.
Или другими словами. Необходим алгоритм нумерации сочетаний.
Пример.
С(13,5)=1287
Генерацию сочетаний начинаем с (1,2,3,4,5). У него будет номер 1.
Какой номер будет у сочетания (1,2,3,4,10)?
|
|
|
| Re: Математика. Генерация номера сочетания по самому сочетанию. ID:29025 ответ на 29024 |
Пн, 6 декабря 2004 13:29 («] [#] [») |
|
|
Привет,
Всего C(13;5) комбинаций.
Имеем X(i1,i2,i3,i4,i5) комбинацию.
Формула для индекса комбинации:
C (13; 5) - C (13 - i1 + 1; 5) +
+ C (13 - i1; 4) - C (13 - i2 + 1; 4) +
+ C (13 - i2; 3) - C (13 - i3 + 1; 3) +
+ C (13 - i3; 2) - C (13 - i4 + 1; 2) +
+ C (13 - i4; 1) - C (13 - i5 + 1; 1) + 1
Массив C(13;5) должен быть предопределён заранее.
Удачи,
Jack Daw
|
|
|
| Re: Математика. Генерация номера сочетания по самому сочетанию. ID:29026 ответ на 29024 |
Пн, 6 декабря 2004 13:32 («] [#] [») |
|
|
Делал что-то подобное лет 20 назад (увлекался спортлото  ). А тебе зачем, если не секрет?
|
|
|
|
| Re: Математика. Генерация номера сочетания по самому сочетанию. ID:29028 ответ на 29024 |
Пн, 6 декабря 2004 14:16 («] [#] [») |
|
|
Приветствую!
2 Grey
| Цитата: | | Делал что-то подобное лет 20 назад (увлекался спортлото Smile). А тебе зачем, если не секрет? |
Унифицировать процедуру сжатия по мастям для анализа покерных ракладов.
|
|
|
| Re: Математика. Генерация номера сочетания по самому сочетанию. ID:29029 ответ на 29024 |
Пн, 6 декабря 2004 15:22 («] [#] |
|
|
Привет, Mariner.
Боюсь, ссылку на теорию дать не смогу, так как формулу выводил сам, когда занимал подобными вопросами.
Основная идея: определить сдвиг индекса от начала, последовательно для i1, i2, итд.
Последовательность рассуждений.
Всего С(X;Y) кобминаций.
Когда значение i1 меняется с 1 на 2, то остаются такие комбинации:
2 3 4 5 6
2 3 4 5 7
.............
9 10 11 12 13
Иными словами, С(X-1;Y)
Когда значение i1 меняется 3, то остаются такие комбинации:
3 4 5 6 7
3 4 5 6 8
.............
9 10 11 12 13
Иными словами, С(X-2;Y)
Заметим, что из исходного числа элементов X вычитается значение i1-1
Итак, чтобы определить сдвиг индекса по значению первого элемента, надо из общего числа комбинаций вычесть оставшиеся
С(X;Y) + С(X - i1 + 1;Y)
Далее находим сдвиг индекса по значению второго элемента.
Отбросим все значения меньше i1, уберем 1 столбец.
. 4 5 6 7
. 4 5 6 8
.............
. 10 11 12 13
Исходные условия такие же, как и для 1-го элемента, только вместо X используем (X - i1), вместо i1 используем (i2-i1), a вместо Y используем (Y - 1),
Подставляем в формулу
С(X - i1;Y-1) + С((X -i1) - (i2-i1) + 1;Y-1) = С(X - i1;Y-1) + С(X - i2 + 1;Y-1) 'произвели сокращение в формуле
Аналогично находим сдвиг для 3, 4 и 5 элемента.
Итого:
С(X;Y) + С(X - i1 + 1;Y) +
+ С(X - i1;Y-1) + С(X - i2 + 1;Y-1) +
+ С(X - i2;Y-2) + С(X - i3 + 1;Y-2) +
+ ,,,,
+ С(X - i(y-1); 1) + С(X - i(y) + 1; 1) + 1
Удачи,
Jack Daw
P.S. Кстати, протестируй формулу на своих значениях, всё-таки давно её выводил, мало ли что.
|
|
|
