Index Combiner Algorithm

Earlier in my work at Mobile Strategy I had a nice algorithmic question which was phrased as follows (I am posting it now as I just had to fix it):

There are N sets of indices (essentially a 2d array) that have to be combined together (in a list of all combinations, order does not matter) in such a way that no combination contains more than one index from one set in N. Our example will look like:

N = [[0], [1], [2,3]]

and our desired output will be:

["0", "0,1", "0,1,2", "0,1,3", "0,2", "0,3", "1", "1,2", "1,3", "2", "3"]

As far as I know the only way of getting this output is recursively (anyone who can find a non-recursive solution, leave a comment – I’m all ears for more efficient solutions), so here is the code I used for this:

ArrayList<String> strings = new ArrayList<String>();
private void recursive(int[][] indices, int array, String currentString) {
      if (array < indices.length) {
            for (int i = 0; i < indices[array].length; i++) {
                  // At this level recurse down for all items in it.
                  String fullString = ((currentString.length() > 0) ? currentString + "," : "") + indices[array][i];
                  strings.add(fullString);
                  recursive(indices, array + 1, fullString);
            }
            recursive(indices, array + 1, currentString);
      }
}

The code in itself is rather simple, the trick is the recursive part, the initial recursing call for our example would be (call 1):

recursive(new int[new int[0], new int[1], new int[2,3]], 0, "")

If we step through the code; the first call of recursive starts the loop placing “0” into strings, then recurses down passing “0” as fullString. The second call of recursive (call 2):

recursive(indices, 1, "0")

would then in the loop put “0,1” into strings and recurse with the following parameters (call 3):

recursive(indices, 2, "0,1")

Again in the loop “0,1,2” would be put into strings and then we would call recurse again (call 4):

recursive(indices, 3, "0,1,2")

As at this point the variable “array” (value 3) is greater than the length of indices – see line 3 of the code, we simply return up again at this point to call 3, continuing with the for loop we insert “0,1,3” into strings and call recurse again (call 5):

recursive(indices, 3, "0,1,3")[/code</span></span>]

This call functions as <span style="color: #ff0000;">call 4</span> did, so I will not recover the ground already covered and return into the evaluation of <span style="color: #00ff00;">call 3</span>. When we return from <span style="color: #ff0000;">call 5</span> the loop in <span style="color: #00ff00;">call 3</span> will finish and we will call recurse as on line 10 (note the use of <span style="text-decoration: underline;">currentString</span> not <span style="text-decoration: underline;">fullString</span> in this case, important in later calls) <span style="color: #ff0000;">(call 6)</span>:

recursive(indices, 3, "0,1")

Again this call functions as call 4 and 5 did so we return, finishing the execution of call 3 returning back to call 2. As this loop only has 1 element in it, the loop finishes and calls recurse on line 10 (call 7):

recursive(indices, 2, "0")

This call adds the strings "0,2" and "0,3" - I won't bother filling in the rest, I think I have shown enough for you all to get the idea of how the execution goes. You can trace out the rest from these examples I hope!

Note on colouration choices: Blue has been used for the second level calls of the function, green for third and red for the fourth level calls - in this case all red calls trigger the 'base case' ending the recursion.

About Simeon Cheeseman

I enjoy a wide variety of computer and board games, have a BSc in Computer Science and have played percussion for 18 years.

Posted on November 4, 2011, in Algorithms. Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: