Как найти число комбинаций

[nill]

Это не задача из учебника, а проблема для реально работающей программы


Есть массив из нужных комбинаций, в каждой комбинации участвует ДВА элемента, за один раз из массива берется 1 комбинация, есть 9 попыток

Нужно найти число комбинаций для каждой из попыток

1) Для первой попытки число комбинаций равно числу элементов в массиве из нужных комбинаций

2) Для второй и так далее попыток нужно делать полный перебор, то есть если в массиве из нужных комбинаций 16 элементов то сначала берется первый элемент и считается сколько нужных элементов осталось в массиве потом второй и так далее
то есть чтобы посчитать количество комбинаций при двух попытках нужно сделать 16*16 вычислений и если скажем элементов в массиве больше 1000 а попыток 9 то это 1000*1000*1000*1000*1000*1000*1000*1000*1000 вычислений и думаю ни один супер компьютер не справиться с этой задачей в реальные сроки

Отсюда вопрос существует ли какая-нибудь формула чтобы упростить эти вычисления ?

Смотрел в сторону факториала но он считается только для целых чисел и все просто посчитать только если к примеру количество нужных комбинаций в массиве равно 28 а количество разных элементов составляющих эти комбинации равно 8, то есть чтобы найти количество комбинаций при двух попытках надо 8!*6!= 420 при трех 8!*6!*4!=2520

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

[meduza]

Расставьте запятые для начала, читать невозможно. И объясните, что это за "комбинации" такие. Короче второе предложение не понятно (по крайней мере для меня).

[gris]

Я просто про факториал.
Есть формула Стирлинга. Её можно применять и для нецелых значений аргумента. То есть получается фактически "факториал" любого числа.

[nill]

meduza
запятые расставил

ну вот реальный пример

есть массив из 16 комбинаций, которые состоят из чисел от 1 до 8


1) 1 - 5
2) 1 - 6
3) 1 - 7
4) 1 - 8
5) 2 – 5
6) 2 - 6
7) 2- 7
8) 2- 8
9) 3- 5
10) 3- 6
11) 3- 7
12) 3- 8
13) 4- 5
14) 4- 6
15) 4- 7
16) 4- 8

1) число комбинаций при первой попытке равно 16

2) число комбинаций при второй попытке равно 16*9=144

Здесь очень простой случай так как при выборе любого элемента остается еще 9 возможных вариантов

Вот мне и нужна формула чтобы как то получить это число 9 не перебирая все возможные варианты (в большинстве случаев это конечно будет не целое число)

[Sonic86]

nill
Все-таки неясно, чего Вы хотите. Попробуйте подробно процедуру вытаскивания описать.

Пусть $M$ - множество комбинаций. Вам нужно определить, сколько различных девяток $(m_1,...,m_9)$ Вы можете вытащить из $M$ за 9 попыток?

-- Ср янв 13, 2010 15:31:17 --

Вот на Вашем примере. Я понял так. Взяли $M$ из 16 элементов. Вытаскиваем 1 из 16 16-ю способами. Вытащили. Осталось 15. А потом откуда взялось 9? Или 144? Вытащить 2 различных элемента из $M$ без учета порядка можно $\frac{16!}{(16-2)! \cdot 2!} = 120$-ю способами. Вытащить 2 различных элемента с учетом порядка можно $\frac{16!}{(16-2)!}=240$-ю способами. Взять 2 элемента, возможно одинаковых, без учета порядка можно $120+16=136$-ю способами. Откуда 144?

[nill]

Sonic86

Цитата:

Вытаскиваем 1 из 16 16-ю способами. Вытащили. Осталось 15

остаеться не 15 а как раз 9
то есть если убрать из массива первый элемент {1,5} то выбор вариантов где содержаться или 1 или 5 будет невозможен

и получеться остаеться еще 9 вариантов

и если считать для каждого из 16 элементов
то получаеться 1*9*16=144

Надесь теперь все понятно

[Sonic86]

nill, понятно. Попробую сформулировать.
Пусть $M_1$ - данное множество комбинаций. На $j$-и шаге выбираем некоторую пару $(a_j,b_j) \in M_{j}$ и вычисляем $M_{j+1}$. Оно равно $M_j}$ без всех пар, содержащих элементы $a_j$ или $b_j$. И пусть $M_{n+1} = \{ \}$. Тогда надо найти $|M_1| \cdot ... \cdot |M_k|, 1 < k \leq n$ ($k$ - число попыток)(оценить сверху, снизу). Причем ее надо найти для произвольной последовательности вытаскиваемых пар $\{ (a_j,b_j) \}_{j=1}^n$.

