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

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