combinatorics problem
- To: mathgroup at smc.vnet.net
- Subject: [mg40087] combinatorics problem
- From: "Szumiloski, John" <john_szumiloski at merck.com>
- Date: Wed, 19 Mar 2003 03:23:24 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
Dear MathGroupers,
(I use both v4.2 for WinNT 4 w/ 512MB RAM, and v4.0.1 for MacOS 8.6 w/ 160
MB RAM.)
I am trying to write a function which takes a list 'listA' of n integers
(perhaps nondistinct) and an arbitrary integer partition 'P' of n, and, for
the list of all the ways to partition the elements of listA into sublists of
the sizes given by P, sums each sublist for each instance and returns the
number of times each distinct set of sums (where the order is not important)
occurs. (Apologies for using 'partition' in two different ways here)
This is complicated, so an example definitely helps. Let's break the
problem up. Say the function prelimfunc returns a list of all the ways to
partition the elements of listA into sublists of the sizes given by P:
In[1]:= listA = {1,2,3,4,5} ; P = {2,2,1}; (* Note Length[listA] =
Apply[Plus,P] *)
In[2]:= pre1=prelimfunc[listA, P]
Out[2]= { {{1,2},{3,4},{5}}, {{1,2},{3,5},{4}}, {{1,2},{4,5},{3}},
{{1,3},{2,4},{5}}, {{1,3},{2,5},{4}}, {{1,3},{4,5},{2}},
{{1,4},{2,3},{5}}, {{1,4},{2,5},{3}}, {{1,4},{3,5},{2}},
{{1,5},{2,3},{4}}, {{1,5},{2,4},{3}}, {{1,5},{3,4},{2}},
{{2,3},{4,5},{1}}, {{2,4},{3,5},{1}}, {{2,5},{3,4},{1}} }
Desired properties of prelimfunc:
1) The order of the returned list is not important; the example's order was
just an artifact of my enumerating the result in my head.
2) The ordering of the sublists are not important. Thus, {{1,2},{3,4},{5}}
would be considered the same list as {{3,4},{1,2},{5}}, so only one would
appear in the result.
3) The ordering of the elements within each sublist are not important.
Thus, {{1,2},{3,4},{5}} would be considered the same list as
{{2,1},{3,4},{5}}, so only one would appear in the result.
4) Replicates of the elements of listA are considered distinct. This, if
listA={1,2,3,1,5} (where there are two elements equal to 1), there would be
two lists of {{1,3},{1,5},{2}} in the result, corresponding to the 6th and
12th list element in the above output. Since there are two "1"s in this
listA, this result would not violate property (2) above, since the "1"s are
considered distinct. Thus the result will always contain the same number of
possible partitions of listA so long as listA has same length n and the
integer partition of n remains the same.
The next operation would be, for each element in this list, to sum up each
sublist:
In[3]:= pre2=Map[Apply[Plus, #]&, pre1, {2}]
Out[3]= { {3, 7, 5}, {3, 8, 4}, {3, 9, 3}, {4, 6, 5}, {4, 7, 4},
{4, 9, 2}, {5, 5, 5}, {5, 7, 3}, {5, 8, 2}, {6, 5, 4},
{6, 6, 3}, {6, 7, 2}, {5, 9, 1}, {6, 8, 1}, {7, 7, 1} }
Next, determine the distinct set of sums:
In[4]:= pre3=Union[Map[Sort, pre2] ]
Out[4]= { {1, 5, 9}, {1, 6, 8}, {1, 7, 7}, {2, 4, 9}, {2, 5, 8},
{2, 6, 7}, {3, 3, 9}, {3, 4, 8}, {3, 5, 7}, {3, 6, 6},
{4, 4, 7}, {4, 5, 6}, {5, 5, 5} }
Next, for each of these sets, count how many times each appears in the
previous result (order not being important):
In[5]:= pre4=Map[Count[#, True]&, Outer[SameQ, pre3, Map[Sort, pre2], 1] ]
Out[5]= {1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1}
Last, return the unique sets of sums with the number of times each appears:
In[6]:= Thread[List[pre3, pre4] ] (* for example *)
Out[6]= { {{1, 5, 9}, 1}, {{1, 6, 8}, 1}, {{1, 7, 7}, 1}, {{2, 4, 9}, 1},
{{2, 5, 8}, 1}, {{2, 6, 7}, 1}, {{3, 3, 9}, 1}, {{3, 4, 8},
1},
{{3, 5, 7}, 2}, {{3, 6, 6}, 1}, {{4, 4, 7}, 1}, {{4, 5, 6},
2},
{{5, 5, 5}, 1} }
So I want a function myfunc which would do this:
In[7]:= myfunc[listA, P]
Out[7]= { {{1, 5, 9}, 1}, {{1, 6, 8}, 1}, {{1, 7, 7}, 1}, {{2, 4, 9}, 1},
{{2, 5, 8}, 1}, {{2, 6, 7}, 1}, {{3, 3, 9}, 1}, {{3, 4, 8},
1},
{{3, 5, 7}, 2}, {{3, 6, 6}, 1}, {{4, 4, 7}, 1}, {{4, 5, 6},
2},
{{5, 5, 5}, 1} }
Another example, with more multiplicities:
In[8]:= myfunc[{1,1,2,2,3}, {2,2,1}]
Out[8]= { {{1, 3, 5}, 4}, {{1, 4, 4}, 2}, {{2, 2, 5}, 2},
{{2, 3, 4}, 5}, {{3, 3, 3}, 2} }
I have figured out how to write a naive version of prelimfunc by 1) simply
enumerating all permutations of listA, 2) pruning (if P has some repeated
elements; accounts for property (2) above), 3) inserting braces in the
appropriate places. So with the additional steps above given explicitly, in
a sense I have solved my problem.
****However****, I would like a solution which does not have intermediate
steps that consume memory (and time?) at an (supra-?)exponential rate. I am
interested in using listA of 30-40 elements or maybe more (!).
One approach could be to enumerate the distinct set of sums (e.g., pre3)
first, then determine how many times each would appear. I have written this
function which enumerates the possible sum sets, based loosely on the
Partitions code in the Combinatorica package:
(******** Begin code ********)
NonZeroCompositions[totalsum_Integer /; totalsum <= 1, ___] := {};
NonZeroCompositions[totalsum_Integer, ngroups_Integer /; ngroups < 1, ___]
:= {};
NonZeroCompositions[totalsum_Integer, 1, ___ ] := {{totalsum}};
NonZeroCompositions[totalsum_Integer, ngroups_Integer, ___] /; (ngroups >
totalsum) := {};
NonZeroCompositions[totalsum_Integer, ngroups_Integer] :=
NonZeroCompositions[totalsum, ngroups] =
NonZeroCompositions[totalsum, ngroups, 1];
NonZeroCompositions[totalsum_Integer, ngroups_Integer,
low_Integer] /; (low * ngroups > totalsum)
:= {};
(* ...and the workhorse... *)
NonZeroCompositions[totalsum_Integer, ngroups_Integer, low_Integer] :=
Partition[Flatten[Table[Map[Append[{i}, #] &,
NonZeroCompositions[totalsum -
i, ngroups - 1, i]],
{i, low, Floor[totalsum/ngroups]}
]
],
ngroups];
(******** End code ********)
The argument totalsum refers to the sum of the elements of listA (so the sum
over each set in the result is also this), and ngroups to the number of
elements in the partition P. Thus to get the candidate sum sets for the
example, we do
In[8]:= sets=NonZeroCompositions[Apply[Plus, listA] (* = 15 *), Length[P] (*
= 3 *) ]
Out[8]= { {1, 1, 13}, {1, 2, 12}, {1, 3, 11}, {1, 4, 10}, {1, 5, 9}, {1, 6,
8},
{1, 7, 7}, {2, 2, 11}, {2, 3, 10}, {2, 4, 9}, {2, 5, 8}, {2,
6, 7},
{3, 3, 9}, {3, 4, 8}, {3, 5, 7}, {3, 6, 6}, {4, 4, 7}, {4, 5,
6},
{5, 5, 5} }
Now some of these do not appear in pre3 (e.g., {1,1,13}); without loss of
generality I would have my function not include such sum sets in the final
result.
Given 'listA', 'P', and now 'sets', I suspect I can Map 'sets' into a
function of listA and P which counts the number of times each sum set would
appear, **without** actually enumerating all the partitions, summing etc.,
etc. I strongly suspect this can be done using Backtrack from the
Combinatorica package. But this is now getting beyond my level of
Mathematica competence.
Any assistance would be most welcome; suggestions of course do not have to
utilize my NonZeroCompositions function, although I suspect it would be
useful. If I get more than one approach, I may summarize some performance
benchmarks for the group.
Thanks in advance for any insights.
John
------------------------------------------------------------------------------
Notice: This e-mail message, together with any attachments, contains information of Merck & Co., Inc. (Whitehouse Station, New Jersey, USA) that may be confidential, proprietary copyrighted and/or legally privileged, and is intended solely for the use of the individual or entity named on this message. If you are not the intended recipient, and have received this message in error, please immediately return this by e-mail and then delete it.
==============================================================================
- Follow-Ups:
- Re: combinatorics problem
- From: Dr Bob <drbob@bigfoot.com>
- Re: combinatorics problem
- From: Dr Bob <drbob@bigfoot.com>
- Re: combinatorics problem