确定集合 {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 的增加而增加，我无法弄清楚如何随着数量的增加对嵌套循环进行编程。任何帮助将不胜感激。

经过一番研究，我发现这是"compositions of n with all parts >1"的问题，可能组合的总数是斐波那契数（Fn-1代表n）。

Answer 1

我对你的回答是尝试提出给定模式的递归关系。递归思考。我怎样才能把这个问题分解成更小的子问题，直到达到最小的问题。解决那个最小的问题。在解决了那个最小的问题之后，想想归纳法。假设第 n 步是什么以及您将如何到达第 (n+1) 步。尝试解决第 (n+1) 步。一旦你对给定的模式提出了递归关系，思考如何递归地解决这个模式应该不会太困难。与其尝试使用嵌套循环，这种方法可能更直观。

Answer 2

我们已经知道这些情况的答案（如您在示例中所写）：

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 to n 分成 n 个部分，其中每个部分的长度可以是 0、2 ，或大于 2 的数字。换句话说，让 xi 成为每个部分的长度：

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

这是一个线性非等式系统，可以通过 here.

中描述的方法求解