Re: Find combinations in k-subsets
- To: mathgroup at smc.vnet.net
- Subject: [mg14155] Re: [mg14089] Find combinations in k-subsets
- From: Robert Pratt <rpratt at math.unc.edu>
- Date: Mon, 28 Sep 1998 18:57:20 -0400
- Sender: owner-wri-mathgroup at wolfram.com
In the case k=2, your problem is that of finding a maximum clique in a
graph. (A clique is a subset of vertices which induce a complete
graph.) The problem is known to be NP-complete, so NOBODY knows an
efficient algorithm. Nevertheless, for small instances, the following
code (based on MaximumClique in the Combinatorica package) should find
a maximum "generalized" clique in a reasonable amount of time:
Needs["DiscreteMath`Combinatorica`"]
FirstExample[lis_List,predicate_]:=Scan[(If[predicate[#],Return[#]])&,lis]
SubsetQ[x_List,y_List]:=Intersection[x,y]==x
MaxGeneralClique[lis_List]:={}/;lis==={}
MaxGeneralClique[lis_List]:=
Module[{d=Table[Count[lis,j,2],{j,1,Max[Flatten[lis]]}],
i,clique=Null,k,len=Length[First[lis]]},
i=Max[d];
While[(SameQ[clique,Null]),
k=Range[i];
clique=FirstExample[
KSubsets[Flatten[Position[d,_?((#>=i)&)]],i+1],
(SubsetQ[KSubsets[#,len],lis])&];i--;];clique]
mylist={{1,2,3},{1,2,4},{1,2,5},{1,2,6},{1,3,4},{1,3,5},{1,3,6},{1,4,6},
{2,3,4},{2,3,6},{2,4,6},{3,4,6}};
Timing[MaxGeneralClique[mylist]]
{0.01 Second,{1,2,3,4,6}}
If you want to find the extra subsets that don't fit, you can do:
Complement[mylist,KSubsets[MaxGeneralClique[mylist],Length[First[mylist]]]]
{{1,2,5},{1,3,5}}
Rob Pratt
Department of Mathematics
The University of North Carolina at Chapel Hill CB# 3250, 331 Phillips
Hall
Chapel Hill, NC 27599-3250
rpratt at math.unc.edu
http://www.math.unc.edu/Grads/rpratt/
On Fri, 25 Sep 1998, Carlos Carreto wrote:
> I would like to solve the following problem:
>
> Having k-subsets given in lexicographic order as input:
>
> {1,2,3},{1,2,4},{1,2,5},{1,2,6},{1,3,4},{1,3,5},{1,3,6},{1,4,6},
> {2,3,4},{2,3,6},{2,4,6},{3,4,6}
>
> I would like to determine the possible combinations.
>
> In this case the k-subsets:
>
> {1,2,3},{1,2,4},{1,2,6},{1,3,4},{1,3,6},{1,4,6},{2,3,4},
> {2,3,6},{2,4,6},{3,4,6}
>
> correspond to the combination: [{1, 2, 3, 4, 6}, 3]
>
> and there are two remaining k-subsets: {1,2,5} and {1,3,5}
>
> This is more or less the opposite of the function KSubsets[ ].
>
> Is there any function to do this?
> Can you think of an efficient algorithm?
>
> Thank you for your help
>
> -:- Carlos