Если да, то навскидку: задачка сложная, надо хотя бы предполагать, как может быть устроено $M$, иначе - перебор. Хотя оценки сверху сниху можно попытаться найти.
Вот у Вас в примере $M = \{1,2,3,4 \} \times \{ 5,6,7,8\}$ - декартово произведение. Вот если бы в общем случае было $M = \{ a_1,...a_n\} \times \{b_1,...,b_m \}$, причем $m \geq n$. Тогда $|M_j| = (n-(j-1))(m-(j-1))$ и тогда для $k$ попыток число комбинаций будет равно $\frac{n!}{(n-k+1)!} \cdot \frac{m!}{(m-k+1)!}$. Причем это не зависит от последовательности $(a_j, b_j)$. В примере $n=m=4, k=2$.

Как у Вас устроено $M$ в общем случае?

Так же несложно подсчитать число комбинаций в случае, когда $M$ является объединением декартовых произведений с разными элементами. Можно попытаться придумать какой-то оптимальный перебор, чтобы число комбинаций минимизировать...

[nill]

M устроено случайным образом

Ну мне хотябы получить какую то формулу для того случая что я привел где 16 элементов в массиве, чтобы иметь точку от которой можно отталкиваться.

вот по вашей формуле где n=m=4, k=2 у меня получается 16

(24/(4-2+1)!)=(24/6)=4
4*4=16

а должно быть 144
k ведь равно 2, а это значит тут должны считаться комбинации для двух попыток

если конечно я все правильно понял

[Sonic86]

Блин, неправильно формулу написал. Правильно так:
$\frac{n!}{(n-k)!} \cdot \frac{m!}{(m-k)!}$. Извините Вы рассуждения посмотрите.
Если $M$ устроено случайным образом, то плохо. Число комбинаций тогда зависит от цепочки $\{ (a_j, b_j) \}_{j=1}^n$ и тогда надо Вам сказать, что дальше сделать. Минимизировать число комбинаций? Или найти среднее число комбинаций и отклонение от него? Или найти наихудшую оценку - максимально худшее число комбинаций? Худшую оценку можно опять же найти из этой формулы. То есть если в $M$ первых элементов пары всего $n$ штук, а вторых элементов пары всего $m$ штук, то засунув $M$ в соответствующее декартово произведение получаем, что число комбинаций не больше $\frac{n!}{(n-k)!} \cdot \frac{m!}{(m-k)!}$. Оценка, ессно, очень грубая.

[TOTAL]

nill в сообщении #280040 писал(а):

есть массив из 16 комбинаций

Что такое комбинация?

[Sonic86]

TOTAL писал(а):

Что такое комбинация?

Он имеет виду пары $(a,b) \in M, a \in A, b \in B$ и, видимо, $A \cap B = \{ \}$, хотя насчет последнего соотношения точно не уверен.

[maxal]

Если я правильно понял, то есть двудольный граф (доли образуют соответственно первые и вторые элементы комбинаций, ребра - сами комбинации) и нужно вычислить в нём количество максимальных паросочетаний.
Это сложная проблема, хотя и аппроксимируемая для двудольных графов:
http://en.wikipedia.org/wiki/Perfect_ma ... g_problems

[nill]

Sonic86
теперь все сходиться
правда работает в очень редких случаях

Вообще мне конечно надо наиболее приблизительное число к количеству ВСЕХ возможных комбинаций, вот такая цель

Я можно сказать решил эту проблему для двух попыток, там просто считаю что то типо веса для каждой пары и потом считаю количество комбинаций для каждого веса и умножаю на количество пар с анологичным весом
то есть все очень просто и быстро

А когда три попытки то чтобы получить реальное число комбинаций нужно делать полный расчет для каждой пары иначе цифры получаються неточными

maxal
а если на русском то искать статьи про двудольные графы ?

[maxal]

nill в сообщении #280404 писал(а):

а если на русском то искать статьи про двудольные графы ?

гугл - ваш друк

-- Thu Jan 14, 2010 23:26:30 --

nill в сообщении #280404 писал(а):

Вообще мне конечно надо наиболее приблизительное число к количеству ВСЕХ возможных комбинаций, вот такая цель

Вот как раз диссер 2009 года по этой теме с детальным изложением теории и алгоритмов (но на английском):
Approximately Counting Perfect And General Matchings in Bipartite Graphs

[nill]

maxal
а если элементы массива будут состоять не из двух чисел а из четырех ?
и иметь вид
{1, 3, 5, 6}
{1, 3, 5, 7}
и так далее

и получаеться это наверно не двудольный а четырех дольный граф

алгоритмы в дисертации подходят для поиска количества комбинаций в этом случае?