algorithm - 按字典顺序生成 k 组合

Question

我不知道也找不到一种算法来按字典顺序生成 k 个项目(即 k 个子集)的组合。我知道生成 n 选择 k 组合的算法，但它们不会按字典顺序生成 k 子集。

有人可以帮我解决这个问题或为我指明正确的方向吗？

Answer 1

以下算法将生成集合元素的所有组合:

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}，这个算法做...

所有组合({2,3})

所有组合({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}