4
$\begingroup$

Assume I have a matrix.

(mat = Partition[Range@9, 3]) // MatrixForm

mat$=\left( \begin{array}{ccc} \color\red1 & \color\red2 & \color\red3 \\ \color\green 4 & \color\green5 & \color\green6 \\ \color{blue}7 & \color{blue}8 &\color{blue} 9 \\ \end{array}\right)$

I would like to scramble matrix matcolunmn-wise to generate all possible new matrix newMat under some condition.

Conditions are:

1) Column elements of mat must stay in their column, i.e. 1st column of newMat must be one of the elements of the Permutations[{1, 4, 7}, {3}]={{1, 4, 7}, {1, 7, 4}, {4, 1, 7}, {4, 7, 1}, {7, 1, 4}, {7, 4, 1}}; And similarly col2 $\in$ Permutations[{2,5,8}, {3}] and col3 $\in$ Permutations[{3,6,9}, {3}].

2) 1st row of mat is {1,2,3} and thus 1st Row entries of newMat, should not contain any of element of this set= {{1, 2}, {1, 3}, {2, 3},{1,2,3}} i.e. pairs or triple. The same for row 2 and row 3.

...............

..................

$\{1,4,7\}$ must stay in the 1st column, $\{2,5,8\}$ must stay in the 2nd column, $\{3,6,9\}$ must stay in the 3rd column. Every row has distinct colors.

....

.....

Some of the undesired newMat: It passes first condition but not second condition. enter image description here

For $3\times3$ there are only 3!2!1!= 12 matrices satisfies the condition which shows below. For $4\times4$ there are only 4!3!2!1!= 288 Good candidate:

newMat$=\left( \begin{array}{ccc} \color{red}1 & \color{blue}8 & \color{green}6 \\ \color{green}4 & \color{red}2 & \color{blue}9 \\ \color{blue}7 & \color{green}5 &\color{red} 3 \\ \end{array} \right)$

I would like to generate all $4\times4$ square matrices and if possible/easy all $5\times4$ matrices (there are 5!4!3!2!=34560). Any suggestion.

Edit

After I used @yohbs code I was able to generate all desired matrices but it is not efficient for $4\times4$ matrices.

   {r, c} = Dimensions[mat];
