algorithm - 确定集合 {1,2,3,…,n} 的所有连续子集。子集应该至少有 2 个元素

Question

我需要划分一个由连续数字组成的集合 S={1, 2, 3, … , n} 使得每个子集至少有 2 个元素(规则 1)并且它包含连续数字(规则 2)。

规则是:

1. Each subset has at least two elements.

2. All elements of all subsets are consecutive.

3. All elements of S are included in the partition.

例子:

There is 1 subset for n = 2: 
1 2
There is 1 subset for n = 3:  
1 2 3   
There are 2 subset combinations for n = 4:
1 2 3 4
1 2 - 3 4
There are 3 subset combinations for n = 5:
1 2 3 4 5
1 2 - 3 4 5
1 2 3 - 4 5
There are 5 subset combinations for n = 6:
1 2 3 4 5 6
1 2 - 3 4 5 6
1 2 3 - 4 5 6
1 2 3 4 - 5 6
1 2 - 3 4 - 5 6
There are 8 subset combinations for n = 7:
1 2 3 4 5 6 7
1 2 - 3 4 5 6 7
1 2 3 - 4 5 6 7
1 2 3 4 - 5 6 7
1 2 3 4 5 - 6 7
1 2 - 3 4 - 5 6 7
1 2 - 3 4 5 - 6 7
1 2 3 - 4 5 - 6 7
There are 13 subset combinations for n = 8:
1 2 3 4 5 6 7 8
1 2 - 3 4 5 6 7 8
1 2 3 - 4 5 6 7 8
1 2 3 4 - 5 6 7 8
1 2 3 4 5 - 6 7 8
1 2 3 4 5 6 - 7 8
1 2 - 3 4 - 5 6 7 8
1 2 - 3 4 5 - 6 7 8
1 2 - 3 4 5 6 - 7 8
1 2 3 - 4 5 - 6 7 8 
1 2 3 - 4 5 6 - 7 8
1 2 3 4 - 5 6 - 7 8
1 2 - 3 4 - 5 6 - 7 8
There are 21 subset combinations for n = 9:
1 2 3 4 5 6 7 8 9
1 2 - 3 4 5 6 7 8 9
1 2 3 - 4 5 6 7 8 9
1 2 3 4 - 5 6 7 8 9
1 2 3 4 5 - 6 7 8 9
1 2 3 4 5 6 - 7 8 9
1 2 3 4 5 6 7 - 8 9
1 2 - 3 4 - 5 6 7 8 9
1 2 - 3 4 5 - 6 7 8 9
1 2 - 3 4 5 6 - 6 7 9
1 2 - 3 4 5 6 7 - 8 9
1 2 3 - 4 5 - 6 7 8 9 
1 2 3 - 4 5 6 - 7 8 9
1 2 3 - 4 5 6 7 - 8 9
1 2 3 4 - 5 6 - 7 8 9
1 2 3 4 - 5 6 7 - 8 9
1 2 3 4 5 - 6 7 - 8 9
1 2 - 3 4 - 5 6 - 7 8 9
1 2 - 3 4 - 5 6 7 - 8 9
1 2 - 3 4 5 - 6 7 - 8 9
1 2 3 - 4 5 - 6 7 - 8 9
There are 34 subset combinations for n = 10:
1 2 3 4 5 6 7 8 9 10
1 2 - 3 4 5 6 7 8 9 10
1 2 3 - 4 5 6 7 8 9 10
1 2 3 4 - 5 6 7 8 9 10
1 2 3 4 5 - 6 7 8 9 10
1 2 3 4 5 6 - 7 8 9 10
1 2 3 4 5 6 7 - 8 9 10
1 2 3 4 5 6 7 8 - 9 10
1 2 - 3 4 - 5 6 7 8 9 10
1 2 - 3 4 5 - 6 7 8 9 10
1 2 - 3 4 5 6 - 6 7 9 10
1 2 - 3 4 5 6 7 - 8 9 10
1 2 - 3 4 5 6 7 8 - 9 10
1 2 3 - 4 5 - 6 7 8 9 10
1 2 3 - 4 5 6 - 7 8 9 10
1 2 3 - 4 5 6 7 - 8 9 10
1 2 3 - 4 5 6 7 8 - 9 10
1 2 3 4 - 5 6 - 7 8 9 10
1 2 3 4 - 5 6 7 - 8 9 10
1 2 3 4 - 5 6 7 8 - 9 10
1 2 3 4 5 - 6 7 - 8 9 10
1 2 3 4 5 - 6 7 8 - 9 10
1 2 3 4 5 6 - 7 8 - 9 10
1 2 - 3 4 - 5 6 - 7 8 9 10
1 2 - 3 4 - 5 6 7 - 8 9 10
1 2 - 3 4 - 5 6 7 8 - 9 10
1 2 - 3 4 5 - 6 7 - 8 9 10
1 2 - 3 4 5 - 6 7 8 - 9 10
1 2 - 3 4 5 6 - 7 8 - 9 10
1 2 3 - 4 5 - 6 7 - 8 9 10
1 2 3 - 4 5 - 6 7 8 - 9 10
1 2 3 - 4 5 6 - 7 8 - 9 10
1 2 3 4 - 5 6 - 7 8 - 9 10
1 2 - 3 4 - 5 6 - 7 8 - 9 10

