algorithm - 实现笛卡尔积，这样它就可以跳过迭代

Question

我想实现一个函数，它将返回集合的笛卡尔积，重复给定的数字。例如

input: {a, b}, 2
output:
aa
ab
bb
ba

input: {a, b}, 3
aaa
aab
aba
baa
bab
bba
bbb

然而，我能实现它的唯一方法是首先对 2 个集合(“ab”、“ab”)进行笛卡尔乘积，然后从集合的输出中添加相同的集合。这是伪代码:

function product(A, B):
    result = []
    for i in A:
        for j in B:
            result.append([i,j])
    return result
function product1(chars, count):
    result = product(chars, chars)
    for i in range(2, count):
        result = product(result, chars)
    return result

我想要的是直接开始计算最后一个集合，而不计算它之前的所有集合。这是否可能，还有一个解决方案会给我类似的结果，但它不是笛卡尔积是可以接受的。我阅读大多数通用编程语言都没有问题，因此如果您需要发布代码，您可以使用您熟悉的任何语言来完成。

Answer 1

这是一个构建 S^n 的递归算法，而不是“首先”构建 S^(n-1)。想象一个无限的 k-ary 树，其中 |S| = k。用 S 的元素标记每条边，将任何父节点连接到它的 k 个子节点。 S^m 的一个元素可以被认为是从根开始的任何长度为 m 的路径。按照这种思维方式，集合 S^m 是所有这些路径的集合。现在寻找 S^n 的问题是枚举所有长度为 n 的路径的问题——我们可以通过从头到尾考虑边标签的顺序来命名路径。我们希望直接生成 S^n 而无需首先枚举所有 S^(n-1)，因此修改深度优先搜索以查找深度 n 处的所有节点似乎是合适的。这基本上是以下算法的工作原理:

// collection to hold generated output
members = []

// recursive function to explore product space
Products(set[1...n], length, current[1...m])

    // if the product we're working on is of the
    // desired length then record it and return
    if m = length then
        members.append(current)
        return

    // otherwise we add each possible value to the end
    // and generate all products of the desired length
    // with the new vector as a prefix
    for i = 1 to n do
        current.addLast(set[i])
        Products(set, length, current)
        currents.removeLast()

// reset the result collection and request the set be generated
members = []
Products([a, b], 3, [])

现在，广度优先方法的效率不亚于深度优先方法，如果您考虑一下，它与您已经在做的事情并没有什么不同。事实上，生成 S^n 的方法必须至少生成一次 S^(n-1)，因为可以在 S^n 的解决方案中找到它。