How do I find every combination of n 5-length arrays without repeating row or column

Question

My goal is to pass in, for example, 5 arrays of length 5, and receive every combination possible, without repeating any previously used column or row.

Example input:

let m1 = [84, 69, 78, 81, 82];
let m2 = [73, 74, 80, 75, 65];
let m3 = [62, 85, 81, 65, 57];
let m4 = [61, 84, 85, 60, 71];
let m5 = [67, 80, 68, 70, 12];

And I would expect the output to be an array of arrays, looking something like:

[
 [ 84, 74, 81, 60, 12],
 [ 84, 74, 81, 70, 71],
 [ 84, 74, 85, 65, 12],
 [ 84, 74, 85, 70, 57],
 ...
 [ 67, 84, 81, 51, 82]
]

The each input array is a person's score for 5 particular "skills" (The input is very strict, the arrays will always be of length 5). There can be any number of people (minimum is 1, max is around 10, but that is lenient depending on the exponential workload of adding more comparisons/the difficulty of making the number of arrays dynamic).

The end goal of this function is to find the combination of unique "skill scores" with the highest sum, and possibly even which person each score corresponds to (although this is something I can probably figure out by myself, once that first bit is sorted out).

This is different to finding the highest score in each skill. For example, given the inputs above, if the highest scores in each column were taken from left to right, as if in a simple for loop, and the corresponding row and column were taken out of the search for each subsequent score, the resulting array would be:

[ 84, 85, 85, 75, 12 ]

This array has a sum of 341, whereas the following result is not necessarily the "max" of each column, but fits the criteria and has a higher total sum, which is the desired result:

[84, 85, 80, 70, 71 ]

With a sum of 390.

I suspect the solution has something to do with a branching tree, or recursion, and I have found a very elegant almost-solution here: https://stackoverflow.com/a/15310051/10538353 by Bergi, however it is missing the row/column duplication restriction I am looking for.

The following is a static implementation of the algorithm I'm thinking about:

let m1 = [00, 10, 20, 30, 40];
let m2 = [01, 11, 21, 31, 41];
let m3 = [02, 12, 22, 32, 42];
let m4 = [03, 13, 23, 33, 43];
let m5 = [04, 14, 24, 34, 44];

function testFunc(m1, m2, m3, m4, m5) {
    let result = [];
    m1.forEach((m1Element, m1Index, m1Object) => {
        var m1Temp = [];
        m1Temp.push(m1Element);

        m2.forEach((m2Element, m2Index, m2Object) => {
            var m2Temp = m1Temp.slice(0);
            if (m2Index != m1Index) {
                m2Temp.push(m2Element);

                m3.forEach((m3Element, m3Index, m3Object) => {
                    var m3Temp = m2Temp.slice(0);
                    if (m3Index != m1Index && m3Index != m2Index) {
                        m3Temp.push(m3Element);  
               
                        m4.forEach((m4Element, m4Index, m4Object) => {
                            var m4Temp = m3Temp.slice(0);
                            if (m4Index != m1Index && m4Index != m2Index && m4Index != m3Index) {
                                m4Temp.push(m4Element); 
                        
                                m5.forEach((m5Element, m5Index, m5Object) => {
                                    var m5Temp = m4Temp.slice(0);
                                    if (m5Index != m1Index && m5Index != m2Index && m5Index != m3Index && m5Index != m4Index) {
                                        m5Temp.push(m5Element);
                                        result.push(m5Temp);
                                        return;
                                    }
                                })
                            }
                        })
                    }
                })
            }
        })
    })
    return result;
}
console.log(testFunc(m1, m2, m3, m4, m5));

Which prints out:

[
  [ 0, 11, 22, 33, 44 ], [ 0, 11, 22, 43, 34 ], [ 0, 11, 32, 23, 44 ],
  [ 0, 11, 32, 43, 24 ], [ 0, 11, 42, 23, 34 ], [ 0, 11, 42, 33, 24 ],
  [ 0, 21, 12, 33, 44 ], [ 0, 21, 12, 43, 34 ], [ 0, 21, 32, 13, 44 ],
  [ 0, 21, 32, 43, 14 ], [ 0, 21, 42, 13, 34 ], [ 0, 21, 42, 33, 14 ],
  [ 0, 31, 12, 23, 44 ], [ 0, 31, 12, 43, 24 ], [ 0, 31, 22, 13, 44 ],
...
]

This is exactly what I'm looking for, except as you might expect, the algorithm falls down (just a little bit) when a different number of arrays is passed to the function. I am no great shakes with Javascript, but to me it seems like there would be some kind of map/reduce functionality that would allow me to iterate down the layers, while also retaining both the current "draft" array and the indexes that I have previously used up (see the enourmous "if (index5 != index4 ...)" sections for how I am currently achieving this).

Can anyone anyone recommend how I might proceed with converting this to a more dynamic implementation?

Answer 1

One way to solve this is to use a combination generator combined with a permutation generator.

