DATA Step, Macro, Functions and more

Puzzle - How many matrix can you find?

Reply
Super User
Posts: 10,041

Puzzle - How many matrix can you find?

I thought a puzzle from a post of IML . Just have a fun .

Suppose we have a 3*2 matrix

x11 x12

x21 x22

x31 x32

They are all positive integer (i.e.  1 2 3 4.....). If we know its column total and row total. How many matrix are there ,could be satisfied with this condition?

                                 col_total

                 x11 x12      5

                 x21 x22      5

                 x31 x32      7

row_total      8      9

Xia Keshan

Super User
Posts: 10,041

Re: Puzzle - How many matrix can you find?

Nobody ? Actually it is easy just brute enumerate (greedy algorithm) .  it is 15 .

data _null_;
do x11=1 to 5 ;
 do x12=1 to  5 ;
  do x21=1 to 5 ;
   do x22=1 to  5 ;
     do x31=1 to  7 ;
        do x32=1 to  7 ;
         if x11+x12=5 and
             x21+x22=5 and
             x31+x32=7 and
             x11+x21+x31=8 and
             x12+x22+x32=9 then do; n+1;
             put _all_ /;     end;
       end;
     end;
   end;
  end;
 end;
end;
run;








x11=1 x12=4 x21=1 x22=4 x31=6 x32=1 n=1 _ERROR_=0 _N_=1

x11=1 x12=4 x21=2 x22=3 x31=5 x32=2 n=2 _ERROR_=0 _N_=1

x11=1 x12=4 x21=3 x22=2 x31=4 x32=3 n=3 _ERROR_=0 _N_=1

x11=1 x12=4 x21=4 x22=1 x31=3 x32=4 n=4 _ERROR_=0 _N_=1

x11=2 x12=3 x21=1 x22=4 x31=5 x32=2 n=5 _ERROR_=0 _N_=1

x11=2 x12=3 x21=2 x22=3 x31=4 x32=3 n=6 _ERROR_=0 _N_=1

x11=2 x12=3 x21=3 x22=2 x31=3 x32=4 n=7 _ERROR_=0 _N_=1

x11=2 x12=3 x21=4 x22=1 x31=2 x32=5 n=8 _ERROR_=0 _N_=1

x11=3 x12=2 x21=1 x22=4 x31=4 x32=3 n=9 _ERROR_=0 _N_=1

x11=3 x12=2 x21=2 x22=3 x31=3 x32=4 n=10 _ERROR_=0 _N_=1

x11=3 x12=2 x21=3 x22=2 x31=2 x32=5 n=11 _ERROR_=0 _N_=1

x11=3 x12=2 x21=4 x22=1 x31=1 x32=6 n=12 _ERROR_=0 _N_=1

x11=4 x12=1 x21=1 x22=4 x31=3 x32=4 n=13 _ERROR_=0 _N_=1

x11=4 x12=1 x21=2 x22=3 x31=2 x32=5 n=14 _ERROR_=0 _N_=1

x11=4 x12=1 x21=3 x22=2 x31=1 x32=6 n=15 _ERROR_=0 _N_=1

Xia Keshan

Respected Advisor
Posts: 3,156

Re: Puzzle - How many matrix can you find?

It is 15. I like to break them up first.

data h1;

     do x11=1 to 4;

           x12=5-x11;

           output;

     end;

run;

data h2;

     do x21=1 to 4;

           x22=5-x21;

           output;

     end;

run;

data h3;

     do x31=1 to 6;

           x32=7-x31;

           output;

     end;

run;

proc sql;

     create table w1 as 

           select * from h1, h2, h3

                where x11+x21+x31=8 and x12+x22+x32=9;

quit;

Haikuo

Respected Advisor
Posts: 4,930

Re: Puzzle - How many matrix can you find?

If you have a SAS/OR licence, this puzzle can be solved as a constraint satisfaction problem with proc CLP :

data lincon;

_TYPE_ = "EQ";

input x11 x12 x21 x22 x31 x32 _RHS_;

datalines;

1 1 . . . . 5

. . 1 1 . . 5

. . . . 1 1 7

1 . 1 . 1 . 8

. 1 . 1 . 1 9

;

proc CLP condata=lincon USECONDATAVARS=1  domain=[1,10] findall out=soln;

run;

proc print data=soln; run;

PG

PG
Super User
Posts: 10,041

Re: Puzzle - How many matrix can you find?

Hi PG,

I can't believe you still response this one posted at a couple of weeks ago .

Actually it is from SAS/IML  . I posted here for a fun.

Best.

Xia Keshan

Super Contributor
Posts: 340

Re: Puzzle - How many matrix can you find?

I have an additional solution and a question:

Proc Optmodel;

  Set Rows=1..3;

  Set Columns=1..2;

  Num Row_Sum{Rows}=[5 5 7];

  Num Col_Sum{Columns}=[8 9];

  Var x {i in Rows, j in Columns} >=0 Integer;

  Max z=0;

  Con Cons1{i in Rows}: Sum {j in Columns} x[i,j]=Row_Sum;

  Con Cons2{j in Columns}: Sum {i in Rows} x[i,j]=Col_Sum;

  Solve;

  Print x;

Quit;

The question is: Optmodel with a zero-objective in comparison to constraint programming; is there a significant performance difference if one "abuses" optmodel to solve linear constraint programmes (IF 1 solution is enough)?

Ask a Question
Discussion stats
  • 5 replies
  • 270 views
  • 0 likes
  • 4 in conversation