ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
I have to generate a matrix with p (1<=p<=30) lines and n columns (1<=n<=30) filled with 1 and 0 with the condition that any 2 lines need to have in the same positions exactly m numbers of 1 and 0 and there have to be no column filled just with 0 or 1. The answer will be in a file witch contains yes or no on the first line (if this matrix can be generated or not) and if yes on the following lines the matrix.
For example:
file.in
5 5 3
//5 lines, 5 columns and m=3
This is the problem. I analyzed it and I concluded that the matrix can be generated only if n-m can be wrote as 2*2*2*...*2(x times)
But how can I generate this matrix?
It easy with backtracking but my program should work in 2 sec max.
Sorry for my math-english
Do you mean to say 'Any two lines that are ANDED together' ? No come to think of it, that doesn't make sense either. I don't understand the 2*2, etc. Is it that n-m must be a factor of 2? I guess I have to agree with P_Shep.
first line: 1 1 1 0 0
second line :1 0 0 0 0
positions: 1 2 3 4 5
these lines have the same numbers on columns 1(a[1][1]==a[2][1]==1),4(a[1][4]==a[2][4]==0) and 5(a[1][5]==a[2][5]==0) so there are 3 columns(m=3)
first line: 1 1 1 0 0
third line : 0 1 0 0 0
positions: 1 2 3 4 5
these lines have the same numbers on columns 2(a[1][2]==a[3][2]==1),4(a[1][4]==a[3][4]==0) and 5(a[1][5]==a[3][5]==0) so there are 3 columns(m=3)
second line: 1 0 0 0 0
third line : 0 1 0 0 0
positions: 1 2 3 4 5
these lines have the same numbers on columns 3(a[2][3]==a[3][3]==0),4(a[2][4]==a[3][4]==0) and 5(a[2][5]==a[3][5]==0) so there are 3 columns(m=3)
and the process continues with the lines: 1-4,1-5,2-4,3-5,3-4,3-5...
I hope you understood.
what are you trying to do and with what language?
java will not support multidimensional arrays, (read: matrices) but you should be able to do it like this:
[ [1 0 0]
[0 1 0]
[0 0 1] ]
Originally posted by titanium_geek what are you trying to do and with what language?
java will not support multidimensional arrays, (read: matrices) but you should be able to do it like this:
[ [1 0 0]
[0 1 0]
[0 0 1] ]
Java programmers would argue that Java does indeed support multidimensional arrays. A multidimensional array in Java is, as you have indicated, an array of arrays. However, the syntax for using multidimensional arrays works as you would expect. For example:
Code:
int[][] matrix = new int[5][5];
matrix[0][1] = 10;
Here's a toy example that shows how you might write a Matrix class using multidimensional arrays in Java (compile with the -source 1.4 option):
Code:
public class MultiDimArray {
public static void main( String[] args ) {
Matrix a;
Matrix b;
a = new Matrix( 2 , 3 );
a.setValue( 0 , 0 , 0 );
a.setValue( 0 , 1 , 1 );
a.setValue( 0 , 2 , 2 );
a.setValue( 1 , 0 , 3 );
a.setValue( 1 , 1 , 4 );
a.setValue( 1 , 2 , 5 );
b = new Matrix( 3 , 2 );
b.setValue( 0 , 0 , 1 );
b.setValue( 0 , 1 , 2 );
b.setValue( 1 , 0 , 3 );
b.setValue( 1 , 1 , 4 );
b.setValue( 2 , 0 , 5 );
b.setValue( 2 , 1 , 6 );
a.multiply( b ).print();
}
}
class Matrix {
private int[][] matrix;
public Matrix( int numRows , int numColumns ) {
matrix = new int[numRows][numColumns];
}
/**
* Set the value of a specific matrix position.
*/
public void setValue( int row , int column , int value ) {
matrix[row][column] = value;
}
public int getValue( int row , int column ) {
return matrix[row][column];
}
public int getNumRows() {
return matrix.length;
}
public int getNumColumns() {
return matrix[0].length;
}
/**
* Cross multiply two matrices.
*/
public Matrix multiply( Matrix other ) {
Matrix result = null;
int value = 0;
assert( getNumColumns() == other.getNumRows() );
result = new Matrix( getNumRows() , other.getNumColumns() );
for ( int row = 0 ; row < getNumRows() ; row++ ) {
for ( int column = 0 ; column < other.getNumColumns() ; column++ ) {
value = 0;
for ( int i = 0 ; i < getNumColumns() ; i++ ) {
value += ( getValue( row , i ) * other.getValue( i , column ) );
}
result.setValue( row , column , value );
}
}
return result;
}
/**
* Display the matrix contents.
*/
public void print() {
System.out.println();
for ( int row = 0 ; row < getNumRows() ; row++ ) {
for ( int column = 0 ; column < getNumColumns() ; column++ ) {
System.out.print( getValue( row , column ) + " " );
}
System.out.println("");
System.out.println("");
}
}
}
Here are my ideas, might be wrong, it's your homework not mine.
m is less than n
Don't forget corner cases;
Could m be zero? You can make a valid matrix when m=0
for any value of n (alternating lines of 00000 and 11111)
If p==1 then any matrix is valid
What about n==1,p==1,m==1
n-m can be zero
00 p=2 n=2, m=2
11
000 p=3, n=3,m=3
111
000
Consider p==2 n==4 m==2
by the n-m=2^x rule this should be solveable but I can't
find a correct matrix
when p==2 you can only avoid homogeneous columns when m==0
or m==n
>I concluded that the matrix can be generated only if n-m can be wrote as 2*2*2*...*2(x times)
p=10 n=5 m=2
here n-m=3 so why is this matrix wrong?
It seems to follow the rules you gave.
30*30*30=27000 possible different combinations of p,n and m
Take only the ones where n-m=2^x and you have 3600 combinations.
If you can calculate a matrix in under 5 minutes then
with two computers running for a week you can calculate
a matrix for every p,n,m value.
Make a program that does
if (p==1 && n==1 && m==1) printf("yes\n1\n")
if (p==2 && n==1 && m==1) printf("yes\n1\n0")
etc
You will have a big source code file and the executable
file will be a few megabytes but it will produce the result really
quickly.
If you have to submit the program on paper...
//quick program to work out how many
//combinations of n and m allow a valid matrix.
//using the n-m=2^x rule
#include <stdio.h>
int p=0,n=0,m=0;
int count=0;
int mcheck(int tn, int tm)
{
int temp=0;
int answer=0;
printf("n=%d m=%d\n",tn,tm);
temp=n-m;
if (m==0) return (0);
switch (temp)
{
case 0: {answer=1; break;};
case 2: {answer=1; break;};
case 4: {answer=1; break;};
case 8: {answer=1; break;};
case 16: {answer=1; break;};
case 32: {answer=1; break;};
case 64: {answer=1; break;};
case 128: {answer=1; break;};
case 256: {answer=1; break;};
case 512: {answer=1; break;};
case 1024: {answer=1; break;};
case 2048: {answer=1; break;};
case 4096: {answer=1; break;};
case 8192: {answer=1; break;};
case 16384: {answer=1; break;};
case 32768: {answer=1; break;};
case 65536: {answer=1; break;};
case 131072: {answer=1; break;};
case 262144: {answer=1; break;};
case 524288: {answer=1; break;};
case 1048576: {answer=1; break;};
case 2097152: {answer=1; break;};
case 4194304: {answer=1; break;};
case 8388608: {answer=1; break;};
case 16777216: {answer=1; break;};
case 33554432: {answer=1; break;};
case 67108864: {answer=1; break;};
case 134217728: {answer=1; break;};
case 268435456: {answer=1; break;};
case 536870912: {answer=1; break;};
case 1073741824: {answer=1; break;};
}
return (answer);
}
int main ()
{
for (p=1;p<30+1;p++){
for (n=1;n<30+1;n++){
for (m=1;m<30+1;m++){
if (mcheck(n,m)) count++;}
}
}
printf("%d", count);
return (0);
}
_Creating the matrix_
My theory, which might be wrong;
You can take a correct matrix and swap the position of two
of the columns and it is still correct.
Also you can invert every bit in a column and the matrix stays valid.
Therefore I think that if a valid matrix is possible at all, it
is possible to make one starting with a line of zero's
I suggest the method
first line is 00000....
to create the second line invert the first n-m bits
eg if n==5 m==3 line two is
11000
make the next line by inverting n-m bits starting at the bit after
the last one you inverted to make the previous line, wrap back to
the start of the line whn necessary
for example p==12 n==5 m==3
00000
11000
11110
01111
00011
00000 pattern repeats from here
11000
11110
01111
00011
00000
11000
Excuse me for my late reply.
Your idea is partially good but let take a look at the 2,3 and 4 line:
10000
11000
11100
between 1 and 2 there are four matches on 1,3,4 and 5 position
but between 1 and 4 there are just three matches on 1,4 and 5 position
(4!=3 => wrong)
and there shouldn't be a line filled only with 0 or 1 like your first line (00000)
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.