RE: Q: extract all k-tuple from a list of n elements
- To: mathgroup at smc.vnet.net
- Subject: [mg49688] RE: [mg49650] Q: extract all k-tuple from a list of n elements
- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
- Date: Thu, 29 Jul 2004 07:42:50 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
>-----Original Message----- >From: Klaus Duellmann [mailto:klaus.duellmann at arcor.de] To: mathgroup at smc.vnet.net >Sent: Monday, July 26, 2004 10:02 AM >To: mathgroup at smc.vnet.net >Subject: [mg49688] [mg49650] Q: extract all k-tuple from a list of n elements > > >Question: How can I extract all k-tuple from a list of n elements >(without considering permutations of the k-tuple)? > >Example: For the special case k=3 one solution would be > >Flatten[Table[{i, j, k}, {i, 1, n - 2}, {j, i + 1, n - 1}, {k, j + 1, >n}], 2]; > >A generalization of this solution for all k >=1 would involve >to create >'automatically' a table of dimension k, but how can this be >implemented? > >Any help is appreciated. > >Regards, > >Klaus > > Klaus, you may glimpse (spicken) into In[7]:= << DiscreteMath`Combinatorica` In[8]:= KSubsets[{1, 2, 3, 4, 5}, 3] Out[8]= {{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}} but to give you a hint: think recusively! Here is quite a different method (perhaps more performant, didn't check) generalizing you case for any (sensible) k: In[43]:= ksets[n_, 0] := {{}} In[44]:= ksets[n_Integer, k_Integer?Positive] /; k <= n := With[{vars = Table[jj[kk], {kk, k}]}, Flatten[Table[vars, ##], k - 1] & @@ Rest@FoldList[{#2, #1[[1]] + 1, #1[[-1]] + 1} &, {0, 0, n - k}, vars]] In[45]:= ksets[5, 3] Out[45]= {{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}} -- Hartmut Wolf