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/