Search code examples
algorithmcomputer-sciencecombinatoricsset-theory

Determine all consecutive subsets of the set {1,2,3,…,n}. The subsets should have at least 2 elements

I need to partition a set S={1, 2, 3, … , n} consisting of consecutive numbers such that each subset has has at least 2 elements (rule 1) and it consists of consecutive numbers (rule 2).

The rules are:

  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.

Examples:

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

I didn't write them down here but there are 55 subset combinations for n = 11 and 89 subset combinations for n = 12.

I need to write a Visual Basic code listing all possible subset groups for n. I have been thinking on the solution for days but it seems that the solution of the problem is beyond my capacity. The number of required nested loops increases with n and I could not figure out how to program the nested loops with increasing number. Any help will be greatly appreciated.

After some research, I found out this is the problem of "compositions of n with all parts >1" and the total number of possible compositions are Fibonacci numbers (Fn-1 for n).

Solution

  • We already know the answer for these cases (as you wrote in your examples):

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

    For n=5:

    • You can partition from 2: 1 2 - 3 4 5. This is like dividing the 5 member set into two sets, first one n=2, and second one n=3. We can now continue dividing each half, but we already know the solutions when n=2 and n=3!
    • You can partition from 3: 1 2 3 - 4 5. This is like dividing the 5 member set into two sets, first one n=3, and second one n=2. We can now continue dividing each half, but we already know the solution when n=2 and n=3!

    For n=6:

    • You can partition into two sets from 2: 1 2 - 3 4 5 6. This is like dividing the 6 member set into two sets, first one n=2, and second one n=4. We can now continue dividing each half, but we already know the solution when n=2. Solve the second half by assuming n=4!
    • You can partition into two sets from 3: 1 2 3 - 4 5 6. This is like dividing the 6 member set into two sets, first one n=3, and second one n=3, We can now continue dividing each half, but we already know the solution when n=3 and n=3!
    • You can partition into two sets from 3: 1 2 3 4 - 5 6. This is like dividing the 6 member set into two sets, first one n=4, and second one n=2, We can now continue dividing each half. Solve the first half by setting n=4. For the second half, we already know the solution when n=2!

    This is a simple recursion relationship. The general case:

    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)

    ---

    Another perhaps harder solution is to assume we are dividing the numbers 1 to n into n sections, where the length of each section can be either 0, 2, or a number greater than 2. In other words let xi be the length of each section:

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

    This is a system of linear non-equalities can can be solved by methods described here.