Re: [Q] Generalized Partitions
- To: mathgroup at smc.vnet.net
- Subject: [mg30013] Re: [mg29942] [Q] Generalized Partitions
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Sat, 21 Jul 2001 00:49:23 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Just one more improvement. Changing the code for partialQ to: partialQ[l_] /; Length[l] == 1 = True; partialQ[l_] := Tr[l] + (k - Length[l])*Max[l] <= n && Tr[l] + (k - Length[l])*Max[L] >= n &&l[[-1]] >= l[[-2]]; solutionQ[l_] := Tr[l] == n; (Note Max[l] and Max[L]) will produce a very substantial speed gain. Of course the command to run the final evaluation (omitted form my code last time) is: Lengtth[Backtrack[sp,partialQ,solutionQ,All]]//Timing -- Andrzej Kozlowski Toyama International University JAPAN http://platon.c.u-tokyo.ac.jp/andrzej/ http://sigma.tuins.ac.jp/~andrzej/ on 01.7.21 8:46 AM, Andrzej Kozlowski at andrzej at tuins.ac.jp wrote: > Unfortunately the code I sent below contained one silly mistake (more of a > misprint) and one "misjudgement". The mistake is in the code where I should > have distinguished the given list (which I shall denote by capital letter L) > and the partial solution l. The misjudgement was counting separately > permutations of the same solutions which greatly increases their number. So > here is my corrected code in the same case as below. I Use the same modified > Backtrack function (by the way you need not worry about all spell messages > Mathematica produces when that is evaluated): > > We begin as below (but note the capital L!): > > In[5]:= > n=51; > k=6; > In[7]:= > L={1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,47,50,53,56,59}; > In[8]:= > sp=Table[L,{k}]; > > > partialQ[l_] /; Length[l] == 1 = True; > partialQ[l_] := Tr[l] + (k - Length[l])*Min[L] <= n && Tr[l] + (k - > Length[l])*Max[L] >= n &&l[[-1]] >= l[[-2]]; > solutionQ[l_] := Tr[l] == n; > > Notice the capilal and small l's. Also, I have added the conditions that the > numbers in solutions should not decrease: > > {5.79 Second,{{1,1,1,1,4,43},{1,1,1,1,7,40},{1,1,1,1,10,37},{1,1,1,1,13, > 34},{1,1,1,1,16,31},{1,1,1,1,19,28},{1,1,1,1,22,25},{1,1,1,4,4,40},{1,1, > 1,4,7,37},{1,1,1,4,10,34},{1,1,1,4,13,31},{1,1,1,4,16,28},{1,1,1,4,19, > 25},{1,1,1,4,22,22},{1,1,1,7,7,34},{1,1,1,7,10,31},{1,1,1,7,13,28},{1,1, > 1,7,16,25},{1,1,1,7,19,22},{1,1,1,10,10,28},{1,1,1,10,13,25},{1,1,1,10, > 16,22},{1,1,1,10,19,19},{1,1,1,13,13,22},{1,1,1,13,16,19},{1,1,1,16,16, > 16},{1,1,4,4,4,37},{1,1,4,4,7,34},{1,1,4,4,10,31},{1,1,4,4,13,28},{1,1, > 4,4,16,25},{1,1,4,4,19,22},{1,1,4,7,7,31},{1,1,4,7,10,28},{1,1,4,7,13, > 25},{1,1,4,7,16,22},{1,1,4,7,19,19},{1,1,4,10,10,25},{1,1,4,10,13, > 22},{1,1,4,10,16,19},{1,1,4,13,13,19},{1,1,4,13,16,16},{1,1,7,7,7, > 28},{1,1,7,7,10,25},{1,1,7,7,13,22},{1,1,7,7,16,19},{1,1,7,10,10,22},{1, > 1,7,10,13,19},{1,1,7,10,16,16},{1,1,7,13,13,16},{1,1,10,10,10,19},{1,1, > 10,10,13,16},{1,1,10,13,13,13},{1,4,4,4,4,34},{1,4,4,4,7,31},{1,4,4,4, > 10,28},{1,4,4,4,13,25},{1,4,4,4,16,22},{1,4,4,4,19,19},{1,4,4,7,7, > 28},{1,4,4,7,10,25},{1,4,4,7,13,22},{1,4,4,7,16,19},{1,4,4,10,10,22},{1, > 4,4,10,13,19},{1,4,4,10,16,16},{1,4,4,13,13,16},{1,4,7,7,7,25},{1,4,7,7, > 10,22},{1,4,7,7,13,19},{1,4,7,7,16,16},{1,4,7,10,10,19},{1,4,7,10,13, > 16},{1,4,7,13,13,13},{1,4,10,10,10,16},{1,4,10,10,13,13},{1,7,7,7,7, > 22},{1,7,7,7,10,19},{1,7,7,7,13,16},{1,7,7,10,10,16},{1,7,7,10,13, > 13},{1,7,10,10,10,13},{1,10,10,10,10,10},{4,4,4,4,4,31},{4,4,4,4,7, > 28},{4,4,4,4,10,25},{4,4,4,4,13,22},{4,4,4,4,16,19},{4,4,4,7,7,25},{4,4, > 4,7,10,22},{4,4,4,7,13,19},{4,4,4,7,16,16},{4,4,4,10,10,19},{4,4,4,10, > 13,16},{4,4,4,13,13,13},{4,4,7,7,7,22},{4,4,7,7,10,19},{4,4,7,7,13, > 16},{4,4,7,10,10,16},{4,4,7,10,13,13},{4,4,10,10,10,13},{4,7,7,7,7, > 19},{4,7,7,7,10,16},{4,7,7,7,13,13},{4,7,7,10,10,13},{4,7,10,10,10, > 10},{7,7,7,7,7,16},{7,7,7,7,10,13},{7,7,7,10,10,10}}} > > This looks to me already like a reasonable code to try running on your problem > with n=2500 and k =18. I think I shall try running it overningth myself. >