4

注意：在阅读了 templatetypedef 的帖子后，似乎我正在尝试计算一组与自身的笛卡尔积一定次数。

我不完全确定我要解决的问题是什么，但对我来说似乎非常接近置换。

所以基本上，我的问题是这个。给定一个数组，例如：

{1, 2, 3}

和一个大小，比如 2。我需要输出：

{1,1},{1,2},{1,3},{2,1},{2,2},...

如果大小为 3，那么它将是

{1,1,1},{1,1,2},{1,1,3},{1,2,1},{1,2,2},{1,2,3},{1,3,1}...

我该怎么做？

就我的问题而言，我的输入大小为 15 个数字，所以我想我可以创建 15 个 for 循环，但这对我来说似乎是一个 hack。

谢谢。

编辑：在不确定我在问什么和我真正需要的是本质上相同的问题后，我编辑了我的问题。在阅读了 templatetypedef 的帖子后，似乎我正在尝试计算一组具有自身大小的笛卡尔积。

4

1 回答 1

2

您正在尝试计算集合 {1, 2, 3} 与自身的笛卡尔积十五次。您可以使用简单的递归算法非常优雅地做到这一点：

  • 要计算一个集合与其自身的笛卡尔积，返回一个集合，其中包含原始集合中每个元素的单例列表。
  • 计算一个集合与自身 n > 1 次的笛卡尔积：
    • 递归地计算集合与自身的笛卡尔积 n - 1 次。
    • 对于输入列表的每个元素 x：
      • 对于到目前为止产生的每个序列 S：
        • 将序列 S + x 添加到输出集。
    • 返回输出集。

在（有些低效的）C++ 代码中：

vector<vector<int>> CartesianPower(const vector<int>& input, unsigned k) {
    if (k == 1) {
        vector<vector<int>> result;
        for (int value: input) {
            result.push_back( {value} );
        }
        return result;
    } else {
        vector<vector<int>> result;
        vector<vector<int>> smallerPower = CartesianProduct(input, k - 1);

        for (int elem: input) {
            for (vector<int> sublist: smallerPower) {
                sublist.push_back(elem);
                result.push_back(sublist);
            }
        }

        return result;
     }
}

希望这可以帮助！

于 2013-01-27T02:24:10.360 回答