MathGroup Archive 2002

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

Search the Archive

Partitions

  • To: mathgroup at smc.vnet.net
  • Subject: [mg32839] Partitions
  • From: "Juan" <erfa11 at hotmail.com>
  • Date: Fri, 15 Feb 2002 02:49:36 -0500 (EST)
  • Sender: owner-wri-mathgroup at wolfram.com

Hello,
Looking in the package DiscreteMath`Combinatorica`,I can not find a
function to get the partitions of n, in  s parts.

A way to get the partitions of n, in s parts with diferents numbers is like 
that:
<< DiscreteMath`Combinatorica`

In[1]:= F1[n_, s_] := Select[Partitions[n],
   Length[#] == Length@Union[#] == s &]

In[2]:= F1[60, 8]; // Timing
Out[2]:= {170.315 Second, Null}


(If you try F1[100,10] ... is useless)


I need to do that for n=100, 200, 300,..., becouse I am writing a package to 
play lottery.

Using the brute force philosophy, I have wrote the function F2, which
is hundred of times faster:

In[3]:= F2[n_, s_, m_:1] :=
Module[{a = Array[p, s - 1], y, v, q, t, b = Abs[s - 2]},
    p[0] = m - 1;
    y = FoldList[Plus, 0, Range[n - 1]];
    v = {a, n - Plus @@ a} // Flatten;
    q = n - FoldList[Plus, 0, a];
    t = Table[{p[i + 1], p[i] + 1, (q[[i + 1]] - y[[s - i]])/(s - i)}, {i, 
0, s - 2}];
    Flatten[Table[v, Evaluate[Sequence @@ t]], b]]

In[4]:= F2[60, 8]; // Timing
Out[4]:= {0.06 Second, Null}

In[5]:= F1[20, 5]
Out[5]:= {{10, 4, 3, 2, 1}, {9, 5, 3, 2, 1}, {8, 6, 3, 2, 1}, {8, 5, 4, 2, 
1}, {7, 6, 4, 2, 1}, {7, 5, 4, 3, 1}, {6, 5, 4, 3, 2}}

In[6]:= F2[20, 5]
Out[6]:= {{1, 2, 3, 4, 10}, {1, 2, 3, 5, 9}, {1, 2, 3, 6, 8}, {1, 2, 4, 5, 
8}, {1, 2, 4, 6, 7}, {1, 3, 4, 5, 7}, {2, 3, 4, 5, 6}}

In[7]:= Length@F1[30, 5] == Length@F2[30, 5]
Out[7]:= True

In[8]:= F2[100, 10]; // Timing
Out[8]:= {3.014 Second, Null}

(F2 also works for m<=0)

Surely F2 can be improbe or samebody knows something better.Please send it 
here.

If you want all the partitions of n in diferents numbers you have to find 
F2[n, i] for i={1,2,3,...,(Sqrt[1+8n]-1)/2}

Regards
Juan

_________________________________________________________________
MSN Photos es la manera más sencilla de compartir e imprimir sus fotos: 
http://photos.latam.msn.com/Support/WorldWide.aspx



  • Prev by Date: Re: Notebook manipulation
  • Next by Date: Re: Nonatomic expression ? in Append command
  • Previous by thread: Partitions
  • Next by thread: Re: Partitions