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

**References**:**Re: Re: List-Selection***From:*kewjoi@hixnet.co.za (Kew Joinery)

**Re: Mathematica programming language**

**Re: Defining new Forms**

**Re: Re: List-Selection**

**Re: Re: List-Selection**