Добрый день всем присутствующим!
Предположим, есть некое множество N элементов {1,2,3,...N}
Нужно определить количество всевозможных не повторяющихся наборов по M элементов. К примеру, для M=4 {{1,2,3,4},{2,4,5,6},{7,8,4,9}...}
В этом случае задача решается просто - это классический случай, количество сочетаний без повторений. Немного усложним задачу - нужно определить количество всевозможных наборов по M элементов, в которых не повторяется K элементов.
То есть, при K=M задача вырождается в предыдущую; при K=1 нам необходимо посчитать множества, состоящие из полностью различных элементов {{1,2,3,4},{5,6,7,8},{12,9,30,10},...}; при K=2 нам подходят все наборы, в которых повторяется не более одного элемента {{1,2,3,4},{1,5,6,7},{2,5,9,10},...} и т.д.
В самом идеальном случае хотелось бы получить быстрый линейный алгоритм перебора таких множеств.
Попробую еще добавить информации.
Допустим у нас есть множество из N элементов, из которого нужно выбирать 4 элементные выборки.
Выборок, в которых ни один элемент не пересекается будет, по понятным причинам N/4
Выборки, в которых повторяется не более одного элемента можно посчитать эмпирически:
N кол-во возможных выборок
5 1
6 1
7 2
8 2
9 3
10 5
11 5
12 6
13 8
...
Выборки, в которых повторяется не более двух элементов:
N кол-во выборок
5 1
6 3
7 7
8 10
9 13
10 18
11 27
12 37
13 50
14 65
15 81
16 102
17 127
18 149
19 185
20 212
...
Для 3 повторяющихся элементов, по понятным причинам, количество будет равно количеству сочетаний из 10 по 4 без повторений а для 4 - количеству сочетаний с повторениями.
Вопрос - можно ли как то составить универсальную формулу расчета данного числа или задача нетривиальна по сути?
Предположим, есть некое множество N элементов {1,2,3,...N}
Нужно определить количество всевозможных не повторяющихся наборов по M элементов. К примеру, для M=4 {{1,2,3,4},{2,4,5,6},{7,8,4,9}...}
В этом случае задача решается просто - это классический случай, количество сочетаний без повторений. Немного усложним задачу - нужно определить количество всевозможных наборов по M элементов, в которых не повторяется K элементов.
То есть, при K=M задача вырождается в предыдущую; при K=1 нам необходимо посчитать множества, состоящие из полностью различных элементов {{1,2,3,4},{5,6,7,8},{12,9,30,10},...}; при K=2 нам подходят все наборы, в которых повторяется не более одного элемента {{1,2,3,4},{1,5,6,7},{2,5,9,10},...} и т.д.
В самом идеальном случае хотелось бы получить быстрый линейный алгоритм перебора таких множеств.
Попробую еще добавить информации.
Допустим у нас есть множество из N элементов, из которого нужно выбирать 4 элементные выборки.
Выборок, в которых ни один элемент не пересекается будет, по понятным причинам N/4
Выборки, в которых повторяется не более одного элемента можно посчитать эмпирически:
N кол-во возможных выборок
5 1
6 1
7 2
8 2
9 3
10 5
11 5
12 6
13 8
...
Выборки, в которых повторяется не более двух элементов:
N кол-во выборок
5 1
6 3
7 7
8 10
9 13
10 18
11 27
12 37
13 50
14 65
15 81
16 102
17 127
18 149
19 185
20 212
...
Для 3 повторяющихся элементов, по понятным причинам, количество будет равно количеству сочетаний из 10 по 4 без повторений а для 4 - количеству сочетаний с повторениями.
Вопрос - можно ли как то составить универсальную формулу расчета данного числа или задача нетривиальна по сути?
