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: Re: List-Selection