

C++でmatrixクラスのオブジェクトで、以下の条件を満たすものを作成したいです。

  * オブジェクトの列数はSである
  * オブジェクトは0か1を成分に持つ
  * オブジェクトのそれぞれの行の要素の和はNである

ここで、S個の成分のうち、N個、1を選ぶ組み合わせは、M = S C N (Cはコンビネーション)通り、存在します。したがって、

  * オブジェクトの行数はMである

これら4つの条件を満たすオブジェクトを作成したいです。

具体例を挙げます。例えば、S=4、N=2であれば、オブジェクトの列要素(S=)4つのうち、(N=)2つのみを1にすることが許されます。ですので、取りうる場合の数（オブジェクトの行数）は(M=)6通りです。

上の条件を満たすオブジェクトは、それぞれの行が

[code]

    (0,0,1,1), (0,1,0,1), (0,1,1,0), 
    (1,0,0,1), (1,0,1,0), (1,1,0,0)
    
[/code]

となることに注意すると、

[code]

    (0,0,1,1
     0,1,0,1
     1,0,0,1
     0,1,1,0
     1,0,1,0
     1,1,0,0)
    
[/code]

というM(=6)×S(=4)のオブジェクトになっていることがわかります。  
このようなオブジェクトを任意の自然数S, Nに対して作成したいというのが、やりたいことです。

# 試したこと

N=2の場合には、以下のようなコードを用いることで、一般のSに対して、オブジェクトを作成することができました。

[code]

    #include <vector>
    #include <complex>
    
    using namespace std;
    typedef complex<double> Complex;
    typedef vector<Complex> cvector;
    typedef vector<cvector> cmatrix;
    
    int main(void)
    {
        int S = 4;
        int N = 2;
    
        //Mを求める
        int a1 = 1; // S*(S-1)*・・・( S - (N-1)) //N回の掛け算
        int a2 = 1; // N!
    
        for (int i = 0; i < N; i++) {
            a1 = a1 * (S - i);
        }
    
        for (int i = 0; i < N; i++) {
            a2 = a2 * (N - i);
        }
    
        int M = a1 / a2;  //行列の行数を決定　M = S C N
        
        //行列Bに値を代入
        cmatrix B(M, cvector((S), 0));
        for (int i = 0; i < S - 1; i++) {
            for (int j = 0; j < S - i - 1; j++) {
                B[j + S * i - 0.5 * i * (i + 1)][(S - 1) - i] = 1;
                B[j + S * i - 0.5 * i * (i + 1)][(S - 1) - (i + j + 1)] = 1;
            }
        }
    
        return 0;
    }
    
[/code]

これにより、cmatrixのオブジェクト"B"が

[code]

    B = 
    (0,0,1,1
     0,1,0,1
     1,0,0,1
     0,1,1,0
     1,0,1,0
     1,1,0,0)
    
[/code]

という形で作成されました。

上のコードでは、S =
4としていますが、任意のSでこのコードは動きます。ただ、Nに対してはN=2しか許されません。（というのも、for文を使って、Bに直接、N回値を書き込むという操作を行っているからです。）  
ネットで調べていると、ビット演算というものを使えばできると書いてあるものもありましたが、如何せん初心者であるため、よくわかっていません。

どなたか、ご教示をお願い致します。


CC BY-SA 4.0
2022-12-17T23:52:32.337
92855
2022-12-18T11:45:15.187
2022-12-18T07:11:00.303
56056
56056
question
c++ c アルゴリズム 行列
ある条件を満たす、matrixクラスのオブジェクトを生成したい


