MathGroup Archive 2001

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

Search the Archive

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




  • Prev by Date: RE: parametric plots
  • Next by Date: Re: [Q] Generalized Partitions
  • Previous by thread: Re: [Q] Generalized Partitions
  • Next by thread: Re: [Q] Generalized Partitions