Создание k-комбинаций лексикографически

Question

Я не знаю и не мог найти алгоритм для генерации комбинаций k элементов (например, k-подмножеств) лексикографически. Я знаю алгоритмы для генерации комбинаций n, выбирающих k, но они не генерируют k-подмножества лексикографически.

Может ли кто-нибудь помочь мне с этим или указать мне в правильном направлении?

Answer 1

Этот алгоритм в основном использует некоторые простые правила для определения следующих маркеров в комбинации: предположит, набор N размера n и незаконченное сочетание C который до сих пор заполнен с c < k элементами (поиск комбинации имеет длину = k). Теперь C[c + 1] должен находиться в диапазоне между (оба включительно) N[indexOf(C[c]) + 1] (каждый элемент должен быть выше предыдущего для обеспечения порядка) и N[k - c + 1] (есть k - (c - 1) свободные места для остальных элементов, которые должны быть выше, чем их предыдущий элемент). С помощью этого мы можем генерировать комбинации довольно легко рекурсивно:

define combinationsLex(T[] set , int k) 
    sort(set) 

    //initialize the combinations with their first element 
    for int i in [0 , length(set) - k] 
     int c_init[k] 
     c_init[0] = set[i] 

     combinationsLexRec(set , c_init , 1) 

//set is the alphabet from which the combinations are created, c is the current 
//incomplete combination and at is the position in c at which the next element will be inserted 
define combinationsLexRec(T[] set , int[] c , int at) 
    if at == length(c) 
     //do whatever you want with the combination 

    for int i in [c[at] + 1 , length(set) - c[at]] 
     int[] nc = copy(c) 
     nc[at] = set[i] 

     combinationsLexRec(set , nc , at + 1) 

Примечание:

• эта реализация предполагает arrayindices 0 на основе
• результат только лексикографический, если вход заказан как хорошо

Answer 2

Следующий алгоритм будет генерировать все комбинации элементов набора:

procedure all_combinations(S) 

    if length(S) == 0 
     return {} 
    else 
     all_comb = {} 
     x = first element of S 
     Sx = S-{x} 
     for each C in all_combinations(Sx) 
      all_comb += C 
      all_comb += {x} ∪ C 
     return all_comb 

Для множества {1,2,3}, этот алгоритм делает ...

all_combinations ({2,3})

all_combinations ({3})

all_combinations ({}), который возвращает {}

all_combinations ({3}) возвращает {{}, {3}}

all_combinations ({2,3}) возвращает {{}, {2}, {3}, {2,3}}

all_combinations ({1,2,3}) возвращает {{}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, { 1,2,3}}