MathGroup Archive 1999

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

Search the Archive

Re: Re: Re: List-Selection

  • To: mathgroup at smc.vnet.net
  • Subject: [mg20331] Re: [mg20157] Re: [mg20060] Re: [mg20021] List-Selection
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Fri, 15 Oct 1999 20:20:52 -0400
  • References: <199910020705.DAA08176@smc.vnet.net.>
  • Sender: owner-wri-mathgroup at wolfram.com

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 =
{{1,2,4,8,16,32,64},{2,1,3,7,15,31,63},{3,4,2,6,14,30,62},{4,3,1,5,13,29,61},{
   
5,6,8,4,12,28,60},{6,5,7,3,11,27,59},{7,8,6,2,10,26,58},{8,7,5,1,9,25,
   
57},{9,10,12,16,8,24,56},{10,9,11,15,7,23,55},{11,12,10,14,6,22,54},{12,
   
11,9,13,5,21,53},{13,14,16,12,4,20,52},{14,13,15,11,3,19,51},{15,16,14,10,
   
2,18,50},{16,15,13,9,1,17,49},{17,18,20,24,32,16,48},{18,17,19,23,31,15,
   
47},{19,20,18,22,30,14,46},{20,19,17,21,29,13,45},{21,22,24,20,28,12,44},{
   
22,21,23,19,27,11,43},{23,24,22,18,26,10,42},{24,23,21,17,25,9,41},{25,26,
   
28,32,24,8,40},{26,25,27,31,23,7,39},{27,28,26,30,22,6,38},{28,27,25,29,
   
21,5,37},{29,30,32,28,20,4,36},{30,29,31,27,19,3,35},{31,32,30,26,18,2,
   
34},{32,31,29,25,17,1,33},{33,34,36,40,48,64,32},{34,33,35,39,47,63,31},{
   
35,36,34,38,46,62,30},{36,35,33,37,45,61,29},{37,38,40,36,44,60,28},{38,
   
37,39,35,43,59,27},{39,40,38,34,42,58,26},{40,39,37,33,41,57,25},{41,42,
   
44,48,40,56,24},{42,41,43,47,39,55,23},{43,44,42,46,38,54,22},{44,43,41,
   
45,37,53,21},{45,46,48,44,36,52,20},{46,45,47,43,35,51,19},{47,48,46,42,
   
34,50,18},{48,47,45,41,33,49,17},{49,50,52,56,64,48,16},{50,49,51,55,63,
   
47,15},{51,52,50,54,62,46,14},{52,51,49,53,61,45,13},{53,54,56,52,60,44,
   
12},{54,53,55,51,59,43,11},{55,56,54,50,58,42,10},{56,55,53,49,57,41,9},{
   
57,58,60,64,56,40,8},{58,57,59,63,55,39,7},{59,60,58,62,54,38,6},{60,59,
   
57,61,53,37,5},{61,62,64,60,52,36,4},{62,61,63,59,51,35,3},{63,64,62,58,
    50,34,2},{64,63,61,57,49,33,1}};


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] :=
mat[[Map[Min[Max[Fl
  2^Length[Complement[Range[mx],Union[Flatten[g[{n},mat,mx]]]]]

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
development).

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