Re: [Q] Generalized Partitions

*To*: mathgroup at smc.vnet.net*Subject*: [mg29993] Re: [mg29942] [Q] Generalized Partitions*From*: Andrzej Kozlowski <andrzej at tuins.ac.jp>*Date*: Sat, 21 Jul 2001 00:49:01 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

Since your problem involves rather large numbers none of the methods I have suggested so far will work. Both of them build up unnecessarily long lists. The method to use is known as backtracking. The most efficient way would be to write your own backtracking program. However, one can also rely on the already existing "general" one in the Combinatorica package. In your case it will take a very long time (you need a fast computer and be ready to wait). To speed up thecomputations it would be a good idea to be able to Compile the Backtrack function. I have not quite been able to do this so far (I would need to think about it more, as there seem to be some difficulties and I have little experience with compiling functions) but I have complied a one component of the function (the Solution function below) which results in a speed up of 55%. Compiling the entire function should result in additional gains. Here is the code of the Backtrack function taken form the Combinatorica package and modified to use Compile: In[1]:= Backtrack[space_List,partialQ_,solutionQ_,flag_:One] := Module[{n=Length[space],all={},done,index,v=2,solution}, index=Prepend[ Table[0,{n-1}],1]; While[v > 0, done = False; While[!done && (index[[v]] < Length[space[[v]]]), index[[v]]++; done = Apply[partialQ,{Solution[space,index,v]}]; ]; If [done, v++, index[[v--]]=0 ]; If [v > n, solution = Solution[space,index,n]; If [Apply[solutionQ,{solution}], If [SameQ[flag,All], AppendTo[all,solution], all = solution; v=0 ] ]; v-- ] ]; all ]; In[2]:= Solution=Compile[{{space,_Integer,2},{index,_Integer,1},{count,_Integer}}, Module[{i}, Table[space[[ i,index[[i]] ]], {i,count}] ]] Now we set up the auxiliary functions for our problem and the problem itself. I shall much smaller data than you want to use. This much smaller example below is pretty fast: In[3]:= l={1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,47,50,53,56,59}; In[4]:= k=6; In[5]:= n=51; In other words, we shall try to find the partitions of 51 as a sum of 6 members of the list l. Next we define the solution space for our problem, the test for a partial solution (a potential solution is rejected if it fails the test) and the test for the final solution. In[6]:= sp = Table[l, {k}]; In[7]:= partialQ[l_, n_] := Tr[l] + (k - Length[l])*Min[l] <= n && Tr[l] + (k - Length[l])*Max[l] >= n In[8]:= solutionQ[l_, n_] := Tr[l] == n Now we can run our program: In[9]:= Length[Backtrack[sp,partialQ[#,n]&,solutionQ[#,n]&,All]]//Timing Out[9]= {10.4333 Second,1386} This was done on a 400 MHZ Macintosh. The problem is certainly of high time complexity so for your size of data I would expect a very long wait. -- Andrzej Kozlowski Toyama International University JAPAN http://platon.c.u-tokyo.ac.jp/andrzej/ on 01.7.19 11:43 PM, Janusz Kawczak at jkawczak at uncc.edu wrote: > Dear Andrzej: > > thank you for your e-mail. Indeed, your solution seems to do the job, but > for a quite small data. I am trying to get the following partition into an > ordered sets and I am interested ONLY in the cardinality of the set. Here > is the magnitude of one of my problems: > > l={1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 47, 50, 53, > 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, 101, 104, 107, > 110, 113, 116, 119, 122, 125, 128, 131, 134, 138, 142, 146, 150, 155, 160, > 165, 170, > 175} > > The numbers to be partinioned are at least 2500 and they are composed of > 18 elements. When I tried your function I got an error message that the > number of iterations (256) has be exceeded, i.e. in you function > > Length[OrderedPartitions[2500, 18, l]] > > Any suggestions? > > Dziekuje za pomoc. > Janusz. > > ** Janusz Kawczak ** > ** UNC at Charlotte, Department of Mathematics, Room 350F ** > ** 9201 University City Blvd. ** > ** Charlotte, NC, 28223-0001, U.S.A. ** > ** Tel.: (704) 687-2566 (W) (704) 921-0273 (H) Fax.: (704) 687-6415 ** > > On Thu, 19 Jul 2001, Andrzej Kozlowski wrote: > > andrze>You do not state if the partitions should be into ordered or un-ordered > andrze>sets. Anyway, probably the easiest way is to make use of the standard > andrze>package Combinatorica: > andrze> > andrze>In[1]:= > andrze><<DiscreteMath`Combinatorica` > andrze> > andrze>In[2]:= > andrze>OrderedPartitions[n_, k_, l_List] := > andrze> Select[Compositions[n, k], Complement[#1, l] == {}& ] > andrze> > andrze>In[3]:= > andrze>UnorderedPartitions[n_, k_, l_List] := > andrze> Select[OrderedPartitions[n, k, l], OrderedQ] > andrze> > andrze>Using your list: > andrze> > andrze>In[4]:= > andrze>l={1,3,4,5,6,7,9}; > andrze> > andrze>In[5]:= > andrze>OrderedPartitions[10,2,l] > andrze>Out[5]= > andrze>{{1,9},{3,7},{4,6},{5,5},{6,4},{7,3},{9,1}} > andrze>In[6]:= > andrze>UnorderedPartitions[10,2,l] > andrze>Out[6]= > andrze>{{1,9},{3,7},{4,6},{5,5}} > andrze> > andrze>-- > andrze>Andrzej Kozlowski > andrze>Toyama International University > andrze>JAPAN > andrze> > andrze>http://platon.c.u-tokyo.ac.jp/andrzej/ > andrze>http://sigma.tuins.ac.jp/~andrzej/ > >