Get all combinations of a list of lists of arrays...

Question

I have the following structure: a known number of objects, each of which contains an unknown number of arrays (the size and contents of each array is known). Each array is a "solution", where each element is a reference to another object.

How would I go about filling a list of lists, where each list contains every object reference contained in a single permutation of the above structure? For example, say I have 2 objects, like so:

Object 1:

Solution 1: Object 1, Object 2

Solution 2: Object 2, Object 3

Object 2:

Solution 1: Object 3, Object 4

I would want to end up with the following list of lists: (brackets for clarification only -- each bracketed set is a single object's "solution", as shown above)

List 1: (Object 1, Object 2), (Object 3, Object 4)

List 2: (Object 2, Object 3), (Object 3, Object 4)

I know that I need some kind of recursive function; I have tried implementing a version of the function described here - http://stackoverflow.com/a/17193002 - but what ends up happening is that each list contains every object reference in all permutations. This is the function I wrote (scr_tile is the name of the object I am talking about):

 void GeneratePermutations(List<List<scr_tile[]>> Lists, List<List<scr_tile>> result, int depth, List<scr_tile> current) {
     if (depth == Lists.Count) {
         result.Add(current);
         return;
     }
     for (int i = 0; i < Lists[depth].Count; ++i) {
         List<scr_tile> new_current = current;
         new_current.AddRange(Lists[depth][i]);
         GeneratePermutations(Lists, result, depth + 1, new_current);
     }
 }

And I call it using the following (also including the code used to populate Lists -- shape_solutions is simply the list for each scr_tile, which contains arrays, where each array represents a single "solution"):

 List<List<scr_tile[]>> Lists = new List<List<scr_tile[]>>();
 foreach (scr_tile tile in (scr_tile[])Object.FindObjectsOfType(typeof(scr_tile))) {
     tile.GetShapeSolutions();
     if (tile.shape_solutions.Count > 0 && !Lists.Contains(tile.shape_solutions)) Lists.Add(tile.shape_solutions);
 }
 List<List<scr_tile>> Result = new List<List<scr_tile>>();
 GeneratePermutations(Lists, Result, 0, new List<scr_tile>());

So I feel like the above function could be modified in some relatively simple way to store these permutations properly -- but I am beating my head against a wall at the moment. I have tried tinkering with it in a few ways. I know basically nothing about recursive functions so they are not very intuitive to me, so assume zero knowledge of the subject matter.

I hope that all made sense. It is 3am, so...

Any help would be massively appreciated.

Answer 1

I understood it in the following way:

Solution is a list of SolutionObject

1) You have a collection of SolutionObjects, and you want to select i'th solutions-list from each one and add them into one large list of list of list<SolutionObject>, in other words, into a list of lists of solutions

2) Increment`i` by one. If it reaches the maximum number of solutions ever encountered in any SolutionObject, then stop the algorithm

3) go to step 1

Here is how you do it (no recursion needed)

 using System.Linq;
  
    //here is a collection of solution objects to be looked at:
 List<SolutionObject> toInspect = new List<SoutionObject>() {... .... ... .. ... . .};

 List<List<SolutionObject>> grabThemSolutionObjects(List<SolutionObject> TO_INSPECT) {

     //result will be stored here (list of lists of solutions):
     List<List<List<SolutionObject>>> result = new List<List<List<SolutionObject>>>();

     //first of all, find the maximum number of solutions that's ever contained in any of
     //provided SolutionObjects:
     // getSolutions() should provide a LIST of solutions for each object.
     int maxNumSolutions = TO_INSPECT.Select(sobj => sobj.getSolutions().Count)
                                     .Max();

     for(int i =0; i< maxNumSolutions; ++i) {
         Get_ith_solutionFromEach_s_obj(TO_INSPECT, i);
     }//end for maxNumSolutions



     //use result as needed or return it

     //return list of solutions (a list of list of SolutionObjects)
     return result;
 }

 //returns i'th solution from all the objects, as a list.
 List<List<SolutionObject>> Get_i_solutionFromEach_s_obj(List<SolutionObject> TO_INSPECT, int i) {

     List<List<SolutionObject>> ith_solutions = new List<List<SolutionObject>>();

     //inspect a provided collection of SolutionObjects
     foreach (SolutionObject s_obj in TO_INSPECT) {
         //here is a list of ALL solutions of "s_obj" from "TO_INSPECT":
         List<List<SolutionObject>> solutions_of_s_obj = s_obj.getSolutions();

         //we want to get the i'th solution from this s_obj, but if there are
         //not enough of solutions, we will sample the last solution.
         int clamped_ix = Mathf.Min(i, solutions_of_s_obj.Count - 1);

         ith_solutions.Add(solutions_of_s_obj[clamped_ix]);
     }//end foreach

     return ith_solutions;
 }

For this to work, each SolutionObject must have a public function getSolutions(), which returns a List<List<SolutionObjects>>, which represents a list of solutions.

If all is good, you will have the following thing:

 <list>
      <list of first solutions from all supplied objects>
       <list of second solutions from all supplied objects>
       <list of third solutions from all supplied objects>
       <etc...>
 </list>

Answer 2

Answer by afender7 · Feb 27, 2017 at 01:00 AM

@IgorAherne

Replied to your suggestion, but it is not showing up on my screen. Let me know if you can see it!

Thanks!

Add comment · Share

Get all combinations of a list of lists of arrays...

2 Replies

Follow this Question

Related Questions