MathGroup Archive 1998

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

Search the Archive

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



  • Prev by Date: Help with list contour plot
  • Next by Date: how use short keys in mathematica 3.0 (PC Windows Version)
  • Previous by thread: Find combinations in k-subsets
  • Next by thread: finite element analysis in mathematica