3
$\begingroup$

Folks,

I am trying to construct and algorithm which finds all of the remaining groupings (of three items, in this case) from a list of items for which no two items are in groups that have previously been formed. Here is what I wrote, which seemed pretty straightforward to me:

makeGroups[myList_, existingGroups_] := 
   Complement[Subsets[myList, {3}], existingGroups,
   SameTest -> (Length[Intersection[#1, #2]] >= 2 &)]

My thinking is that the defined "SameTest" should be comparing each item in the Subsets constructed from myList to the entries in existingGroups and rejecting items which have 2 or more overlaps with any entry in existingGroups.

However, when I run this on the following lists:

myList = Range[15];

existingGroups = Partition[Range[15],3];

I get results which do not include some obviously unique groups (there is no group which has 1 and 15 in it, for example).

Any ideas where I have gone off the rails?

Alternatively, if you have a better way of solving this same problem I would love to hear/see it.

$\endgroup$
  • $\begingroup$ Interesting sub-problem. How large are the lists you'll be dealing with? As it stands, the only answer currently posted will be very slow on large lists. Do you need to handle other than trivially small cases? $\endgroup$ – ciao Apr 1 '15 at 5:37
1
$\begingroup$

Can you check if this works for you?

With[{p = Subsets[myList, {3}]},
 Pick[p, And @@@ 
   Table[(Length@Intersection[#, p[[i]]] < 2) & /@ existingGroups, {i,
      1, Length[p]}]]]
$\endgroup$
  • $\begingroup$ That does seem to work (though I haven't had time to thoroughly check the sets produced just yet). Great solution! $\endgroup$ – Marshall Bartlett Mar 31 '15 at 18:02
  • 1
    $\begingroup$ I am still curious, though, why the "SameTest" doesn't seem to be doing what I intended. It is odd that it only returns a partial set of the full solution space. Can't quite wrap my head around where it is going awry. $\endgroup$ – Marshall Bartlett Mar 31 '15 at 18:04
  • 1
    $\begingroup$ @MarshallBartlett: It's doing precisely what it says it's supposed to. Read the doc. description carefully. The first "pass" is equivalent to reducing your targets from myList as DeleteDuplicates[Subsets[myList, {3}], Length@Intersection[#1, #2] >= 2 &], then that is complemented with your existing groups using your test. $\endgroup$ – ciao Apr 1 '15 at 4:56
  • $\begingroup$ @rasher: Thanks for the comment, rasher. I was not considering that Complement would compare elements of myList with one another (which, of course, it should) using SameTest as well. Thanks for pointing it out! $\endgroup$ – Marshall Bartlett Apr 1 '15 at 18:25
0
$\begingroup$

A quick follow-up to my comment question (don't know if useful if only trivially small cases are of import to you).

With tasks like this (generation followed by filtering), one should ask "Can I reduce the filtering?" - either by minimizing that to be filtered, improving the efficiency of filtering, or both, and even more so, "Can I eliminate filtering and generate the desired results directly?".

Here's a couple of tacks along those lines:

fn[lst_, exi_] := Module[{tr, f, a1, a2, a3},
  tr = Append[#, _] & /@ Join @@ (Subsets[#, {2}] & /@ exi);
  SetAttributes[f, Orderless];
  f[a1_, a2_, a3_] = {a1, a2, a3};
  (f[Sequence @@ #] = Unevaluated@Sequence[];) & /@ tr;
  f @@@ lst];

gen = Module[{pp = Partition[#, 3, 3, {1, 1}, {}], t}, 
    t = Sort@Flatten[Tuples /@ Subsets[pp, {3}], 1];
    If[Length@Last@pp == 2, 
     Sort@Join[t, Tuples[{Flatten[Most@pp], Sequence @@ Transpose[{Last@pp}]}]], 
     t]] &;

fn is completely generalized, that is, given some list of elements and a list of existing sets, it generates the 3-tuples of the elements that share at most one element with any of the existing sets. It handles existing sets of arbitrary size members, and if other than 3-tuple results are desired, easily adapted.

gen generates the example results (3-tuples from a list of elements where existing sets are defined as the 3-partitions of the list as in your example) from a target list. Again, pretty easily adapted to other output needs.

A brief performance comparison using OP example output against lists 10-80 in length (on loungebook, so 10+X faster on workstation):

enter image description here

We can see fn is better than an order of magnitude faster than using the Table/Intersection method, and gen is better than an order of magnitude faster yet. The latter also has a superior growth rate (a bit hard to discern on the plot) - roughly linear with result size, while the others are quite a bit worse...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.