c++ - 提取所有可能的有序子集

Question

我有一组元素，我想从中提取有序子集。我所说的有序子集的意思是我无法切换集合内的元素。我举了三个例子来展示我如何解决这个问题。

• 如何递归提取这些子集？
• 您有什么伪代码吗？
• { . } = 子集

---

示例 1

令S = {f1,f2,f3}为由3个元素组成的集合。我想提取所有可能的有序子集，如下所示:

-{f1},{f2},{f3} // {f1} is a subset, {f2} is a subset etc.
-{f1,f2},{f3} // {f1,f2} form a subset and {f3} is also a subset
-{f1},{f2,f3} // {f1} is a subset and {f2,f3} form a subset 

---

示例 2

让S = {f1,f2,f3,f4}设置为由4个元素组成。

可能的有序子集:

-{f1},{f2},{f3},{f4}
-{f1,f2},{f3,f4}
-{f1},{f2,f3},{f4}
-{f1},{f2},{f3,f4}
-{f1,f2,f3}{f4}
-{f1},{f2,f3,f4}
-{f1,f2},{f3},{f4}
-{f1,f2,f3,f4}

---

示例 3

让S = {f1,f2,f3,f4,f5}设置为由5个元素组成。

可能的有序子集:

-{f1},{f2},{f3},{f4},{f5}
-{f1,f2},{f3},{f4},{f5}
-{f1},{f2,f3},{f4},{f5}
-{f1},{f2},{f3,f4},{f5}
-{f1},{f2},{f3},{f4,f5}
-{f1,f2},{f3,f4},{f5}
-{f1},{f2,f3},{f4,f5}
-{f1,f2,f3},{f4,f5}
-{f1,f2,f3},{f4},{f5}
-{f1},{f2,f3,f4},{f5}
-{f1},{f2},{f3,f4,f5}
-{f1,f2},{f3,f4,f5}
-{f1,f2,f3,f4}{f5}
-{f1},{f2,f3,f4,f5}
- etc...

Answer 1

如果数组包含该集合，请修改该数组，使每个元素之间有一个空格。该空间是为分区保留的。采用任何命名约定。 0 表示不分区，而 1 表示分区。现在遍历数组以递归方式在分区中添加 1 或 0。可以生成所有可能的组合。

以示例 1 为例:

S = {f1,f2,f3}
S'= {f1,0,f2,0,f3}

所以子集将是:

{f1,0,f2,0,f3}, {f1,0,f2,1,f3}, {f1,1,f2,0,f3}, {f1,1,f2,1,f3}

等同于:

{f1,f2,f3}, {{f1,f2},{f3}}, {{f1},{f2,f3}}, {{f1},{f2},{f3}}

如果不想让原始集合出现在所有子集的集合中，就不要考虑每个分区都包含0的状态。