1
$\begingroup$

I have a list of the following struture:
(my real list also has the same structure, just much longer not just 12)

mylist= {group1, group2, group3, group4, group5, group6, group7, group8, group9, group10, group11, group12}

Each group is also a list which include 4 sublists, let's assume:

group1 = {list1A, list1B, list1C, list1D}
group2 = {list2A, list2B, list2C, list2D}
group3 = {list3A, list3B, list3C, list3D}
...
group11 = {list11A, list11B, list11C, list11D}
group12 = {list12A, list12B, list12C, list12D}

Now I want to form families of 6 lists from 6 groups (out of 12 groups and one list from group) which satisfies the structure in any order:

form = {{x1, x2, x3, x4, x5, x6, x7, x8}, {x3, x2, x1, x6, x5, x4, x8,
    x7}, {x3, x2, -x1 - x3, x6, x5, -x4 - x6, 
   x8, -x7 - x8}, {-x1 - x3, x2, x3, -x4 - x6, x5, x6, -x7 - x8, 
   x8}, {-x1 - x3, x2, x1, -x4 - x6, x5, x4, -x7 - x8, x7}, {x1, 
   x2, -x1 - x3, x4, x5, -x4 - x6, x7, -x7 - x8}}

for example:
families1= {list1A, list3A, list2A, list10A, list12A, list4A}
families2= {list6A, list5A, list8A, list11A, list9A, list7A}
(* all of them happens to be the first list of each group but it's not necessary to be the first list in each group, just any list in a group is okay and lists in families1 and families2 should not intersect*)

so the expectedOut would be: 

expectedOut = {families1, families2}
(*families are not allowed to be interesect*)

This is the result I got by manually do it myself so probably I missed some other possible different combinations of families.
for example: 

expectedOut1 = {families1, families2}
expectedOut2 = {families1, families3}
expectedOut3 = {families5, families7}
or just only one families is found:
expectedOut1 = {families8}

Finally here is my data:
(the expectedOUt) does satisfy the form just not in the given order and the order is not important.)

 mylist = {{{-3, -3, 0, -3, 0, 0, -3, 3}, {-3, 0, 0, -3, -3, 0, -3, 
     3}, {3, 0, 0, 3, 3, 0, -3, 3}, {3, 3, 0, 3, 0, 0, -3, 
     3}}, {{0, -3, -3, 0, 0, -3, 3, -3}, {0, 0, -3, 0, -3, -3, 
     3, -3}, {0, 0, 3, 0, 3, 3, 3, -3}, {0, 3, 3, 0, 0, 3, 
     3, -3}}, {{-3, -3, 3, -3, 0, 3, -3, 0}, {-3, 0, 3, -3, -3, 3, -3,
      0}, {3, 0, -3, 3, 3, -3, -3, 0}, {3, 3, -3, 3, 0, -3, -3, 
     0}}, {{3, -3, 0, 3, 0, 0, 0, 3}, {3, 0, 0, 3, -3, 0, 0, 3}, {-3, 
     0, 0, -3, 3, 0, 0, 3}, {-3, 3, 0, -3, 0, 0, 0, 3}}, {{-3, -3, 
     3, -3, 0, 3, 0, 3}, {-3, 0, 3, -3, -3, 3, 0, 3}, {3, 0, -3, 3, 
     3, -3, 0, 3}, {3, 3, -3, 3, 0, -3, 0, 3}}, {{-3, -3, 0, -3, 0, 0,
      0, -3}, {-3, 0, 0, -3, -3, 0, 0, -3}, {3, 0, 0, 3, 3, 0, 
     0, -3}, {3, 3, 0, 3, 0, 0, 0, -3}}, {{3, -3, 0, 3, 0, 0, 
     3, -3}, {3, 0, 0, 3, -3, 0, 3, -3}, {-3, 0, 0, -3, 3, 0, 
     3, -3}, {-3, 3, 0, -3, 0, 0, 3, -3}}, {{0, -3, -3, 0, 0, -3, -3, 
     0}, {0, 0, -3, 0, -3, -3, -3, 0}, {0, 0, 3, 0, 3, 3, -3, 0}, {0, 
     3, 3, 0, 0, 3, -3, 0}}, {{3, -3, -3, 3, 0, -3, 3, 0}, {3, 0, -3, 
     3, -3, -3, 3, 0}, {-3, 0, 3, -3, 3, 3, 3, 0}, {-3, 3, 3, -3, 0, 
     3, 3, 0}}, {{0, -3, 3, 0, 0, 3, 3, 0}, {0, 0, 3, 0, -3, 3, 3, 
     0}, {0, 0, -3, 0, 3, -3, 3, 0}, {0, 3, -3, 0, 0, -3, 3, 
     0}}, {{0, -3, 3, 0, 0, 3, -3, 3}, {0, 0, 3, 0, -3, 3, -3, 3}, {0,
      0, -3, 0, 3, -3, -3, 3}, {0, 3, -3, 0, 0, -3, -3, 
     3}}, {{3, -3, -3, 3, 0, -3, 0, -3}, {3, 0, -3, 3, -3, -3, 
     0, -3}, {-3, 0, 3, -3, 3, 3, 0, -3}, {-3, 3, 3, -3, 0, 3, 
     0, -3}}};


