CODEWITHSUNDEEP
cmatrixpermutationcombinatorics
Tony
Tony

Reputation: 1207

Matrix problem in C

In an mxn matrix having k objects, what are the number of ways that an object be placed in a matrix cell.(k<=n,m). By giving an example the more better illustrated, if the 1st object out of the "k" objects was placed at location (1,1),then the next object could not be placed on the 1st column or on the 1st row, and on for rest of the remaining objects.

The output of the problem will be like: (kth object, nth row, mth column) i.e., (3,3,4) or informally,"How many ways can k objects be placed on (nxm) matrix cells.

I found out the working rule,say : [n(n-1)(n-2)...(n-(k-1))][m(m-1)(m-2)...(m-(k-1))] --> this will give me exactly the number of ways, k objects can be placed in the cell, with the applied constraints.

But i can't construct the "nested for-loop" condition: for(object) for(row) for(column)

I AM USING C !

need some help in constructing the code !

Upvotes: 1

Views: 613

Answers (2)

didest
didest

Reputation: 177

As I said here, just implement this.

/* n,m,k are constants */
int rook() {
    int i, j, mem[m+1][k+1];
    for (i=0; i<=m; i++)
        mem[i][0] = 1;
    for (j=1; j<=k; j++)
        mem[0][j] = 0;
    for (i=1; i<=m; i++)
        for (j=1; j<=k; j++)
            mem[i][j] = mem[i-1][j] + (n-j+1)*mem[i-1][j-1];
    return mem[m][k];
}

As usual, you can optimize this to use O(k) space.

Upvotes: 1

user470379
user470379

Reputation: 4889

Look up Rook polynomials

Upvotes: 1

Related Questions