Algorithm to return all possible pairings of matches

Question

I have an Array of PlayerIDs

Players = [ 1, 2, 4, 12, 14, 16 ]

I now need an algorithm that returns all possible combinations, like

 [1,2], [4,12], [14,16] 
 [1,4], [2,12], [14,16] 
 [1,12], [2,4], [14,16]
 [1,14], [2,4], [12,16]
...and so on, till all combinations have been listed

There is no difference between [1,2] or [2,1]. I would stay that X<Y at [X,Y]

I found the following approach [https://stackoverflow.com/a/16256122][1] which is really near to what I look for, but this algorithm doesn't group the pairings (Array of 6 Players = Group of 3 possible pairings).

Can somebody refine this algorithm that fits my needs?

Examples in Java, C++, C# or PHP are fine.

Thank you in advance!

Answer 1

eager evaluation

We can write choosek(t, k) to find all fixed-length combinations of size k from an array or list, t. We can approach the problem using inductive reasoning -

1. if k is zero or negative, there are no more choices to make, return a singleton list of the empty choice
2. (inductive) k is positive so there is at least one thing to choose. If t is empty, there is nothing to choose from, return the empty list of choices.
3. (inductive) k is positive and t has at least one choice to make. For each comb of the sub-problem choosek(t.slice(1), k - 1), prepend the first element of t to the resulting comb. Concatenate this result to the result of the second sub-problem, choosek(t.slice(1), k).

Below I chose JavaScript because I can embed a functioning demo right here in the answer. Run the program below to see demoes of k = 2 and k = 3

function choosek(t, k) {
  if (k <= 0)
    return [[]]                            // 1
  else if (t.length == 0)
    return []                              // 2
  else
    return choosek(t.slice(1), k - 1)      // 3
      .map(comb => [t[0]].concat(comb))
      .concat(choosek(t.slice(1), k))
}

console.log(
  choosek(["","","",""], 2).map(comb => comb.join("")).join(", ")
)

console.log(
  choosek(["","","",""], 3).map(comb => comb.join("")).join(", ")
)

// choose 2
, , , , , 

// choose 3
, , , 

All of the functions used here .map, .concat, and .slice have straightforward counterparts in PHP, Java, Python, and C#.

Notice that choosek returns an array of combinations where each combination is itself an array. This allows the caller to do whatever she/he pleases with each combination. For example, you may wish to convert each to a string for logging in the console or perhaps you will leave them as arrays to build a tournament bracket.

generators

PHP, Python, and C# all support generators, though I'm unsure of Java. Using JavaScript we can demonstrate choosek using generators. The advantage of this approach are numerous -

1. Generators are lazy, meaning we can pause/resume them. The caller can collect as many combinations as needed, discard the rest, or exhaust the entire generator.

2. If the input is significantly large, the solution space may be gigantic. Forcing all of the combinations into an array before returning the result could cost a lot of memory. Generators allow you to process the result as each one is being generated.

3. A generator's results can easily be collected into an array using Array.from or equivalent, if desired, though this is not required. This choice is left for the caller to decide. As a result, the generator implementation reduces one level of nesting arrays, making it easier to read/write the program.

4. The exact same inductive reasoning approach can be applied to solve the problem

function* choosek(t, k) {
  if (k <= 0)
    return yield []
  else if (t.length == 0)
    return
  else {
    for (const comb of choosek(t.slice(1), k - 1))
      yield [t[0]].concat(comb)
    yield *choosek(t.slice(1), k)
  }
}

for (const comb of choosek(["","","",""], 2))
  console.log(comb.join(""))

To compute permutations, see this related Q&A.