0

NxN 正方行列が与えられた場合、同じ数の行と列を削除して、可能なすべての正方部分行列を決定したいと思います。

可能なすべての 2x2 行列を決定するには、4 回ループする必要があります。同様に、3x3 行列の場合、6 回ループする必要があります。ループのコードが動的に生成されるように C++ でコードを生成する方法はありますか? C++ でのコード生成に関連するいくつかの回答を確認しましたが、それらのほとんどは python を使用しています。Pythonについてはわかりません。では、C++ でコードを生成するコードを書くことは可能ですか?

4

1 に答える 1

1

あなたの言っていることが理解できれば、M 行を選択するには M ループが必要であり、M x M サブマトリックスの場合は M 列に M ループが必要であるということです。1 <= M <= N

これを行うために 2*M ループは必要ありません。増え続けるループでコードを動的に生成する必要はありません!

基本的に、i_{1}、i_{2}、...、i_{M} と j_{1}、j_{2}、...、j_{M} のすべての可能な組み合わせを「組み合わせる」必要があります。その 1 <= i_{1} < i_{2} < ... < i_{M} <= N (j についても同様)

そのようなすべての i_{1}, ..., i_{M} のすべての可能な組み合わせがあれば、基本的に完了です。

たとえば、10 x 10 マトリックスで作業していて、4 x 4 サブマトリックスが必要だとします。

最初に行 {1, 2, 3, 4} と列 {1, 2, 3, 4} を選択したとします。次に列 {1, 2, 3, 5} を選択します。次の {1, 2, 3, 6} というように {1, 2, 3, 10} まで。次に {1, 2, 4, 5} を選択し、次の {1, 2, 4, 6} を選択して、{7, 8, 9, 10} に到達するまで続けます。これは、一連のすべての組み合わせ (「10 から 4 を選択」) を生成する方法の 1 つです。

さあ、このシーケンスを生成する関数を書けば完成です。入力として M、N、現在の組み合わせ (M 値の配列として) を取り、次の組み合わせを返すことができます。

次の行と次の列を選択するには、このシーケンスを呼び出す必要があります。

これは少しゆるめにしています。不明な点がある場合は、編集して回答を更新できます。

編集：

ループ インデックスが 0 から始まると仮定します (C++ の方法です!)。アルゴリズムをさらに詳しく説明すると、入力として 1 つの組み合わせを指定すると、その組み合わせをある種の「カウンター」として扱うことによって、次の組み合わせを生成できます (ただし、数字の繰り返しはありません)。

免責事項 : 以下のコード スニペットを実行またはテストしていません。しかし、アイデアはあなたが見るためにそこにあります。また、C++ はもう使用しません。間違いがあればご容赦ください。

// Requires M <= N as input, (N as in N x N matrix)
void nextCombination( int *currentCombination, int M, int N ) {
    int *arr = currentCombination;
    for( int i = M - 1; i >= 0; i-- ) {
        if( arr[i] < N - M + i ) {
            arr[i]++;
            for( i = i + 1, i < M; i++ ) {
                arr[i] = arr[i - 1] + 1;
            }
            break;
        }
    }

}

// Write code for Initialization: arr = [0, 1, 2, 3]
nextCombination( arr, 4, 10 );
// arr = [0, 1, 2, 4]

// You can check if the last combination has been reached by checking if arr[0] == N - M + 1. Please incorporate that into the function if you wish.

編集：

実際には、可能なすべての部分行列の特異点を確認したいと考えています。私のアプローチは、すべての部分行列を計算してから、それらの行列式を見つけることです。ただし、2x2 行列の行列式を計算した後は、それらを保存して、3x3 行列の行列式の計算中に使用します。等々。より良いアプローチを提案してもらえますか。スペースと時間の制約はありません。– ヴィニール

あなたが提案したものを使用した簡単なアプローチは、サブマトリックスを作成する行と列の組み合わせに基づいて決定要因にインデックスを付けることです。最初に、1 x 1 サブ行列の行列式をハッシュ マップに格納します (基本的にはエントリ自体)。

したがって、10 x 10 の場合、ハッシュ マップは次のようになります。
{ "0-0" : arr_{0, 0}, "0-1" : arr_{0, 1}, . . . "1-0" : arr_{1, 0}, "1-1" : arr_{1, 1}, . . . "9-9" : arr_{9, 9} }

M = 2 の場合、通常の式 (初期化された 1 x 1 サブ行列の行列式) を使用して行列式を計算し、ハッシュ マップに追加できます。2 x 2 サブマトリックスのハッシュ文字列は1:3-2:8、元の 10 x 10 マトリックスの行インデックスが 1,3 で、列インデックスが 2, 8 のようになります。一般に、mxm サブマトリックスの行列式は次のようになります。必要な (既に) 計算された (m - 1) x (m - 1) 行列式をすべて検索することによって決定されます。これは単純なハッシュ マップ検索です。繰り返しますが、計算が完了したら、行列式をハッシュ マップに追加します。

もちろん、nextCombination() 関数を少し変更する必要があるかもしれません。現在、行と列のインデックスは 0 から N - 1 までと想定されています。

別の注意として、すべての部分行列は 1 x 1 から処理されるため、nextCombination() 関数のようなものは必要ありません。2 x 2 行列が与えられた場合、もう 1 つの行と列を選択して 3 x 3 行列を形成する必要があります。したがって、1 つの行インデックス (2 x 2 サブマトリックスを作成する行インデックスの一部ではない) と、同様に 1 つの列インデックスを選択する必要があります。しかし、2 x 2 行列ごとにこれを行うと、重複した 3 x 3 行列が生成されます。重複を排除する方法を考える必要があります。重複を回避する 1 つの方法は、インデックスがサブ マトリックスの最大の行/列インデックスより大きい行/列のみを選択することです。

繰り返しますが、私はアイデアを大まかに定義しました。その上に構築できます。

于 2016-06-15T17:25:33.157 に答える