I am trying to write a function which produces square matrices with certain characteristics. The function should have two inputs:

  1. number of the rows, n

  2. number of the times each element in the range 1, 2, 3, ..., n should be repeated in the matrix

So assuming the function is called KOCH then KOCH[4, {2, 4, 5, 5}] means the matrix should be 4 x 4 with 1, 2, 3 and 4 repeated respectively for 2, 4, 5, 5 times in the matrix, but each row in the output should be nondecreasing. And finally the function should find all the possible matrices, not only some of them.

The code I prepared is as following

Koch[n_, num_] := 
    list = Flatten@Table[Range[n], {i, n}];
    list = DeleteDuplicates[Sort /@ Tuples[list, {n}]];
    list = Tuples[list, {n}];
    For[i = 1, i < n + 1, i++, 
      list = list[[Flatten@Position[Map[Count[#, i, 2] &, list], num[[i]]]]]];

But as you notice what I am doing is to reproduce a large pool of the possible matrices and then filtering them with regards to the constraint on the number of repeatings. So it's inefficient.

My function works for up to n = 4 even though it takes seconds for n = 4 but for n = 5 it fails because of memory constraint with shooting this error

General::nomem: The current computation was aborted because there was insufficientmemory available to complete the computation.

I need to compute for up to n = 15 and, therefore, need a better algorithm to find all the possible matrices given the constraints.

  • 2
    $\begingroup$ Sounds like the BKP problem, which is NP-complete. If so, I'd suggest giving up looking for ALL solutions, as there is no know algorithm which can solve it fast and completely. $\endgroup$
    – Silvia
    Commented Jun 20, 2013 at 19:01
  • $\begingroup$ Actually I need to have all the possible solutions!! The matrices are going to be ground of an economical theory evaluation!! What if I use a computer with 64GB ram and 12 CPUs??? $\endgroup$
    – Morry
    Commented Jun 20, 2013 at 19:08
  • $\begingroup$ Maybe LinearProgramming and LinearSolve would help. $\endgroup$
    – Silvia
    Commented Jun 20, 2013 at 19:31
  • $\begingroup$ May I ask you to explain a little more about your idea?? I am familiar with LP but no clues here!! $\endgroup$
    – Morry
    Commented Jun 20, 2013 at 19:40

2 Answers 2


Not a solution, but I think it would be REALLY hard to enumerate ALL solutions for matrices as large as $n=15$. I don't have a proof, just intuition coming from the size of the solution sets for relatively small $n$s.

The example setting $n=4$, $c=\{2, 4, 5, 5\}$, where $c_k$ denotes the repeating times of $k$, has 6720 solutions.

A setting I tried with $n=5$, $c=\{1, 2, 10, 1, 11\}$ has 151510 solutions.

$n=6$, $c=\{8, 1, 11, 2, 8, 6\}$ has ? (insufficient RAM here..) solutions.

Along with the number of solutions for $n=2$ and $n=3$, it looks like growing exponentially.

So I (wildly) guess the number of solutions for $n=15$ could require up to $\boldsymbol{10^{20}}$ Bytes or one hundred thousand Peta Bytes RAM, which will simply make it impossible even just to allocate them in RAM. Both time and memory costing are unpractical.

  • $\begingroup$ So what I should do is to change to another algorithm!! $\endgroup$
    – Morry
    Commented Jun 20, 2013 at 21:48
  • 1
    $\begingroup$ @user8144 As the limit is the scale of the final solution set itself, I think any algorithm will not be able to improve this problem. $\endgroup$
    – Silvia
    Commented Jun 20, 2013 at 21:52

The approach here is to first make a list of required elements, then successively pick valid orws from the remaining list.

I have not verified this is absolutely correct , but it should get you started..

stillneeded[ needed_, rows_ ] := 
   Module[{n0 = needed}, (n0 = Drop[n0, First@Position[n0, #]]) & /@  Flatten[ rows ]; n0]
KOCH[n_, req_] := Module[ {}, 
     needed = Flatten@ Table[j, {j, Length[req]}, {req[[j]]}];
     possible = {#} & /@ 
           Union[Select[ Subsets[needed, {n}] , # == Sort[#] & ]];
    Do[possible = 
         Flatten[Table[(Join[possible[[j]], {#}] & /@ 
           Subsets[ stillneeded[needed, possible[[j]]], {n}] , # ==  Sort[#] & ] ]) ,
                         {j, Length[possible]}], 1] ; 
         Print["row", irow + 1, "npos", Length[possible]], {irow,  n - 1}] ;  
                possible   ] /; (Total@req == n^2)
     Length[ KOCH[4, {2, 4, 5, 5}] ]
  • $\begingroup$ Thanks a lot @george2079 ..... I added DeleteDuplicates@(Sort /@ possible) to your code and it works proper and fast for n=5, but for n=6 it takes more than 6 hours to compute.... and imagine the larger n.... at least the RAM problem is vanished in your code!!! $\endgroup$
    – Morry
    Commented Jun 21, 2013 at 8:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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