subset - 在不打乱顺序的情况下生成子集

Question

给定一组字母 S = { a, b, c, d, e}

如果输入 k = 3，我如何生成以下子集？

abc abd abe acd ace ade bcd bce bde cde

其中子集不违反 S 中的字母顺序。此类问题的名称是什么，解决方案是什么？

Answer 1

1. 考虑一个由 k 个 1 和 (|S|-k) 个 0 组成的具有 5 个位置（或与 S 中的字符一样多的位置）的二进制字符串。
2. 生成上述字符串的所有 (|S|! / (k! * (|S|-k)!)) 排列。
3. 现在输出对应于 1 的字符。这不会违反 S 中的字符顺序。