Re: Re: List-Selection

*To*: mathgroup at smc.vnet.net*Subject*: [mg20157] Re: [mg20060] Re: [mg20021] List-Selection*From*: kewjoi at hixnet.co.za (Kew Joinery)*Date*: Sat, 2 Oct 1999 03:05:12 -0400*Sender*: owner-wri-mathgroup at wolfram.com

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) {{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}} Note: use ColumnForm to see some nice features of m. Thank you for your attention and any suggestions. Eugene

**Follow-Ups**:**Re: Re: Re: List-Selection***From:*Daniel Lichtblau <danl@wolfram.com>