form = {{x1, x2, x3, x4, x5, x6, x7, x8}, {x3, x2, x1, x6, x5, x4, x8, 
  x7}, {x3, x2, -x1 - x3, x6, x5, -x4 - x6, x8, -x7 - x8}, {-x1 - x3, 
  x2, x3, -x4 - x6, x5, x6, -x7 - x8, x8}, {-x1 - x3, x2, 
  x1, -x4 - x6, x5, x4, -x7 - x8, x7}, {x1, x2, -x1 - x3, x4, 
  x5, -x4 - x6, x7, -x7 - x8}}



expectedOut = {{{-3, -3, 0, -3, 0, 0, -3, 3}, {-3, -3, 3, -3, 0, 
     3, -3, 0}, {0, -3, -3, 0, 0, -3, 3, -3}, {0, -3, 3, 0, 0, 3, 3, 
     0}, {3, -3, -3, 3, 0, -3, 0, -3}, {3, -3, 0, 3, 0, 0, 0, 
     3}}, {{-3, -3, 0, -3, 0, 0, 0, -3}, {-3, -3, 3, -3, 0, 3, 0, 
     3}, {0, -3, -3, 0, 0, -3, -3, 0}, {0, -3, 3, 0, 0, 3, -3, 
     3}, {3, -3, -3, 3, 0, -3, 3, 0}, {3, -3, 0, 3, 0, 0, 3, -3}}};

How can I do that? Note that the expectOut above is just what I got by doing manually myself so it may not include all possible cases.

Edit by lericr attempting to clarify

Given 6 data of the same type (specifically a flat list of 8 numbers), we can check a condition which I'll call isFamily. The isFamily condition is satisfied if some permutation of the 6 data matches the pattern supplied in the original post and labelled form (with the implied replacements of the xN symbols).

A group is a list of 4 data (of the type described above, a length 8 list of numbers). As input, we are given a larger data structure, theData, that consists of 6k groups for some positive integer k.

We want to find families such that each member of the family comes from a different group. Ideally, we'd like to find k disjoint inter-group families. With regard to the disjoint condition, I'm assuming that if the groups are not disjoint then the families need not be disjoint as long as they can be formed without pulling two data from the same group (but it may be the case that theData is constrained so that this cannot occur--maybe the OP can clarify). If the ideal cannot be satisfied, I'm assuming that we want the largest set of inter-group families that we can find.

A solution could provide either one family set (the set that most closely matches the ideal) or all possible family sets.

Improve this question
$\endgroup$
21
  • $\begingroup$ What? mylist has Length 12 (i.e. 12 "groups"). If you pick one item from each "group", shouldn't you end up with a list of Length 12? $\endgroup$
    – lericr
    Commented May 10, 2022 at 22:26
  • $\begingroup$ Is your form a pattern to match against, or is it a target that you're transforming a list to? $\endgroup$
    – lericr
    Commented May 10, 2022 at 22:26
  • $\begingroup$ @lericr 12 is the length of the input list. So it can be divided into two groups of six lists as my expected output. However, the group should be of the given form. Each group in my expected output match the form. I pick one list from each group to form a set of 6 lists which match the form. $\endgroup$
    – hana
    Commented May 10, 2022 at 22:54
  • $\begingroup$ You pick one list from each group... okay, at this point you have 12 lists ... to form a set of 6 lists... how did you get from 12 to 6? $\endgroup$
    – lericr
    Commented May 10, 2022 at 23:25
  • 1
    $\begingroup$ @MichaelE2 I think I understand the objective. I could update the question to make it more clear, and I could update my answer to to better fit the expectations. Unfortunately, I don't have the necessary time at the moment. I'll try to get back to it later. $\endgroup$
    – lericr
    Commented May 11, 2022 at 18:30

2 Answers 2

Reset to default
2
$\begingroup$

Not sure if this kind of answer is appropriate on this forum. There are many assumptions baked in, and it might be hard to modify if those assumptions are wrong. It also seems more complicated that what the OP probably expected (but maybe someone out there has a simpler, more elegant solution). But anyway, here goes...

