Математика. Генерация номера сочетания по самому сочетанию.

Приветствую!

Использую немного измененный алгоритм генерации сочетаний, приведенный на
[Зарегистрироваться?]

Теперь интересует обратная задача.
Т.е. по виду сочетания, определить его номер.

Или другими словами. Необходим алгоритм нумерации сочетаний.
Пример.
С(13,5)=1287
Генерацию сочетаний начинаем с (1,2,3,4,5). У него будет номер 1.
Какой номер будет у сочетания (1,2,3,4,10)?

__________________
Mariner

Западное полушарие Марса рассечено на протяжении 4 000 км вдоль экватора рифтовыми долинами Маринер - крупнейшим поясом разломов на планете.

Привет,

Всего 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

Делал что-то подобное лет 20 назад (увлекался спортлото ). А тебе зачем, если не секрет?

__________________
Arthur Grey

Приветствую!

2 JackDaw

Огромное спасибо за формулу!

Еще бы ссылочку на источник с теорией, для полного понимания.

Нашел пока только вот это
[Зарегистрироваться?] tions1-2004
но пока не смог разобраться в определении num().

__________________
Mariner

Западное полушарие Марса рассечено на протяжении 4 000 км вдоль экватора рифтовыми долинами Маринер - крупнейшим поясом разломов на планете.

Приветствую!

2 Grey
Унифицировать процедуру сжатия по мастям для анализа покерных ракладов.

__________________
Mariner

Западное полушарие Марса рассечено на протяжении 4 000 км вдоль экватора рифтовыми долинами Маринер - крупнейшим поясом разломов на планете.

Привет, 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. Кстати, протестируй формулу на своих значениях, всё-таки давно её выводил, мало ли что.