MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: Re: List-Selection

  • To: mathgroup at
  • Subject: [mg20331] Re: [mg20157] Re: [mg20060] Re: [mg20021] List-Selection
  • From: Daniel Lichtblau <danl at>
  • Date: Fri, 15 Oct 1999 20:20:52 -0400
  • References: <>
  • Sender: owner-wri-mathgroup at

Kew Joinery wrote:
> Hello Everyone ,
> I would like to thank Mr. Kozlowski  for spending more then 2 hours for this
> problem. (I spent much more- Human  is curious about unknown).
> The example illustrate the ability of Mathematica to be weak in the most important
> spectrum of Discrete Mathematics Searching (Sorting is handily controlled). There
> is no build  in function Search (probably is impossible to build  in one). The
> best custom implementation is Combinatoricas Backtrack, because is using bit vector
> (incrementing) and one could be able to search longer  without run out of memory.
> Mr. Hayess backtrack is faster but is memory hungry .So Mathematica needs one
> build-in function just to perform at least exhaustive search over a candidate
> solutions. Better one would be to involve pruning possibilities like cut off
> k-subsets from rank r1 to rankr2.
>   Consider in this case custom implementation  construct all 7-subsets from 32 set
> (which is 3365856) and map them over the matrix, then perform exhaustive search.
> Thanks to Mr. Pratt for the nice pruning in the solution space. So Mr.Kozlowski was
> patient to perform complete search and to find all 320 solutions.
>  Now I ask you  how to approach the next instance?
> This is steal small instance: n=6 so the desirable matrix is m(64x7)
> Note: to construct matrix whit property NO number appears twice in the same column
> or the same row + that all numbers are equally distributed   the matrix should be
> long prime.
> *** the task is: Find JUST ONE solution satisfying the condition:
> Union[Flatten[ some 12 rows of m ]] = = Range[64]
>  Here is the modest matrix for n=6 >m( 2^6=64  x  n+1=7)
> [... Reproduced in reply below. dl]
> Eugene

matbig =

I first tried a greedy algorithm which bogged down and gave no
indication of wanting to get the full set using just 12 rows. So instead
I formulated it as a global optimization problem suitable for a numeric
minimizer. This may be done as follows. We define a function g[...]
that, given a vector of real values between 0 and #rows, rounds off,
adds 1, and produces those matrix rows.

There is a bit of further machination in the g[...] to work around a
minor weakness in a minimizer package we have in development.
Specifically, in the process we may get vectors with components less
than 0 or greater than the given maximum bound, and we need to make
g[...] handle this.

Our objective function f[...] then flattens the rows, takes the
complement of this set from the master set, and raises 2 to that power
(not really necessary). We hope to get a result of 1, indicating the
complement is empty.

g[n_,mat_,mx_Integer] := mat[[Map[Min[Max[Floor[#],0],mx-1]&,n]+1]]

f[{n___Real},mat_,mx_Integer] := [n_,mat_,mx_Integer] :=

rnum = 12;
vars = Array[xx,rnum];
rnges = Apply[Sequence,Map[{#,0,Length[matbig]}&, vars]];

Now I do:

Timing[{nmin,vals} = NMinimize[f[vars,matbig,Length[matbig]], rnges,...]
(options and warning messages excised, this stuff is still under

Out[78]= {1076.33 Second, {1, {xx[1] -> 1.74308, xx[2] -> 28.5045, 
  xx[3] -> 17.5805, xx[4] -> 11.9106, xx[5] -> 58.6166, 
  xx[6] -> 8.68512, xx[7] -> 42.3791, xx[8] -> 32.6406, 
  xx[9] -> 55.4619, xx[10] -> 25.6583, xx[11] -> 35.0879, 
  xx[12] -> 50.5449}}}

We write the row indices in an acceptable form:

In[84]:= rows = Sort[Floor[vars /. vals] + 1]
Out[84]= {2, 9, 12, 18, 26, 29, 33, 36, 43, 51, 56, 59}

We check that these rows indeed cover the set.

In[85]:= Union[Flatten[matbig[[rows]]]] === Range[64]
Out[85]= True

I believe this is useful technology and I hope to see this numerical
optimizer become an add-on standard package in a future release.

Daniel Lichtblau
Wolfram Research

  • Prev by Date: Re: Mathematica programming language
  • Next by Date: Re: Defining new Forms
  • Previous by thread: Re: Re: List-Selection
  • Next by thread: Re: Re: List-Selection