I solved the problem externally.
Get all combinations of a list of lists of arrays...
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.
add more examples for
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)
Can't quite see what you want to do, need more examples
$$anonymous$$aybe this example will make it slightly clearer?:
Object 1:
Solution 1: Object 1, Object 2
Solution 2: Object 2, Object 3
Object 2:
Solution 1: Object 2, Object 3
Solution 2: Object 3, Object 4
Object 3:
Solution 1: Object 5, Object 6
The final List of Lists should look like so:
List 1: (Object 1, Object 2), (Object 2, Object 3), (Object 5, Object 6)
List 2: (Object 1, Object 2), (Object 3, Object 4), (Object 5, Object 6)
List 3: (Object 2, Object 3), (Object 2, Object 3), (Object 5, Object 6)
List 4: (Object 2, Object 3), (Object 3, Object 4), (Object 5, Object 6)
This is a simplified version of the actual in-game setting, but the point about iteration and all of the structure is the same.
Answer by IgorAherne · Feb 24, 2017 at 03:16 PM
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>
Hey, thx for reply, sry for being late.
I tinkered a bit with ur suggestion but it was not getting me what I want and I wasn't sure exactly how to implement it in my case. I'll try to be a bit more clear:
It's a 2D tile-based game. Every tile can be on or off. The player toggles them by walking on them. Some tiles have symbols, which I'll call "shape symbols". (If you've played The Witness, they look like the tetro$$anonymous$$o symbols.) These say that tiles must be OFF that make up the shape displayed by the symbol (the tile with the symbol must be a part of the shape). e.g.: https://tinyurl.com/zp6ywkh - here, the centre tile has a shape symbol in an L-shape. This has 3 solutions, shown by the tiles marked 1, 2, or 3. Only one solution can be used at a time. So if solution 1 is used, then ALL tiles must be ON, EXCEPT FOR all the tiles marked 1, and so on for solutions 2 and 3.
However, shape symbols can 'overlap'. I.e., when there are multiple tiles with shape symbols on them, the off tiles used for each can overlap. e.g.: http://tinyurl.com/hvnycy2 - here, the middle row of tiles can all be OFF (with the rest ON), and both these tiles will be 'solved'; i.e., the centre tile is used for BOTH shape symbols' solutions.
Each tile has a script (scr_tile) which contains an array of all possible combinations of tiles that could be used as solutions for that tile's shapes symbol (if it has one). Each of these 'combinations' is an array of the position of each tile. I need to find every single possible permutation of all solutions for all tiles with shapes symbols, so that I can iterate through each one and check which one/s are solved.
So, to summarise: I have a bunch of "scr_tile"s. Some of them have shapes symbols on them. Each of these has an array of "potential combinations", where each "potential combinations" is an array of positions that make up the shape shown on the symbol. I need to be able to iterate through every single permutation of every "potential combination" of all tiles with shapes symbols on them.
Here is a specific example: https://gyazo.com/2af8a7d3aa4418e1975ce44f00d48db1 -- In this case, Tile(B,1) has the following TWO solutions: Solution i) Tiles: (A1, B1, B2) Solution ii) Tiles: (B1, C1, C2) And Tile(C,4) has the following TWO solutions: Solution i) Tiles: (C4, D4) Solution ii) Tiles: (B4, C4) As such, the final list of lists should look like so: 1st list: all tiles from (B,1) Solution i) + all tiles from Tile(C,4) Solution i) i.e.: A1, B1, B2, C4, D4 2nd list: all tiles from Tile(B,1) Solution i) + all tiles from Tile(C,4) Solution ii) i.e.: A1, B1, B2, B4, C4 3rd list: all tiles from Tile(B,1) Solution ii) + all tiles from Tile(C,4) Solution i) i.e.: B1, C1, C2, C4, D4 4th list: all tiles from Tile(B,1) Solution ii) + all tiles from Tile(C,4) Solution ii) i.e.: B1, C1, C2, B4, C4
I hope this makes sense... may be best to email me at afender7[at]yahoo.co.uk if not. The formatting & character limit here are a bit tricky!
Answer by afender7 · Feb 27, 2017 at 01:00 AM
Replied to your suggestion, but it is not showing up on my screen. Let me know if you can see it!
Thanks!
Follow this Question
Related Questions
Recursive reference within a list 2 Answers
Threading and minimax algo 1 Answer
Mobile Buttons not working? 0 Answers