我没有在这里写下来，但是 n = 11 有 55 个子集组合，n = 12 有 89 个子集组合。

我需要编写一个 Visual Basic 代码，列出 n 的所有可能的子集组。几天来我一直在思考解决方案，但似乎问题的解决超出了我的能力范围。所需的嵌套循环的数量随着 n 的增加而增加，我无法弄清楚如何随着数量的增加对嵌套循环进行编程。任何帮助将不胜感激。

经过一些研究，我发现这是“n 的所有部分 >1 的组合”的问题，可能组合的总数是斐波那契数(Fn-1 代表 n)。

Answer 1

我们已经知道这些情况的答案(如您在示例中所写):

1. n=2
2. n=3
3. n=4

对于 n=5:

• 您可以从 2: 1 2 - 3 4 5 进行划分。这就像将 5 个成员集分成两组，第一个 n=2，第二个 n=3。我们现在可以继续划分每一半，但我们已经知道 n=2 和 n=3 时的解决方案!
• 您可以从 3 进行划分:1 2 3 - 4 5。这就像将 5 个成员集分成两组，第一个 n=3，第二个 n=2。我们现在可以继续划分每一半，但我们已经知道 n=2 和 n=3 时的解决方案!

对于 n=6:

• 您可以从 2 分成两组:1 2 - 3 4 5 6。这就像将 6 个成员的集合分成两组，第一个 n=2，第二个 n=4。我们现在可以继续划分每一半，但我们已经知道 n=2 时的解决方案。假设 n=4 求解后半部分!
• 你可以从3分成两组:1 2 3 - 4 5 6。这就像把6个成员的集合分成两组，第一组n=3，第二组n=3，我们现在可以继续划分每一半，但我们已经知道当 n=3 和 n=3 时的解决方案!
• 你可以从3分成两组:1 2 3 4 - 5 6。这就像把6个成员的集合分成两组，第一组n=4，第二组n=2，我们现在可以继续划分每一半。通过设置 n=4 求解上半部分。对于后半部分，我们已经知道了当n=2时的解法!

这是一个简单的递归关系。一般情况:

Partition (S): (where |S|>4)
- For i from 2 to |S|-2, partition the given set into two halves: s1 and s2 from i (s1={1,...,i}, s2={i+1,...,n}), and print the two subsets as a solution.
- Recursively continue for each half by calling Partition(s1) and Partition(s2)

---

另一个可能更难的解决方案是假设我们将数字 1 到 n 分成 n 部分，其中每个部分的长度可以是 0、2 或大于 2 的数字。换句话说，让 xi 成为每个部分的长度:

x1 + x2 + ... xn = n, where the range of xi is: {0} + [2,n]

这是一个线性非等式系统，可以通过描述的方法解决here .