MathGroup Archive: October 2009 [00160]

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

Re: Re: generating submultisets with repeated

To: mathgroup at smc.vnet.net
Subject: [mg103794] Re: [mg103784] Re: [mg103681] generating submultisets with repeated
From: David Bevan <david.bevan at pb.com>
Date: Tue, 6 Oct 2009 08:01:41 -0400 (EDT)
References: <200910051758.NAA11900@smc.vnet.net>

Here's another approach:

msNew[s_,k_]:=Flatten[Flatten[Outer[Inner[ConstantArray,#1,#2,Flatten[List[##],1]&,1]&,Subsets[s,{Length[#[[1]]]}],#,1],1]&/@Split[Flatten[Permutations/@IntegerPartitions[k],1],Length[#1]==Length[#2]&],1]

coinSetsNew[s_,k_]:=Join @@ Table[msNew[s,i],{i,k}]

coinSetsNew[{1,3,5,7},3]
{{1},{3},{5},{7},{1,1},{3,3},{5,5},{7,7},{1,3},{1,5},{1,7},{3,5},{3,7},{5,7},{1,1,1},{3,3,3},{5,5,5},{7,7,7},{1,1,3},{1,1,5},{1,1,7},{3,3,5},{3,3,7},{5,5,7},{1,3,3},{1,5,5},{1,7,7},{3,5,5},{3,7,7},{5,7,7},{1,3,5},{1,3,7},{1,5,7},{3,5,7}}

Length[coinSetsNew[Range[20],7]]//Timing

{11.297,888029}





It works by creating one multiset from each combination of a partition of k of length i and a subset of s with i elements. However, this approach doesn't create the multisets in lexicographic order.



David %^>









________________________________________
From: David Bevan [david.bevan at pb.com]
Sent: 05 October 2009 18:58
To: mathgroup at smc.vnet.net
Subject: [mg103794] [mg103784] Re: [mg103681] generating submultisets with repeated elements

Dan, Adriano, Kurt,

Thanks for the feedback.



Here are some performance results:



(* Dan *)

Length[multiSetsUpToK[Range[20],7]]//Timing

{18.14,888029}



(* Adriano *)

Length[coinSetsAdriano[Range[20],7]]//Timing

{9.516,888029}



(* Kurt *)

Length[coinSetsKurt[Range[20],7]]//Timing

Subsets::toomany: The number of subsets (189407486533) indicated by Subsets[{1,1,1,1,1,1,1,2,2,2,<<130>>},{1,7}] is too large; it must be a machine in =
teger.





And with my code:



Length[coinSets[Range[20],7]]//Timing

{5.063,888029}



My 'accumulator' approach seems to be quite effective!



However, I'm sure this can be improved significantly with the technique use=
=
d for KSubsets without too much difficulty.



David %^>

--_000_DE9DE45304B6FA4EBE8252CD4EBDA2418286B95F46PBINAMSG02MGD_
Content-Type: text/html; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
X-Sun-Content-Length: 2730

<html dir="ltr"><head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-=
1">
<style title="owaParaStyle"><!--P {
	MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px
}
--></style>
</head>
<body ocsi="x">
<p><font size="2" face="Courier New">Here's another approach:<br>
</font></p>
<p><font size="2" face="Courier New">msNew[s_,k_]:=Flatten[Flatten[Ou=
ter[Inner[ConstantArray,#1,#2,Flatten[List[##],1]&amp;,1]&amp;,Subsets[s,{L=
ength[#[[1]]]}],#,1],1]&amp;/@Split[Flatten[Permutations/@IntegerPartitions=
[k],1],Length[#1]==Length[#2]&amp;],1]</p>
<p><br>
coinSetsNew[s_,k_]:=Join @@ Table[msNew[s,i],{i,k}]<br>
<br>
coinSetsNew[{1,3,5,7},3]<br>
{{1},{3},{5},{7},{1,1},{3,3},{5,5},{7,7},{1,3},{1,5},{1,7},{3,5},{3,7},{5,7=
},{1,1,1},{3,3,3},{5,5,5},{7,7,7},{1,1,3},{1,1,5},{1,1,7},{3,3,5},{3,3,7},{=
5,5,7},{1,3,3},{1,5,5},{1,7,7},{3,5,5},{3,7,7},{5,7,7},{1,3,5},{1,3,7},{1,5=
,7},{3,5,7}}<br>
<br>
Length[coinSetsNew[Range[20],7]]//Timing<br>
</p>
<font face="Courier"><font face="Courier New"><font face="Courier New=
">
<p>{11.297,888029}</p>
</font></font></font>
<p>&nbsp;</p>
<p>&nbsp;</p>
<p>It works by creating&nbsp;one multiset from each combination of a&nbsp;p=
artition of k of length&nbsp;i and a subset of&nbsp;s with&nbsp;i elements.=
&nbsp;However, this approach doesn't create the multisets in lexicographic =
order.</p>
<p>&nbsp;</p>
<p>David %^&gt;</p>
<p>&nbsp;</p>
<p>&nbsp;</p>
<p>&nbsp;</p>
<p><br>
<br>
<br>
</font>________________________________________<br>
From: David Bevan [david.bevan at pb.com]<br>
Sent: 05 October 2009 18:58<br>
To: mathgroup at smc.vnet.net<br>
Subject: [mg103794] [mg103784] Re: [mg103681] generating submultisets with repeated el=
ements<br>
<br>
Dan, Adriano, Kurt,<br>
<br>
Thanks for the feedback.<br>
<br>
<br>
<br>
Here are some performance results:<br>
<br>
<br>
<br>
(* Dan *)<br>
<br>
Length[multiSetsUpToK[Range[20],7]]//Timing<br>
<br>
{18.14,888029}<br>
<br>
<br>
<br>
(* Adriano *)<br>
<br>
Length[coinSetsAdriano[Range[20],7]]//Timing<br>
<br>
{9.516,888029}<br>
<br>
<br>
<br>
(* Kurt *)<br>
<br>
Length[coinSetsKurt[Range[20],7]]//Timing<br>
<br>
Subsets::toomany: The number of subsets (189407486533) indicated by Subsets=
=<br>
[{1,1,1,1,1,1,1,2,2,2,&lt;&lt;130&gt;&gt;},{1,7}] is too large; it must be =
a machine in=<br>
teger.<br>
<br>
<br>
<br>
<br>
<br>
And with my code:<br>
<br>
<br>
<br>
Length[coinSets[Range[20],7]]//Timing<br>
<br>
{5.063,888029}<br>
<br>
<br>
<br>
My 'accumulator' approach seems to be quite effective!<br>
<br>
<br>
<br>
However, I'm sure this can be improved significantly with the technique use=
=<br>
d for KSubsets without too much difficulty.<br>
<br>
<br>
<br>
David %^&gt;</p>
</body>
</html>

--_000_DE9DE45304B6FA4EBE8252CD4EBDA2418286B95F46PBINAMSG02MGD_--

References:
- Re: generating submultisets with repeated elements
  - From: David Bevan <david.bevan@pb.com>

Prev by Date: Re: How to find which variable caused the trigger in Manipulate[]

Next by Date: Re: Colorfunction + parametricplot3d + plotrange = ?

Previous by thread: Re: generating submultisets with repeated elements

Next by thread: Re: generating submultisets with repeated elements