Итерация по всем подмножествам заданного размера

Question

Я знаю, что итерация по всем подмножествам набора размеров n является кошмаром исполнения и займет время O (2^n).

Как насчет итерации по всем подмножествам размера k (для (0 < = k < = n))? Это кошмар? Я знаю, что есть (n, k) = n!/k! (n - k)! возможности. Я знаю, что если k очень близко к 0 или очень близко к n, это небольшое число.

Какое худшее значение в отношении n и k? Есть ли более простой способ сказать это иначе, чем просто O (n!/K! (N - k)!)? Является ли это асимптотически меньше, чем O (n!) Или то же самое?

Answer 1

Вы хотите взломать Госпер в:

int c = (1<<k)-1; 
while (c < (1<<n)) { 
    dostuff(c); 
    int a = c&-c, b = c+a; 
    c = (c^b)/4/a|b; 
} 

Объяснение:

найти следующий номер с таким количеством бит в основном сводится к случаю чисел ровно один «блок единиц» --- номер имея кучу нулей, затем кучу единиц, затем кучу нулей снова в их двоичных разложениях.

Способ борьбы с таким числом «блоков одного» состоит в том, чтобы переместить наивысший бит слева на один и захлопнуть все остальные как можно ниже. Взлом Gosper работает, набирая самый младший бит (a), находя «высокую часть», содержащую биты, которые мы не касаемся, и «бит переноса» (b), затем создаем блок из блоков соответствующего размера, который начинается с наименее значимый бит.

Answer 2

Легко показать, что для фиксированного n, (n, k) имеет максимум на k = n/2. Если я не ошибочно использовал приближение Стерлинга, асимптотика для (n, n/2) экспоненциальна.

Для постоянных k, (n, k) является O(n^k). Имейте в виду, что комбинаторная функция симметрична, поэтому она одинакова для (n, n-k). Это многочлен, поэтому он меньше, чем O(n!).