The strategy will be to take in turn each datum in the input structure, use it to generate a "family" based on a generating function (similar to the OP form), search within the input data for each element of that family, and then process what we find to see if we have any families that satisfy the requirement that each "group", i.e. row, is only represented once. Each family has 6 members (according to the original post, but the implementation allows for other family sizes), and so if the input data is longer that 6 rows, we will need to repeat this process after removing rows that have already been "covered". If we get to the smallest version of the data and do not find satisfactory families, we need to backtrack. If we ever do find families that completely "cover" the rows, then we want to return immediately. If we exhaust all of the possible candidates and don't find any satisfactory families, we'll return an empty set.

Let's start with some helper functions.

(* DataElements assumes that the low level data, the 8-element lists, are at 
the second level down. *)
DataElements[data_]:=Flatten[data,1]

(* FamilyOf generates a candidate family to search for. *)
(* Instead of the form from the original post, I've chosed to use a generatorFn 
to generate a family based on one element. This avoids having to know which 
specific symbols are used in the form, and it just generalizes a bit.
No constraints are applied with regard to size of the element or correctness 
of the generatorFn, and so this could be easily extended to different 
"forms" and different data shapes. *)
FamilyOf[generatorFn_][element_] := generatorFn @@ element

(* FamilyRowSets tells us which rows/groups are covered by the family generated 
by the chosen element. *)
(* data is the input data in which we search for family members. *)
FamilyRowSets[generatorFn_][data_, element_] :=
  With[
    {family = FamilyOf[generatorFn][element]},
    With[
      {coveredRows = 
      Part[Position[data, #, {2}] & /@ family, All, All, 1](* Find the positions of each family member, keeping just the row. *)},
      (* At this point, some family members may not have 
      been found or may have been found multiple times. If a member is found multiple 
      times in the same row, we collapse those to a single row (we don't care about 
      the position within a row, just that a row is covered). From these member-positions, 
      we want to construct all ways to combine them. It's possible that rows can 
      contain multiple family members, and so the same pattern of rows can arise 
      by selecting different members from particular rows. We want to collapse those 
      duplicates to just one set of rows. Finally, we only want row-sets of the correct 
      size (in the original post this was 6) *)   
      Select[
        DeleteDuplicatesBy[Sort][DeleteDuplicates /@ Tuples[coveredRows]],
        Length[family] == Length[#] &]]]

(* We're going to use recursion, basically a depth-first traversal through the search 
space. We will short-circuit the search immediately if we find a solution. A solution 
exhausts all rows, so if we ever reach a point where no rows remain, we know we're 
done. The solution will be the set of families discovered, which we don't have to 
remember along the way, because our generatorFn can recover them. *)
FindCoveringFamiliesStep[generatorFn_][prevGens_, {}] := Throw[generatorFn @@@ prevGens]

(* This is the basic step. As input, we have family-generating-elements that we've 
already found and used to reduce the data, and we have the data that we now wish to 
explore. *)
FindCoveringFamiliesStep[generatorFn_][prevGens_, data_] :=
  With[
    {genElems = DataElements@data},
    FindCoveringFamiliesStep[generatorFn][prevGens, data, #] & /@ genElems]

(* We've picked out one new element from the new data to generate a family. We'll use it 
to generate the covered rows, and then we'll descend into the reduced data. *)
FindCoveringFamiliesStep[generatorFn_][prevGens_, data_, elem_] :=
  With[
    {rowSets = FamilyRowSets[generatorFn][data, elem]},
    If[{} == rowSets,
      Nothing,
      FindCoveringFamiliesStep[generatorFn][Append[prevGens, elem], Delete[data, List /@ #]] & /@ rowSets]]

(* This is the entry point, the wrapper. It will catch the first solution found. 
Otherwise, all of our map actions will produce empty lists. We'll flatten this down 
to a simple empty list, which is intended to be interpreted as failure to find 
solution. *)
FindCoveringFamilies[generatorFn_][data_] :=
  Catch[Flatten[FindCoveringFamiliesStep[generatorFn][{}, data]]]

We can try this out. We need a generator (basically like the form from the original):

theGenerator=
  {{#1,#2,#3,#4,#5,#6,#7,#8},
   {#3,#2,#1,#6,#5,#4,#8,#7},
   {#3,#2,-#1-#3,#6,#5,-#4-#6,#8,-#7-#8},
   {-#1-#3,#2,#3,-#4-#6,#5,#6,-#7-#8,#8},
   {-#1-#3,#2,#1,-#4-#6,#5,#4,-#7-#8,#7},
   {#1,#2,-#1-#3,#4,#5,-#4-#6,#7,-#7-#8}}&

We'll use the data from the OP, and call it theData:

FindCoveringFamilies[theGenerator][theData]
(* returns
{{{-3,-3,0,-3,0,0,-3,3},{0,-3,-3,0,0,-3,3,-3},{0,-3,3,0,0,3,3,0},
  {3,-3,0,3,0,0,0,3},{3,-3,-3,3,0,-3,0,-3},{-3,-3,3,-3,0,3,-3,0}},
 {{-3,-3,3,-3,0,3,0,3},{3,-3,-3,3,0,-3,3,0},{3,-3,0,3,0,0,3,-3},
  {0,-3,3,0,0,3,-3,3},{0,-3,-3,0,0,-3,-3,0},{-3,-3,0,-3,0,0,0,-3}}} *)
Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, I haven't comprehense all your code but it seems work well in my real data as well. Is the result above is the only case? Last time you said like 48 cases. $\endgroup$
    – hana
    Commented May 14, 2022 at 4:11
  • $\begingroup$ It returns the first successful case. There are many other cases that would work, but the algorithm quits as soon as it finds one $\endgroup$
    – lericr
    Commented May 14, 2022 at 4:49
  • $\begingroup$ Would it be easy to modify some number of cases if needed? $\endgroup$
    – hana
    Commented May 14, 2022 at 4:54
1
$\begingroup$

Okay, this is a bit wonky, and I'm not sure how it would perform in your actual context, but...

Here's a function to generate a search target for a given element (the list at the lowest level in your data (form is as you've defined in your post):

interGroupFamily[item_] := form /. Thread[{x1, x2, x3, x4, x5, x6, x7, x8} -> item]

The strategy will be to take each candidate item and see if its interGroupFamily can be found in the data. This should all be bundled into a function, but I'm laying it out explicitly in steps here. Let's get a list of elements to use as generators:

mylistElements = Flatten[mylist, 1]

Now, I'm going to iterate over all of these "atomic" elements, generate a candidate "family" and then look for it in the data. Whatever I find, I'll do some further processing to make sure it satisfies the criteria.

For[idx=1,idx<=Length@mylistElements,idx++,
  With[
    {searchFamily=interGroupFamily[mylistElements[[idx]]]},
    With[
      {candidateFamily=DeleteDuplicatesBy[DeleteCases[Position[mylist,#]&/@searchFamily,{}],First@*First]},
      If[6<=Length@candidateFamily,Return[Take[candidateFamily,6]],Continue[]]]]]

(* with the provided data, this gives
   Return[{{{1, 1}}, {{2, 1}}, {{10, 1}}, {{4, 1}}, {{12, 1}}, {{3, 1}}}] *)

Now, you might want to use Reap/Sow instead to get a full list of "families". Furthermore, this just gives a successful match for the given criteria of a list of length 6. It's not clear to me whether you want "full exhaustion" of the original 12 lists, so maybe this isn't sufficient. I think you can adapt this to get "full exhaustion".

When I tested this, I found that all 48 "atomic" lists generated "families" that could be found in the data that satisifed the criteria. I don't know how to interpret that, but it seems that your data is already primed with a certain structure related to your form. Maybe that is something you could take advantage of. Or maybe I made a mistake.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I don't get how you got 48 "atomic" lists generated "families" that match the form. I ran it and it only generate one result which you also commented above Return[{{{1, 1}}, {{2, 1}}, {{10, 1}}, {{4, 1}}, {{12, 1}}, {{3, 1}}}]. I don't want to take advantage of the data as it can be changed so that would not work for other cases. $\endgroup$
    – hana
    Commented May 11, 2022 at 7:40
  • $\begingroup$ If there are many results would it be possible to generate all possible combinations for that 12 lists? Something like this case1 = {families1, families2}; case2 = {families1, families3}; case3= {families5, families6}, etc where each families has 6 elements and no interesection between two families in the same case. $\endgroup$
    – hana
    Commented May 11, 2022 at 7:40
  • $\begingroup$ The code I provided only returns the first match. But I modified it for testing purposes, and every single low-level list was able to generate a "family" of at least 6 members. $\endgroup$
    – lericr
    Commented May 11, 2022 at 14:17
  • $\begingroup$ It would definitely be possible to find all pairs of families that exhaust the 12 groups. However, as this is just a toy example, I'm not sure how that helps you with your original problem. For 18 groups, do you still want pairs, or do you want triples to exhaust the groups? And so forth for larger data. And it would help to know more about the characteristics of your actual data. $\endgroup$
    – lericr
    Commented May 11, 2022 at 14:22
  • $\begingroup$ What you could try is to adapt the strategy I showed, but make it recursive. So, once a family is found, the "covered" groups get removed and the algorithm re-run on the smaller group-set. You'd need to backtrack when you run into unsuccessful dead-ends. $\endgroup$
    – lericr
    Commented May 11, 2022 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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