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