Комбинаторика. Подсчет вхождений ключа во всех комбинациях

[wvxvw]

Собственно, нужно посчитать сколько раз каждый из ключей может попасться во всех возможных комбинациях из заданой групы.
Например, из группы 1, 2, 3, 4 нужно получить все возможные уникальные комбинации, в которых последовательность не важна, а повторение запрещено.
Т.е. получим:

[1, 2, 3, 4] х 2
---------
1, 2
1, 3
1, 4
2, 3
2, 4
3, 4
----
Комбинаций: 6
вхождений каждого ключа: 3

Для [1, 2, 3, 4, 5] х 2
получим:
Комбинаций: 10
вхождений каждого ключа: 4

Для [1, 2, 3, 4, 5] х 3
получим:
Комбинаций: 10
вхождений каждого ключа: 6

И т.д.
Должна быть какая-то простая формула подсчета количества ключей, но, чего-то википедия не помогла...

[Kuruki]

Опытным путем я получил:
Число попаданий каждого ключа = число комбов / кол-во ключей * длина комбо.

6 / 4 * 2 = 3;
10 / 5 * 2 = 4;
10 / 5 * 3 = 6;

Только это надо проверить еще на паре примеров :)

[alexcon314]

бином Ньютона (http://ru.wikipedia.org/wiki/Бином_Ньютона)
Берем формулу биномиальных коэффициентов (та, что с факториалами, сразу вверху страницы, аттачить картинку лень)
n - количество элементовв наборе
m - количество элементов в комбинации.
для первого примера n=4, m=2
для второго примера n=5, m=2
для третьего примера n=5, m=3

число вхождений каждого ключа - эмм .. думаю догадаешься как считать :).

[Котяра]

"Подумаешь, бином Ньютона!" (с) М.Булгаков.Мастер и Маргарита

[wvxvw]

Спасибо. Я формулу знал... но как-то с ключами не мог сообразить...
Вобщем, теперь разобрался, если кому интересно, если формула записана так:
n! / (r! * (n - r)!)
то, количество ключей:
(n - 1)! / ((r - 1)! * (n - r)!)

Но, как оказалось, это не помогает решить изначальную задачу :)
А задача, на самом деле была найти все возможные уникальные комбинации... чего-то у меня только каие-то бесконечные рекурсии получаются... :(

[Kuruki]

А задача, на самом деле была найти все возможные уникальные комбинации... чего-то у меня только каие-то бесконечные рекурсии получаются... :(
А смысл? Всеравно придется циклом пробегаться по всем комбинациям, ведь формула не сможет вернуть массив

[wvxvw]

Даже если есть вариант сначала найти все пермутации, а потом отфильтровать только уникальные комбинации - это было бы мега круто :) Т.как единственное решение которое я нашел - с использованием рекурсии для нахождения пермутаций. А это очень сильно уменьшает производительность...

[bicubic_bublic]

цэ из эн по ка!

[GentleFLASH]

wvxvw можно поинтересоваться - тебе для каких целей? Ну в плане чтобы массив массивов возвращало или массив чисел? Если непонятно, то вот пример:

Для массива [1, 2, 3]:
0: [1,2,3]
1: [1,3,2]
2: [2,3,1]
3: [2,1,3]
4: [3,1,2]
5: [3,2,1]

Для числа 123:
0: 123
1: 132
2: 231
3: 213
4: 312
5: 321

по времени: для [1,2,3,4,5,6,7,8] около 930мс, для 12345678 около 77мс. С каждым шагом увеличивается примерно в 10 раз. Код предоставить? ;)

[wvxvw]

Не, про пермутации я загнул :) На самом деле нужны только уникальные комбинации (т.е. комбинации, в которых порядок чисел не важен).
И уже вроде нашелся способ (помогли, сам бы ни в жизнь не сообразил). И по производительности все-таки не такой жестокий :) Завтра на свежую голову опишу.

[GentleFLASH]

wvxvw, ок, будем ждать. Как получиться - приведи примеры по времени пожалуйста, тоже интересно стало)