I want to create a matrix class object that meets certain conditions.

I would like to create a matrix class object in C++ that meets the following conditions:

The number of columns for the object is S
Objects have 0 or 1 as components
The sum of elements in each row of objects is N

Here, the combination of N and 1 out of S components exists as M=SC N (C is the combination).Therefore,

Object has M rows

I want to create an object that meets these four conditions.

Let me give you a specific example.For example, if S=4 and N=2, only two (N=) of the four column elements (S=) of the object are allowed to be 1.Therefore, there are 6 possible (M=) rows of objects.

Objects that meet the above conditions have their respective rows

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

Note that

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

You can see that the object is M(=6)×S(=4).
You want to create these objects for any natural number S,N.

When N=2, we were able to create objects for the general S by using the following code:

#include<vector>
# include <complex>

using namespace std;
typeef complex<double>Complex;
typeef vector<Complex>cvector;
typedef vector <cvector >cmatrix;

int main (void)
{
    int S = 4;
    int N = 2;

    Find //M
    inta1=1;//S*(S-1)*...(S-(N-1))/N times multiplication
    inta2 = 1; // N!

    for(inti=0;i<N;i++){
        a1 = a1*(S-i);
    }

    for(inti=0;i<N;i++){
        a2 = a2*(N-i);
    }

    int M = a1/a2; // Determine the number of rows in the matrix M = SCN
    
    // Replace matrix B with value
    cmatrix B(M, cvector((S), 0);
    for(inti=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;
}

This allows the cmatrix object "B" to be

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)

Created in the form of

The code above says S = 4, but this code will work for any S.However, only N=2 is allowed for N (because we write the N value directly to B using the for statement).
When I looked it up online, it said that I could do it using bit calculations, but I'm not sure because I'm a beginner.

Please let me know.

c++ c algorithm procession

2022-12-18 14:03

1 Answers

There are two explanations, so please refer to the one that is easier to understand.
Also, the processing becomes more complicated by determining the size of cmatrix first, so we add it every time with vector:push_back.

If N=2, it is difficult to see the rules, so I will explain it with S=5, N=3.

If you write a code with N=3 fixed, it will look like this:

int main (void)
{
    int S = 5;
    int N = 3;

    cmatrix B;
    cvector A(S);
    for(inti=S-1;i>=2;--i){
        A[i] = 1;
        for(int j=i-1;j>=1;--j){
            A[j] = 1;
            for(intk=j-1;k>=0;--k){
                A[k] = 1;
                B.push_back(A);
                A[k] = 0;
            }
            A[j] = 0;
        }
        A[i] = 0;
    }

    return 0;
}

To change N from here, you must change the number of loops nested.
In such cases, you can use a recursive function.(The recursion itself will be long and will be omitted)

If you look at the start and end conditions of each loop, you can see that they follow certain rules.

Start number is S-1 first and then outside variable -1
The termination condition number is initially equal to N-1, decreasing by 1

If you set the starting number to start and the ending condition to stop, you can see that you can reduce stop and stop nesting the loop when it is less than zero.
Then, if you take the values required for the calculation as additional arguments, you can write them in the form of recursive functions as follows:

void combinations_rec (cmatrix & B, cvector & A, int start, int stop) {
    if(stop<0){
        B.push_back(A);
        return;
    }
    for(inti=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;
}

If you look at the order of combinations, you can see that a rule determines the next combination.

For example, if S=5, N=3, consider the following consecutive combinations:

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

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

If the far left is 0, it is easy, and the far left is just one 1 moving to the left.

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

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

If there is one 1 on the far left, the next 1 moves to the left and the left 1 moves to the left.

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

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

If there are two 1s on the far left, then one 1 moves to the left and two 1 moves to the left.

To sum up, if the number of consecutive 1s on the far left is n, then one 1 moves to the left and n 1 moves to the left.

All 1 starts with all 1 placed on the far right and ends when all 1 moves to the far left.

int main (void)
{
    int S = 5;
    int N = 3;

    cmatrix B;
    cvector A(S);
    for (inti=S-N;i<S;++i)
        A[i] = 1;
    B.push_back(A);
    while(true){
        inti,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 (intk=j-i-1;k<j;++k)
            A[k] = 1;
        B.push_back(A);
    }

    return 0;
}

2022-12-19 00:24

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656