按词典顺序生成k组合 [英] Generating k-combinations lexicographically

问题描述

我不知道，也找不到算法来按字典顺序生成k个项(即k个子集)的组合.我确实知道生成n个选择k的组合的算法，但是它们不按字典顺序生成k个子集.

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?

推荐答案

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

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

对于集合{1,2,3}，此算法可以…

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

all_combinations({2,3})

all_combinations({2,3})

all_combinations({3})

all_combinations({3})

all_combinations({})，返回{}

all_combinations({}), which returns {}

all_combinations({3})返回{{}，{3}}

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

all_combinations({2,3})返回{{}，{2}，{3}，{2,3}}

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

all_combinations({1,2,3})返回{{}，{1}，{2}，{1,2}，{3}，{1,3}，{2,3}，{1 ，2,3}}

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

这篇关于按词典顺序生成k组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！