-1

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通りです。

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

(0,0,1,1), (0,1,0,1), (0,1,1,0), 
(1,0,0,1), (1,0,1,0), (1,1,0,0)

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

(0,0,1,1
 0,1,0,1
 1,0,0,1
 0,1,1,0
 1,0,1,0
 1,1,0,0)

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

試したこと

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

#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;
}

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

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)

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

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

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

3
  • 説明に書かれた順番と、ご提示のコードが作成するオブジェクトの順番が異なっているようなのですが、どちらが正しいのでしょうか。例えば、説明だと(0,1,0,1)の次は(0,1,1,0)となっていますが、コードだと(1,0,0,1)になります。
    – actorbug
    Commented 2022年12月18日 3:16
  • すいません、コードの方が正しいです。書き直します。
    – user56056
    Commented 2022年12月18日 7:07
  • 編集しなおしたものが正しいです。書き間違えました、すいません。
    – user56056
    Commented 2022年12月18日 7:11

1 件の回答 1

1

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

再帰を使う方法

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

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

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;
}

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

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

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

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

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;
}

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

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

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

(0,0,1,1,1)
(0,1,0,1,1)

(0,1,0,1,1)
(1,0,0,1,1)

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

(1,0,0,1,1)
(0,1,1,0,1)

(1,0,1,0,1)
(1,1,0,0,1)

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

(1,1,0,0,1)
(0,1,1,1,0)

(1,1,0,1,0)
(1,1,1,0,0)

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

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

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

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;
}

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。