Counting number of sequences

[Shahabonweb]

Hi.

I am trying to make a program which asks the user to enter two numbers n and k and then counts the number of all possible sequences of k-terms in the set {1,2,3...n} which have the following properties:
1. They are in ascending order.
2. The differences between any two successive numbers is among at most any two numbers, where those two numbers vary from sequence to sequence.

For example, for n=5, k=3, every collection of 3 numbers in {1,2,3,4,5} gives a desired sequence of 3-terms and so the program should output 10. Moreover it would be helpful if the program could write these sequences to a text file.

Any help will be appreciated. On putting n=5,k=3 answer should be 10 but my code is outputting 12.
Thanks for your time.

[Gaminic]

Your example isn't really an example and it doesn't explain much. Best I could figure was that you're looking for the Combinations (http://en.wikipedia.org/wiki/Combination), but that doesn't follow suit with your two properties.

So, trying to rephrase it to see if I understood correctly:
From a series of numbers [1...n], you want to pick k unique numbers so that when sorted in ascending order, t₂ - t₁ <= 3?

If so, then you've picked a terrible example, as for (5, 3), all combinations fit, as the maximum distance is (1->4).

A simple search tree algorithm should suffice.

Given (n, k), say we are choosing the i'th number (i = 1 -> k). The bounds are easy to find:
T(i-1) < T(i) < min(n-k+i; T(i-1)+4),
considering we only move forward (property 1), there can only be 2 numbers between T(i-1) and T(i) (property 2) and we still need to select (k-i) numbers after T(i), without exceeding n.

A simple recursion or loop should be able to search this efficiently enough for reasonable ranges of (n, k), as the number of possibilities for each term T(i) can't exceed 3 (except for T(1)).

Basic structure of the recursive program:

void setNextNumber(int i, int min, int max, int& count, std::vector<int>& T) {
    if (i > k) { ++count; return; } // Full sequence generated: increase counter and quit.
    for (int j = min+1; j < max; ++j) { // Loop over all possibilities of T(i)
        T[i] = j;
        setNextNumber(i+1, T[i], max(T[i]+4, n-k+i), count, T);
    }
}

I've assumed that 'n' and 'k' are known in this scope, so you don't have to pass them along as they don't change anyway. I'm not sure if there's a standard max() function, but it should be easy enough to find or write.

If you don't know how vectors work: the same can be done with an array. Just make sure it is of size 'k' and that you can pass it by reference (or as a pointer).

[Gaminic]

Forgot to mention: to start the algorithm, you'd have to call it with the bounds of the first term, being min=1 and max = n-k+i.

[Shahabonweb]

Hmm...I dont think I was very clear. I want to count the number of "progressions" where a progression is defined as a set of k distinct numbers x_1,x_2,...x_k from the set {1,2,...n} where the number of elements in the set {x_{i+1}-x_i :i=1,2...n-1} is at most 2. Note that I am not saying that x_{i+1}-x_i <=2, rather that the number of such differences are at most 2.

For example for n=10, k=4 an instance of such a sequence would be 1,3,4,6 because the successive differences, viz, 3-1,4-3,6-4 are among at most two numbers 1 and 2. Further note that every arithmetic progression of k terms automatically qualifies because the number of difference is 1 which is less then at most 2.

Another example for n=10, k=3. Here some progressions:
5, 9, 10; 1, 2, 7; 1, 6, 7; 2, 3, 8; 2, 7, 8.

Hope it is clear now.

[Gaminic]

So, for example, n=10, k=5, a valid sequence would be:
1, 4, 5, 8, because the difference between any number and the next is either 1 or 3, while the following sequence is invalid:
1, 4, 5, 9, because the difference between any two numbers is any of {1, 3, 4}, which is a set with more than 2 numbers?

Well, then your examples are definitely badly chosen. Why bother with the k = 3 case? Any combination for k = 3 will have at most 2 different differences, because there are only 2 differences.

For any k > 3, the problem becomes a bit harder.

a) The first number is still free between [1, n-k].
b) The second number is free between [T(1), n-k+1].
c) The third number is free between [T(2), n-k+2].
d) For any number beyond the 3rd, it depends:
   d1) If ANY (j, y) exists such that (T(j)-T(j-1) != T(y) - T(y-1)), then T(i) is limited to T(i-1) + (T(j)-T(j-1) OR T(i-1) + (T(y)-T(y-1)).
   d2) Else, T(i) is limited between [T(i-1), n-k+i].

You'll have to keep track of whether there are 2 different differences already. This isn't too hard; just keep an array of 2 initially set to 0 (error value, as the difference can never be 0). Set the first difference to T(2)-T(1). Each time a number is chosen, see if T(i)-T(i-1) == D[0]. If not, set D1 := T(i) - T(i-1), and from that point on the sequence is strongly limited in options.

The real problem is knowing when to unset the value D[1]. At some point, the earlier numbers in the sequence will change and at some point, the 2nd (and first, but that one is easy to check) difference will change, making the range completely open again.

So, in summary:
a) Starting from the algorithm in my previous post,
b) Use the recursion until two unique differences are set,
c) Keep track of the differences, as well as the terms that set the difference.
d) Use a slightly adapted version of the algorithm: rather than ]min, max[, you now have {option1, option2}, calculated as T(i-1) + D[0] and T(i-1) + D[1].
e) Make sure that the loop that set the differences will also unset (or change) the difference when its branch has ended.

Not too difficult, but it'll take some work to get it somewhat clean and readable.