CODEWITHSUNDEEP
algorithmlanguage-agnosticcombinations
Dean
Dean

Reputation: 6960

Generating k-combinations lexicographically

I'm not aware nor could I find an algorithm to generate combinations of k items (i.e. k-subsets) lexicographically. I do know algorithms to generate combinations of n choose k, but they don't generate the k-subsets lexicographically.

Can somebody help me out with this or point me in the right direction?

Upvotes: 1

Views: 1201

Answers (2)

GOPAL GUPTA
GOPAL GUPTA

Reputation: 27

The following algorithm will generate all combinations of elements of a set:

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

For the set {1,2,3}, this algorithm does…

all_combinations({2,3})

all_combinations({3})

all_combinations({}), which returns {}

all_combinations({3}) returns {{}, {3}}

all_combinations({2,3}) returns {{}, {2}, {3}, {2,3}}

all_combinations({1,2,3}) returns {{}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}}

Upvotes: 2

user4668606
user4668606

Reputation:

This algorithm basically uses some simple rules to determine the next token in the combination: assume a set N of size n and an unfinished combination C that is so far filled with c < k elements (searched combinations have length = k). Now C[c + 1] must lie in the range between (both inclusive) N[indexOf(C[c]) + 1] (each element must be higher than the previous to ensure order) and N[k - c + 1] (there are k - (c - 1) free spaces for remaining elements, which must aswell be higher than their previous element). Using this we can generate the combinations pretty easy recursively:

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)

Notes:

  • this implementation assumes 0-based arrayindices
  • the result is only ordered lexicographically if the input is ordered aswell

Upvotes: 0

Related Questions