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ループを作成できると思いますが、それは私にはハックのようです。

ありがとう。

編集：自分が何を求めているのか、実際に何が必要なのかが本質的に同じ問題であることがわからなくなった後、問題を編集しました。templatetypedefの投稿を読んだ後、それ自体のサイズの回数でセットのデカルト積を計算しようとしているようです。

4

1 に答える 1

2

セット {1, 2, 3} とそれ自体のデカルト積を 15 回計算しようとしています。これは、単純な再帰アルゴリズムを使用して非常にエレガントに行うことができます。

  • セットとそれ自体のデカルト積を 1 回だけ計算するには、元のセットの各要素のシングルトン リストを含むセットを返します。
  • セット自体のデカルト積を 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 に答える