2通りの説明を行いますので、どちらか理解しやすい方を参照してください。  
あと、最初に`cmatrix`のサイズを決める方式だと処理が複雑化するので、[vector::push_back](https://cpprefjp.github.io/reference/vector/vector/push_back.html)で都度追加する形としています。

# 再帰を使う方法

N=2 だと規則が見えづらいので、S=5, N=3 で説明します。

N=3 固定でコードを書くと、以下のようになります。

[code]

    int main(void)
    {
        int S = 5;
        int N = 3;
    
        cmatrix B;
        cvector A(S);
        for (int i = S - 1; i >= 2; --i) {
            A[i] = 1;
            for (int j = i - 1; j >= 1; --j) {
                A[j] = 1;
                for (int k = j - 1; k >= 0; --k) {
                    A[k] = 1;
                    B.push_back(A);
                    A[k] = 0;
                }
                A[j] = 0;
            }
            A[i] = 0;
        }
    
        return 0;
    }
    
[/code]

ここから N を変えるためには、ループのネスト回数を変更しなければなりません。  
このような場合は、再帰関数を使うことができます。(再帰自体の説明は長くなるので省略します)

それぞれのループの開始・終了条件を見ると、一定のルールに従っていることが分かります。

  * 開始の数字は、最初は S-1、それ以降は外側の変数-1
  * 終了条件の数字は、最初は N-1 と等しく、1ずつ減っていく

開始の数字を`start`、終了条件の数字を`stop`とすると、`stop`を減らしていって0未満になったらループのネストをやめればよいことが分かります。  
あとは、計算に必要な値を追加の引数として持ち回れば、以下のような再帰関数の形に書くことができます。

[code]

    void combinations_rec(cmatrix& B, cvector& A, int start, int stop) {
        if (stop < 0) {
            B.push_back(A);
            return;
        }
        for (int i = start; i >= stop; --i) {
            A[i] = 1;
            combinations_rec(B, A, i - 1, stop - 1);
            A[i] = 0;
        }
    }
    
    int main(void)
    {
        int S = 5;
        int N = 3;
    
        cmatrix B;
        cvector A(S);
        combinations_rec(B, A, S - 1, N - 1);
    
        return 0;
    }
    
[/code]

# 次の組み合わせを求める方法

組み合わせの順番を眺めていると、ある規則により次の組み合わせが決まることが分かります。

たとえば、S=5, N=3 の場合に、以下の連続する組み合わせについて考えます。

[code]

    (0,0,1,1,1)
    (0,1,0,1,1)
    
    (0,1,0,1,1)
    (1,0,0,1,1)
    
[/code]

左端が`0`の場合は簡単で、一番左の`1`が一つ左に移動しているだけです。

[code]

    (1,0,0,1,1)
    (0,1,1,0,1)
    
    (1,0,1,0,1)
    (1,1,0,0,1)
    
[/code]

左端に`1`が1つある場合、その次の`1`が一つ左に、左端の`1`がその左隣に移動します。

[code]

    (1,1,0,0,1)
    (0,1,1,1,0)
    
    (1,1,0,1,0)
    (1,1,1,0,0)
    
[/code]

左端に`1`が2つある場合、その次の`1`が一つ左に、左端の2つの`1`がその左隣に移動します。

まとめると、左端の連続している`1`の個数がn個の場合、その次の`1`が一つ左に、左端のn個の`1`がその左隣に移動します。

あとは、すべての`1`を右端に配置した状態から開始して、すべての`1`が左端に移動したら終了です。

[code]

    int main(void)
    {
        int S = 5;
        int N = 3;
    
        cmatrix B;
        cvector A(S);
        for (int i = S - N; i < S; ++i)
            A[i] = 1;
        B.push_back(A);
        while (true) {
            int i, j;
            for (i = 0; i < S && A[i] != 0.; ++i)
                A[i] = 0;
            if (i >= N)
                break;
            for (j = i + 1; A[j] == 0.; ++j)
                ;
            A[j] = 0;
            for (int k = j - i - 1; k < j; ++k)
                A[k] = 1;
            B.push_back(A);
        }
    
        return 0;
    }
    
[/code]


CC BY-SA 4.0
2022-12-18T05:36:15.447
92863
2022-12-18T11:45:15.187
2022-12-18T11:45:15.187
43506
43506
92855
answer