MathGroup Archive 2001

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

Search the Archive

Re: [Q] Generalized Partitions

  • To: mathgroup at smc.vnet.net
  • Subject: [mg29976] Re: [mg29942] [Q] Generalized Partitions
  • From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
  • Date: Fri, 20 Jul 2001 03:28:39 -0400 (EDT)
  • Sender: owner-wri-mathgroup at wolfram.com

After sending this reply I realized that depending on the length of the list
and the size of n there will be different algorithms that will be more
efficient. The algorithm I sent (OrderedPartitions) first builds the set of
all compositions of k numbers that add up to n, and then selects from them
those that consist entirely of elements of the given list l. But if l is
short it will be more efficient to first built a list of all sets of k
elements of l and then select from them those which add up to n. The
following code does this:
In[1]:=
<<DiscreteMath`Combinatorica`

In[2]:=
OrderedPartitions1[n_, k_, l_List] :=
  Select[Flatten[Outer[List, Sequence @@ Table[l, {k}]],
    k - 1], Tr[#1] == n & ]
The earlier definiton was:
In[3]:=
OrderedPartitions[n_, k_, l_List] :=
  Select[Compositions[n, k], Complement[#1, l] == {} & ]
Let's take a short list:
In[4]:=
l={1,3,4};

Comparing

In[5]:=
OrderedPartitions1[10,5,l]//Timing
Out[5]=
{0.01 
Second,{{1,1,1,3,4},{1,1,1,4,3},{1,1,3,1,4},{1,1,3,4,1},{1,1,4,1,3},{1,
      
1,4,3,1},{1,3,1,1,4},{1,3,1,4,1},{1,3,4,1,1},{1,4,1,1,3},{1,4,1,3,1},{1,
      
4,3,1,1},{3,1,1,1,4},{3,1,1,4,1},{3,1,4,1,1},{3,4,1,1,1},{4,1,1,1,3},{4,
      1,1,3,1},{4,1,3,1,1},{4,3,1,1,1}}}
With 
In[6]:=
OrderedPartitions[10,5,l]//Timing
Out[6]=
{0.52 
Second,{{1,1,1,3,4},{1,1,1,4,3},{1,1,3,1,4},{1,1,3,4,1},{1,1,4,1,3},{1,
      
1,4,3,1},{1,3,1,1,4},{1,3,1,4,1},{1,3,4,1,1},{1,4,1,1,3},{1,4,1,3,1},{1,
      
4,3,1,1},{3,1,1,1,4},{3,1,1,4,1},{3,1,4,1,1},{3,4,1,1,1},{4,1,1,1,3},{4,
      1,1,3,1},{4,1,3,1,1},{4,3,1,1,1}}}
we see that OrderedPartitions1 is over 50 times faster in this case.

on 01.7.19 10:33 PM, Andrzej Kozlowski at andrzej at tuins.ac.jp wrote:

> You do not state if the partitions should be into ordered or un-ordered sets.
> Anyway, probably the easiest way is to make use of the standard package
> Combinatorica:
> 
> In[1]:=
> <<DiscreteMath`Combinatorica`
> 
> In[2]:=
> OrderedPartitions[n_, k_, l_List] :=
> Select[Compositions[n, k], Complement[#1, l] == {}& ]
> 
> In[3]:=
> UnorderedPartitions[n_, k_, l_List] :=
> Select[OrderedPartitions[n, k, l], OrderedQ]
> 
> Using your list:
> 
> In[4]:=
> l={1,3,4,5,6,7,9};
> 
> In[5]:=
> OrderedPartitions[10,2,l]
> Out[5]=
> {{1,9},{3,7},{4,6},{5,5},{6,4},{7,3},{9,1}}
> In[6]:=
> UnorderedPartitions[10,2,l]
> Out[6]=
> {{1,9},{3,7},{4,6},{5,5}}

-- 
Andrzej Kozlowski
Toyama International University
JAPAN

http://platon.c.u-tokyo.ac.jp/andrzej/
http://sigma.tuins.ac.jp/~andrzej/



  • Prev by Date: Re: Mathematica generating gifs for avi problem
  • Next by Date: Re: Mathematica generating gifs for avi's
  • Previous by thread: Re: [Q] Generalized Partitions
  • Next by thread: Re: [Q] Generalized Partitions