Suppose there are num_people people and num_skills skills. The outer loop would consider all combinations of num_skills people. The inner loop would consider the possible pairings of skills to the different people.

The example below is in Python, chosen particularly because its standard library has functionality for iterating over combinations and permutations. The general idea could be ported to other languages, but may require additional code for iterating over permutations and combinations.

from itertools import combinations, permutations

def generate(num_people, num_skills):
    assert num_people >= num_skills
    # Loop over the combinations of people
    for combo in combinations(range(num_people), num_skills):
        # Loop over the pairings of skills to the different people
        for skills in permutations(range(num_skills)):
            yield tuple(zip(combo, skills))

scores = [
    [84, 69, 78, 81, 82],
    [73, 74, 80, 75, 65],
    [62, 85, 81, 65, 57],
    [61, 84, 85, 60, 71],
    [67, 80, 68, 70, 12],
]

best_total = 0
best_assignment = None

num_people = len(scores)
num_skills = len(scores[0])
for assignment in generate(num_people, num_skills):
    total = sum(scores[person][skill] for person, skill in assignment)
    if total >= best_total:
        best_total = total
        best_assignment = assignment

print(best_assignment)
print(best_total)

Output:

((0, 4), (1, 0), (2, 1), (3, 2), (4, 3))
395

The output indicates that the best score is by pairing skill 4 to person 0, skill 0 to person 1, skill 1 to person 2, skill 2 to person 3, and skill 3 to person 4. This results in a score of 395, which is equal to 82 + 73 + 85 + 85 + 70.

The generate function is a generator that returns pairings of people and skills. For example, suppose there are three people and two skills. In that case, the following elements would be generated by generate, which represents all pairings of the two skills to the three people.

((0, 0), (1, 1))  # person 0 / skill 0, person 1 / skill 1
((0, 1), (1, 0))  # person 0 / skill 1, person 1 / skill 0
((0, 0), (2, 1))  # ...
((0, 1), (2, 0))
((1, 0), (2, 1))
((1, 1), (2, 0))  # person 1 / skill 1, person 2 / skill 0

The implementation requires more code in Javascript, since the standard library does not include combination/permutation generators.

Python's documentation includes a description of algorithms for generating combinations and permutations. With this description, the approach above can be ported to Javascript, with an example implementation included below.

const combinations = function*(n, r) {
    if (r > n)
        return;
    const indices = Array.from(Array(r).keys());
    yield [...indices];
    while (true) {
        let done = true;
        let i;
        for (i = r - 1; i >= 0; --i) {
            if (indices[i] !== i + n - r) {
                done = false;
                break;
            }
        }
        if (done)
            return;
        indices[i] += 1;
        for (let j = i + 1; j < r; ++j) {
            indices[j] = indices[j - 1] + 1;
        }
        yield [...indices];
    }
};

const permutations = function*(n) {
    const indices = Array.from(Array(n).keys());
    yield [...indices];
    const cycles = Array.from({length: n}, (_, i) => i + 1);
    cycles.reverse();
    while (n) {
        let done = true;
        for (let i = n - 1; i >= 0; --i) {
            cycles[i] -= 1;
            if (cycles[i] === 0) {
                let source = indices.slice(i + 1).concat(
                    indices.slice(i, i + 1));
                for (let j = 0; j < source.length; ++j) {
                    indices[i + j] = source[j];
                }
                cycles[i] = n - i;
            } else {
                let j = cycles[i];
                let tmp = indices[i];
                indices[i] = indices[n - j];
                indices[n - j] = tmp;
                yield [...indices];
                done = false;
                break;
            }
        }
        if (done)
            return;
    }
};

const generate = function*(num_people, num_skills) {
    if (num_skills > num_people)
        throw new Error('More skills than people');
    // Loop over the combinations of people
    for (const combo of combinations(num_people, num_skills)) {
        // Loop over the pairings of skills to the different people
        for (const skill of permutations(num_skills)) {
            const assignment = [];
            for (let i = 0; i < combo.length; ++i) {
                assignment.push([combo[i], skill[i]]);
            }
            yield assignment;
        }
    }
};

const scores = [
    [84, 69, 78, 81, 82],
    [73, 74, 80, 75, 65],
    [62, 85, 81, 65, 57],
    [61, 84, 85, 60, 71],
    [67, 80, 68, 70, 12]
];

let best_total = 0
let best_assignment = null;

const num_people = scores.length;
const num_skills = scores[0].length;
for (const assignment of generate(num_people, num_skills)) {
    let total = 0;
    for (let i = 0; i < assignment.length; ++i) {
        const [person, skill] = assignment[i];
        total += scores[person][skill];
    }
    if (total >= best_total) {
        best_total = total;
        best_assignment = assignment;
    }
}

console.log(best_assignment);  // [[0, 4], [1, 0], [2, 1], [3, 2], [4, 3]]
console.log(best_total);  // 395