All Possible Combinations

Problem: Make a list of all combinations of k elements chosen from a pool of n values in Google Sheets.

Google Sheets formula “COMBIN(n, k)” returns the number of ways to choose some number of objects from a pool of a given size of objects.

But how do you get a list of all these combinations?

On StackOverflow, Kenji asked if there is a way to find “all possible combinations from a table in Excel/Sheets”.

I have a table of 18 people and 18 different ‘jobs’ to do on trips. I need to find all of the combinations of 4 people who cover most or all of the 18 jobs to select so each group of 4 is as self-sufficient as possible.

The people and their capabilities will change from time to time, so I’m trying to see if I can make a sheets or excel doc to help me automate or narrow down the combination process. Given that there are more than 3060 different combinations of people I could take on the trip, and how it’s kind of hard for my (or most humans) brains to filter out the best combination, I was hoping to use the power of excel/sheets and it’s formulas to make this a lot easier.

Example: 5x5 table instead of 18x18

Desired Answer: What kind of formula (or formulas) could help find all the possible combinations of 4 people with a “1” answer.

The hard part of this problem is to get a list of all possible combinations. Once you have the combinations on the sheet, you can use a combination of match() and index() formulas to score the teams.

See tab “Team scoring 5C4” on this Google Sheet: All Possible Combinations.

Brute force with formulas

The StackOverflow OP tried brute force but found it time-consuming.

I tried to use some formulas to simplify the brute force method. This method takes some of the grunt work out but if you have a pool of 18 candidates, it could still be quite a bit of work and you may need many tabs.

I changed the example to pick 4 team members from a pool of 6. See tab “Combinations 6C4” on this Google Sheet: All Possible Combinations.

1. Make an array of 2-member teams (columns A to F). This is a list of 15 teams. Using flatten(), sort() and filter(), I got all these teams in a single column G.
2. I then added a 3rd member to these 15 teams making sure not to avoid duplication of a member in the team (columns H to M). This array has duplicate teams. Example: “Ashley, Bobby, Carol” and “Bobby, Carol, Ashley”.
3. Like with the 2-member team, I flattened, sorted and filtered this array into a single column N.
4. Then to remove the duplicates I first had to order each team alphabetically. I did that using split() and join(). I had to use transpose() as sort() works on columns of values and not rows. And the unique() to remove duplicates and get to the list of 3-member teams in column P.
5. Rinse and repeat to get 4-member teams in column Y.

Now if you had to do this for a pool of 18 members, you may want to use a separate tab for each step of the process.

This takes some of the grunt work out of the process. But it still is a lot of work.

Easier with Google Apps Script

Google Apps Script can take out all the grunt work.

See tab “Script” on this Google Sheet: All Possible Combinations.

Listing the 3,060 combinations of C(18,4) takes about 225 seconds. I’m sure this can be sped up. But not bad if you want to avoid grunt work.

Take the pool of members from column A starting at row 2:

  var ss = SpreadsheetApp.getActiveSpreadsheet();
  var sss = ss.getSheetByName('Script');
  var start = sss.getRange("A2");
  var end = start.getNextDataCell(SpreadsheetApp.Direction.DOWN).getRow();
  var pool = sss.getRange(2, 1, end - 1, 1).getValues(); // Names of team members

Initialise the team array:

  var teamsArray = [];
  for (var m = 0; m < pool.length; m++) teamsArray.push([pool[m]]);

Iterate to add team members k times (1st team member add when initialising the array. Iterate teamSize-1 times):

  var teamsize = sss.getRange("C2").getValue();
  for (var s = 1; s < teamsize; s++) teamsArray = helper_(pool, teamsArray);

In the helper_() function, create a copy of each team:

    var newTeam = teamsArray[n].slice(); // create new array of team to add member to

Loop through the pool and see if the pool member is a team member. If not, add the member to the team and sort the team alphabetically:

if (newTeam.indexOf(pool[m]) == -1) {
        newTeam.push(pool[m]);
        newTeam = newTeam.sort();

If the new team is not in the team's array, add the new team:

if (JSON.stringify(newTeamsArray).indexOf(JSON.stringify(newTeam)) == -1) newTeamsArray.push(newTeam);

That’s all folks!

Ping me if you have an interesting problem that needs to be solved.