Количество несмежных наборов заданного размера

Question

Если вам дан набор L={1,2,3,...,N} и целое число k, возможно ли эффективно рассчитать количество "несмежных" подмножеств размера k?Подмножество S не является смежным, если для каждого x в S ни x-1, ни x+1 не находятся в S.

Например, для L={1,2,3,4} и k=2 ответ 3, потому что у нас есть {1,3},{1,4},{2,4}.Для k=3 ответ равен нулю.

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

Answer 1

Это может совпадать с решением Win32, но я не был уверен. Поэтому я публикую это отдельно.

Примите S (n) как число несмежных подмножеств вашей последовательной последовательности размера n (то есть S (n) - это решение, которое вы ищете).

Давайте вычислим S (n + 1), значение, когда мы добавляем элемент в последовательность. Когда мы добавляем элемент k, мы увеличиваем количество несмежных подмножеств этой последовательности. Мы можем разбить эти новые подмножества на следующие категории.

• Подмножества, содержащие исключительно новый элемент, который мы добавили. Есть только один из них ({k}).
• Подмножества, к которым мы можем добавить k и сохранить наши несмежные критерии (плюс k). Мы можем добавить k к любому подмножеству, которое не содержит k-1, сохраняя при этом несмежность. Другой способ сказать, что мы можем добавить k к подмножествам, которые содержат самое большее k-2. А количество подмножеств, содержащих не более k-2, равно S (n-1).

Таким образом, число новых несмежных подмножеств, когда мы добавляем k в нашу последовательность, равно 1 + S (n-1). Другими словами, 1 + S (n-1) = S (n + 1) - S (n). Мы можем изменить эту формулу, чтобы получить S (n + 1) = 1 + S (n-1) + S (n).

Рекурсивные решения не очень полезны, поэтому мы можем попытаться обобщить их. Я не очень хорош в этом шаге, но Wolfram | Alpha равен , и мы находим, что общая формула равна следующему.

• S (n) = 1/2 * (3 * Fib (n) + Лукас (n) - 2)

Вот несколько примеров точек данных.

n | S(n)
0 | 0
1 | 1
2 | 2
3 | 4
4 | 7
5 | 12
6 | 20
7 | 33
8 | 54
9 | 88

Answer 2

Подумайте об этом следующим образом: если бы вы знали, каков ответ для набора L'={1, 2, 3, ..., N - 1}, могли бы вы использовать эту информацию для построения ответа для набора L? Идея состоит в том, что при добавлении N к L' новое решение состоит из всех подмножеств, доступных для L', плюс 1 новое подмножество для каждого из элементов L', которые меньше или равны N - 2*(k - 1), поэтому, если решение для L' имело размер V', то V решение для L будет V = V' + (N - 2*(k - 1))
Если вы поработаете немного больше, вы обнаружите, что решение может быть выражено как сумма первых N - 2k + 2 натуральных целых.

При значении, меньшем или равном N - 2*(k - 1), добавляемый новый номер N будет добавляться только к подмножествам, конечное число которых меньше или равно результату этого выражения, поскольку в элементах k должно быть новое создаваемое подмножество (включая само число N, поэтому требуется k - 1 больше) отделено друг от друга минимум двумя числами, что составляет расстояние 2*(k - 1) от числа N, и так что выражение.

Answer 3

Пусть:

S(n,k) будет набором несмежных подмножеств {1,...n} размера k

Очевидно, S(n-1,k) являетсянабор несмежных подмножеств размера k, и это подмножество S(n,k).

Кроме того, S(n-2,k-1) является набором несмежных подмножеств размера k-1, и ни один из нихподмножества включают n-1.Таким образом, мы можем безопасно добавить {n} к каждому из этих подмножеств, чтобы получить подмножества размером k.И поскольку они не включают n-1 (единственный элемент, смежный с n), они также не являются смежными.

Таким образом:

S(n,k) = S(n-1,k) U ({n} X S(n-2,k-1))

Используя некоторые действительные числа, попробуем найти для S(6,3).

S(6,3) = S(5,3) U ({6} X S(4,2))
 S(5,3) = {1,3,5}                   # Only one solution
  S(4,2) = S(3,2) U ({4} X S(2,1))
   S(3,2) = {1,3}                   # Only one solution
    S(2,1) = {1} {2}                # All sets of 1 element are non-adjacent
   {4} X S(2,1) = {1,4} {2,4}       # Add {4} to each
  S(4,2) = {1,3} {1,4} {2,4}
 {6} X S(4,2) = {1,3,6} {1,4,6} {2,4,6}
S(6,3) = {1,3,5} {1,3,6} {1,4,6} {2,4,6}

Что соответствует вашему ответу.

Теперь, чтобы вычислить число:

Пусть N(n,k) будет количеством элементов в S(n,k)

Тогда:

N(n,k) = N(n-1,k) + N(n-2,k-1)

Я еще не определил закрытую форму, но вот некоторые вычисленные значения:

 n    k=1   k=2   k=3   k=4   k=5   k=6   k=7   k=8   k=9  k=10  k=11  k=12  k=13
 1     1                                                                        
 2     2                                                                        
 3     3     1                                                                  
 4     4     3                                                                  
 5     5     6     1                                                            
 6     6    10     4                                                            
 7     7    15    10     1                                                      
 8     8    21    20     5                                                      
 9     9    28    35    15     1                                                
10    10    36    56    35     6                                                
11    11    45    84    70    21     1                                          
12    12    55   120   126    56     7                                          
13    13    66   165   210   126    28     1                                    
14    14    78   220   330   252    84     8                                    
15    15    91   286   495   462   210    36     1                              
16    16   105   364   715   792   462   120     9                              
17    17   120   455  1001  1287   924   330    45     1                        
18    18   136   560  1365  2002  1716   792   165    10                        
19    19   153   680  1820  3003  3003  1716   495    55     1                  
20    20   171   816  2380  4368  5005  3432  1287   220    11                  
21    21   190   969  3060  6188  8008  6435  3003   715    66     1            
22    22   210  1140  3876  8568 12376 11440  6435  2002   286    12            
23    23   231  1330  4845 11628 18564 19448 12870  5005  1001    78     1      
24    24   253  1540  5985 15504 27132 31824 24310 11440  3003   364    13      
25    25   276  1771  7315 20349 38760 50388 43758 24310  8008  1365    91     1
26    26   300  2024  8855 26334 54264 77520 75582 48620 19448  4368   455    14

Answer 4

Обозначим S(m,n) количество несмежных подмножеств размера m в {1,...,n}. Тогда имеет место следующее:

S(m,n) = S(m,n-1) + S(m-1,n-2)

Таким образом, можно решить это с помощью DP в O(Nk), добавив граничные условия

S(1,n) = n
S(m,1) = I(m==1)
S(m,2) = 2*I(m==1)

, где I() - функция индикатора.