Search code examples
javasequences

Calculate a list of possible int sequences with length K

Let's say I can have a sequence of integers, of length K. Each of those values can be any int from 1 to N. How can I calculate a list of ALL possible sequences that follow this pattern? I know that's a lot, N^K, but I plan on dealing with smaller numbers.

EDIT: In Java, but pseudo-code is fine

Solution

  • Updated to be 1 to N, instead of 0 to N-1

    Think of it as incrementing a base-N number of K digits. This makes for a simple non-recursive implementation:

    int[] seq = new int[K];
Arrays.fill(seq, 1);
OUTER: while (true) {
    System.out.println(Arrays.toString(seq));
    for (int i = K - 1; true; i--) {
        int v = seq[i] + 1;
        if (v <= N) {
            seq[i] = v;
            break;
        }
        if (i == 0)
            break OUTER;
        seq[i] = 1;
    }
}

    E.g. for K = 2 and N = 3:

    [1, 1]
[1, 2]
[1, 3]
[2, 1]
[2, 2]
[2, 3]
[3, 1]
[3, 2]
[3, 3]