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