perms = Permutations[Range@r];
q = 1 + IntegerDigits[Range[(r!)^c], r!, c];
allScrambles = 
  Transpose[
   Table[mat[[perms[[q[[i, j]]]], j]], {j, c}, {i, Length@q}], {3, 1, 
    2}];


 sub = Join @@ (Subsets[#, {2}] & /@ mat);

    ArrayPlot[#, 
   ColorRules -> {1 | 2 | 3 -> Red, 
     4 | 5 | 6 -> Darker@Green, _ -> Blue}, 
   Epilog -> {MapIndexed[
      Text[Style[#1, White, 26], Reverse[#2 - 1/2]] &, 
      Reverse[#], {2}]}] & /@ sol

enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ I can't understand the question. What is "they" in condition (1)? Condition (2) isn't even grammatically correct. If you use clear phrasing and reduce the amount of effort people need to make to understand what you want, you will get better answers. $\endgroup$ – Szabolcs Apr 12 '18 at 10:35
  • $\begingroup$ @Szabolcs sorry for ambiguity. See my edit. $\endgroup$ – OkkesDulgerci Apr 12 '18 at 13:22
  • $\begingroup$ Thanks, it's much clearer now. $\endgroup$ – Szabolcs Apr 12 '18 at 14:26
  • $\begingroup$ Does condition (2) mean the row should not contain any sequence of those numbers? $\endgroup$ – Teabelly May 12 '18 at 16:28
  • $\begingroup$ Yes that's right $\endgroup$ – OkkesDulgerci May 12 '18 at 16:55
1
$\begingroup$

I must have something wrong with my understanding of the criteria because I get a lot more possibilities than what is shown.

Here is my solution:

ClearAll[MatrixOK, matrixSize, mat, sub, columns, columnPermutations, \
    allPossibilities, okChoices]
MatrixOK2[matrix_, columns_] := 
  Max[Length[#] & /@ 
     Flatten[Outer[Intersection, mat, matrix, 1], 1]] <= 1;
matrixSize = {3, 3};
DateString[]
(mat = ArrayReshape[Range@(Times @@ matrixSize), 
    matrixSize]) // MatrixForm
sub = Subsets[#, {2, matrixSize[[2]]}] & /@ mat;
columns = Transpose@mat;
columnPermutations = Permutations[#, {matrixSize[[1]]}] & /@ columns;
allPossibilities = Transpose /@ Tuples[columnPermutations];
okChoices = 
  Select[allPossibilities, MatrixOK2[#, matrixSize[[2]]] &];
DateString[]
Length[allPossibilities]
Length[okChoices]
(* some examples *)
MatrixForm[#] & /@ Take[okChoices, 5]

Edit 2: For the 4x4 case, I get 331776 possibilities and 576 that meet what I think are the criteria. For 3x3, I get 216 possibilities and 12 solutions.

I believe the correct formula for the number of choices for an n by n array is

(Factorial[n])^n

This agrees with the choices that are computed for the 4x4 case. Or, for the case described above that has "matrixSize" describing the {rows, columns},

Factorial[matrixSize[[1]]]^matrixSize[[2]]

EDIT: I believe that there is another way to determine a matrix is OK using this (modified per new understanding):

MatrixOK2[matrix_, columns_] := 
  Max[Length[#] & /@ 
     Flatten[Outer[Intersection, mat, matrix, 1], 1]] <= 1;

It doesn't use or need columns but I kept it in for consistency with the previous formula. I'm somewhat surprised that this new formula isn't substantially faster but for 3x3, that isn't the case. For the 4x4, it lowers the wall clock time from 13 seconds to 5 seconds, so it is noticeably faster there. I've confirmed that the results "okChoices" are the same regardless of what check formula I use.

EDIT 2: I now understand that the criteria about not having repetitions of the original rows applies to ALL rows. So, I've modified the second check function to fix this and now get the same number as expected.

$\endgroup$
6
  • $\begingroup$ Thanks for the answer. I'll check your solution when get home. $\endgroup$ – OkkesDulgerci Jan 3 '20 at 20:36
  • $\begingroup$ MatrixForm[#] & /@ Take[okChoices, 5] 1st, 4th and 5th matrices violate the condition. First matrix has {2,3} in the same row. Fourth matrix has {2,3} and {5,6} in the same row. Fifth matrix has {5,6} and {7,9} in the same row. $\endgroup$ – OkkesDulgerci Jan 4 '20 at 1:39
  • $\begingroup$ See for example ArrayPlot[#, ColorRules -> {1 | 2 | 3 -> Red, 4 | 5 | 6 -> Darker@Green, _ -> Blue}, Epilog -> Join @@ MapIndexed[ Inset[Style[#, White, 26], Reverse[#2 - 1/2]] &, Reverse@#, {2}]] & /@ Take[okChoices, 5] $\endgroup$ – OkkesDulgerci Jan 4 '20 at 2:29
  • $\begingroup$ Ok, I see why I'm misinterpreting the conditions. I thought the exclusion of more than 1 of the items in the same row was only for the initial row, not any row. Your description of the condition said that the first row could not contain these but I misread the second part of this. Let me retry. I'm now assuming that no row may contain multiplies of the initial sets. $\endgroup$ – Mark R Jan 4 '20 at 20:59
  • $\begingroup$ I should have said that I get the expected number for the 3x3 and twice the stated expected number for 4x4. That said, I've hand checked a number of the results, and they seem correct. Please double check and see if there are matrices included in my 4x4 case that shouldn't be included. $\endgroup$ – Mark R Jan 5 '20 at 1:47
1
$\begingroup$

If your matrix is mat then this generates all scrambles of columns:

{r, c} = Dimensions[mat]
perms = Permutations[Range@r];
q = 1 + IntegerDigits[Range[(r!)^ c], r!, c];
allScrambles = 
  Transpose[
   Table[mat[[perms[[q[[i, j]]]], j]], {j, c}, {i, Length@q}],
 {3, 1, 2}];

Then you can check whether a scrambled matrix has a row in common with the original one:

check[candidate_, original_] :=  Not[Or @@ (MemberQ[original, #] & /@ candidate)]

and use that to filter out:

result = Select[allMatrices, check[#, mat] &];

for mat=Partition[Range@12, 4] these are the first 16 results:

enter image description here

You can probably optimize in terms of running time, but for these small sizes it's so fast already that there's no need to. Also, if you want a random scramble without generating them all you can simply do

scramble[matrix_]:=Transpose@Table[RandomSample@col, {col, Transpose@matrix}]
$\endgroup$
3
  • $\begingroup$ It does not produce desired output. Can you please check it. BTW what is allMatrices? $\endgroup$ – OkkesDulgerci Apr 10 '18 at 23:52
  • $\begingroup$ allScrambles is right. But check is not right. If I am right, it should produce 3!2!1!=12 matrices. What I want is 1,2,3 should bot in be in the same row. Similarly, 4,5,6 and 7,8,9 should not be in the same row. $\endgroup$ – OkkesDulgerci Apr 11 '18 at 0:20
  • 2
    $\begingroup$ I can't quite understand what you mean be "4,5,6" should not be in the same row". Any two cannot be? all three? It would be helpful if you could supply the full list of permissible matrices for some small example $\endgroup$ – yohbs Apr 11 '18 at 20:00
0
$\begingroup$

Apologies for the faux pas of a clumsy answer but I have an attempt:

Given your initial matrix and list

(m0 = Partition[Range@9, 3]) // MatrixForm

&

s = {{1, 2}, {1, 3}, {2, 3}, {4, 5}, {4, 6}, {5, 6}, {7, 8}, {7, 9}, {8, 9}, {1, 2, 3}, {4, 5, 6}, {7, 8, 9}}

Finding all column permutations for condition (1)

m1=Permutations[Transpose[m0][[#]]]&/@Range@3

Then taking permutations (one from each list using Tuples)

m2 = Transpose[#] & /@ Tuples[m1]//Dimensions
Out[59]= {216,3,3}

Had a little trouble with the second condition, not sure this is right but...

Pick[m2, IntersectingQ[m2[[#]], s] & /@ Range@Length[m2],False] 

But this gives 156 matrices rather than OP's predicted 12

If terribly wrong, please delete. Thanks.

EDIT*

Realised it is not taking out any of the 2 number sublists of s

$\endgroup$
1
  • $\begingroup$ Yes, your first result from the original code you posted gave {{1, 2, 6}, {4, 5, 9}, {7, 8, 3}}, which clearly violates the second criteria. $\endgroup$ – Mark R Jan 3 '20 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.