计算长度为 K 的可能的 int 序列列表

Question

假设我可以有一个长度为 K 的整数序列。这些值中的每一个都可以是从 1 到 N 的任何整数。我如何计算出遵循此模式的所有可能序列的列表？我知道很多，N^K，但我打算处理更小的数字。

编辑： 在Java中，但伪代码很好

Answer 1

更新为 1 到 N，而不是 0 到 N-1

可以将其视为以 N 为基数递增的 K 位数字。这使得一个简单的非递归实现成为可能：

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;
    }
}

例如对于 K = 2 和 N = 3：

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

Answer 2

这是计算机科学某些领域的常见问题。 Donald Knuth 的 The Art of Computer Programming 是此类问题解决方案的一个很好的参考。他在本书的第 7.2.1.1 节中解决了生成所有 n 元组的这个特殊问题。可以找到包含此部分的本书部分的草稿（PDF 格式）here。

书中讨论了多种解决方案，哪种解决方案最好取决于您的具体情况。我在这里给出的答案对应于 Knuth 的第一个解决方案。他以比您的具体问题更笼统的形式给出了它，因此我会根据您的具体要求对其进行调整。我把你的 n 和 k 调换一下，这样 n 是序列的长度， k 是你想使用的最大整数，而不是存储所有的n 元组，我使用访问者模式来访问每个 n 元组。如果你想存储所有访问者，你可以实现访问者存储每个访问的 n 元组的副本。

我没有测试过这个，但即使其中有一些错误，我想你也会明白的。

public interface Visitor {
    void visit(int[] nTuple);
}

public void generateAndVisitNTuples(int n, int k, Visitor v) {
    int[] nTuple = new int[n];
    // initialize each digit to one
    for (int i = 0; i < n; ++i) {
        nTuple[i] = 1;
    }
    while (true) {
        v.visit(nTuple);
        int j = n - 1;
        while (j >= 0 && nTuple[j] == k) {
            // this is a digit j that is at the maximum, so reset it to 1
            nTuple[j] = 1
            --j;
        }
        if (j < 0) {
            // all digits j were at maximum, so all n-tuples have been visited
            break;
        }
        // this digit j is not yet at its maximum, so increase it
        ++nTuple[j];
    }
}

您可能想要实现一些边界以确保传递到方法中的 n 和 k 在正确的范围内。

计算长度为 K 的可能的 int 序列列表

Calculate a list of possible int sequences with length K

java

sequences