{"id":343,"date":"2014-08-04T07:00:00","date_gmt":"2014-08-04T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2014\/08\/04\/enumerating-the-ways-of-choosing-teams-in-a-group-of-players\/"},"modified":"2014-08-04T07:00:00","modified_gmt":"2014-08-04T07:00:00","slug":"enumerating-the-ways-of-choosing-teams-in-a-group-of-players","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20140804-00\/?p=343","title":{"rendered":"Enumerating the ways of choosing teams in a group of players"},"content":{"rendered":"

\nSuppose you have a bunch of people,\nand you want to break them up into m<\/var> teams of size n<\/var>.\n(Therefore you have a total of nm<\/var> people.)\nToday’s Little Program will enumerate the ways this can be done.\n<\/p>\n

\nFormally, let’s say that you have a collection of size nm<\/var>,\nand you want to enumerate the ways of partitioning the collection\ninto m<\/var> subsets, each subset of size n<\/var>.\nThe order of elements within each subset does not matter,\nand the order of the subsets doesn’t matter.\nThat’s saying that\na team of Alice and Bob is the same as a team of Bob and Alice,\nand Alice-Bob versus Charlie-David is the same as\nCharlie-David versus Alice-Bob.\n<\/p>\n

\nThe number of ways of doing this is\n(nm<\/var>)!\/n<\/var>!m<\/var><\/sup>m<\/var>!.\nYou can see this by first taking all permutations of the players,\nthen dividing out by the things that cause us to overcount:\nThe number of ways of ordering players within each team is n<\/var>!,\nand there are m<\/var> teams, and there are m<\/var>! ways of\nordering the teams themselves.\n(Note that this is a cute way of expressing the result,\nbut\n\nyou shouldn’t use it for computation<\/a>.\nA slightly better way for computation would be\n(Π<\/var>1 ≤ k<\/var> ≤ n<\/var><\/sub>C<\/var>(mk<\/var>, m<\/var>))\/m<\/var>!.\n<\/p>\n

\nOkay, but how do you generate the teams themeselves?\n<\/p>\n

\nLet’s first see how to generate the first team.\nWell, that’s easy.\nYou just select n<\/var> players and call them Team 1<\/i>.\n<\/p>\n

\nThis leaves you n<\/var>(m<\/var> − 1) players with\nwhich to form m<\/var> − 1 teams,\nwhich you can do recursively.\n<\/p>\n

\nfunction Teams(n, m, f) {\n var a = [];\n for (var i = 1; i <= n * m; i++) {\n  a.push(i);\n }\n if (m == 1) { f([a]); return; }\n Subsets<\/a>(n * m, n, function(s) {\n  var rest = a.filter(function(i) { return s.indexOf(i) < 0; });\n  Teams(n, m - 1, function(t) {\n    f([s].concat(t.map(function(team) {\n        return team.map(function(i) { return rest[i-1]; });\n       })));\n  });\n });\n}\nTeams(2, 3, logToConsole);\n<\/pre>\n
\nThe first part of this function builds an array of the form\n[1, 2, 3, ..., n * m]<\/code>.\nIf we are asking for only one team, then everybody is on the\nsame team.\nOtherwise, for all possible choices of n<\/code>-member teams,\nfirst see which people haven’t yet been picked for a team.\nThen generate all remaining possible team arrangements for\nthose leftovers,\nand combine them to form the final team rosters.\n<\/p>\n
\nThe combination step is tricky because the recursive call\ngenerates subsets in the range [1, 2, 3, ..., n * (m-1)]<\/code>,\nand we need to convert those values into indices into the\narray of people waiting to be picked.\n<\/p>\n
\nNote that this algorithm over-counts the possibilities since\nit generates both\n[[1,2],[3,4]]<\/code> and\n[[3,4],[1,2]]<\/code>.\nIn other words, it assumes that team order is important\n(say, because the first team will wear red jerseys and the second\nteam will wear blue jerseys).\nIn the original problem statement,\nthe order of the teams is not significant.\n(Maybe we’ll let them pick their own jersey colors.)\n<\/p>\n
\nTo solve that, we impose a way of choosing one such arrangement\nas the one we enumerate, and ignore the rest.\nThe natural way to do this is to select a representative player from each team\nin a predictable manner\n(say, the one whose name comes first alphabetically),\nand then arranging the representatives in a predictable manner\n(say, by sorting them alphabetically).\n<\/p>\n
\nThe revised version of our algorithm goes like this:\n<\/p>\n
\nfunction Teams(n, m, f) {\n var a = [];\n for (var i = 1; i <= n * m; i++) {\n  a.push(i);\n }\n if (m == 1) { f([a]); return; }\n a.shift();\n Subsets(n * m - 1, n - 1, function(s) {\n  var firstTeam = [1].concat(s.map(function(i) { return i+1; }))\n  var rest = a.filter(function(i) { return s.indexOf(i) < 0; });\n  Teams(n, m - 1, function(t) {\n    f([firstTeam].concat(t.map(function(team) {\n      return team.map(function(i) { return rest[i-1]; });\n     })));\n  });\n });\n}\nTeams(2, 3, logToConsole);\n<\/pre>\n
\nThe first part of the function is the same as before,\nbut the recursive step changes.\n<\/p>\n
\nWe remove the first element from the array.\nThat guy needs to belong to some<\/i> team,\nand since he’s the smallest-numbered guy,\nhe will be nominated as the team representative\nof whatever team he ends up with,\nand since he’s the smallest-numbered guy of all,\nhe will also be the first team representative when they\nare placed in sorted order.\nSo we pick him right up front.\n<\/p>\n
\nWe then ask for his n - 1<\/code> teammates,\nand together they make up the first team.\nThe combination is a little tricky because\nthe Subsets<\/code> function assumes that the\nunderlying set is [1, 2, ..., n-1]<\/code> but we\nactually want the subset to be of the form\n[2, 3, ..., n]<\/code>;\nwe fix that by adding 1 to each element of the subset.\n<\/p>\n
\nWe then find all the people who have yet to be assigned to a team\nand recursively ask for m - 1<\/code> more teams to be generated\nfrom them.\nWe then combine the first team with the recursively-generated teams.\nAgain, since the recursively-generated teams are numbered\nstarting from 1, we need to convert the returned subsets into\nthe original values we saved away in the rest<\/code> variable.\n<\/p>\n
\nRenumbering elements is turning into a bit of a bother,\nso let’s tweak our original\nSubsets<\/code> function.\nFor example, we would prefer to pass the set explicitly\nrather than letting Subsets<\/code> assume that the set is\n[1, 2, 3, ..., n]<\/code>,\nforcing us to convert the indices back to the original set members.\nIt’s also convenient if the callback also included the elements that\nare not in the subset.\n<\/p>\n
\nfunction NamedSubsets(a, k, f) {\n if (k == 0) { f([], a); return; }\n if (a.length == 0) { return; }\n var n = a[a.length - 1];\n var rest = a.slice(0, -1);\n NamedSubsets(rest, k, function(chosen, rejected) {\n  f(chosen, rejected.concat(n));\n });\n NamedSubsets(rest, k-1, function(chosen, rejected) {\n  f(chosen.concat(n), rejected);\n });\n}\nfunction takeAndLeave(chosen,rejected) {\n console.log(\"take \" + chosen + \", leave \" + rejected);\n}\nNamedSubsets([\"alice\", \"bob\", \"charlie\"], 2, takeAndLeave);\n<\/pre>\n
\nThe Named­Subsets<\/code> function\ntakes the last element from the source set\nand either rejects it (adds it to the “rejected” parameter)\nor accepts it (adds it to the “chosen” parameter).\n<\/p>\n
\nWith the Named­Subsets<\/code> variant,\nwe can write the Teams<\/code> function\nmuch more easily.\n<\/p>\n
\nfunction Teams(a, m, f) {\n var n = a.length \/ m;\n if (m == 1) { f([a]); return; }\n var p = a[0];\n NamedSubsets(a.slice(1), n - 1, function(teammates, rest) {\n  var team = [p].concat(teammates);\n  Teams(rest, m - 1, function(teams) {\n    f([team].concat(teams));\n  });\n });\n}\nTeams([1,2,3,4,5,6], 3, logToConsole);\n<\/pre>\n
\nAssuming we’re not in one of the base cases,\nwe grab the first person p<\/code>\nso he can be captain of the first team.\nWe then ask Named­Subsets<\/code> to generate his teammates\nand add them to p<\/code>‘s team.\nWe then recursively generate all the other teams\nfrom the people who haven’t yet been picked,\nand our result is our first team plus the recursively-generated teams.\n<\/p>\n
\nThere is a lot of potential for\n\nstyle points<\/a> with the\nNamed­Subsets<\/code> function.\nFor example, we can avoid generating temporary copies of the\na<\/code> array just to remove an element\nby instead passing slices\n(an array and indices marking the start and end of the elements\nwe care about).\n<\/p>\n
\nfunction NamedSubsetsSlice(a, begin, end, k, f) {\n if (k == 0) { f([], a.slice(begin, end)); return; }\n if (begin == end) { return; }\n var n = a[end - 1];\n NamedSubsetsSlice(a, begin, end - 1, k, function(chosen, rejected) {\n  f(chosen, rejected.concat(n));\n });\n NamedSubsetsSlice(a, begin, end - 1, k-1, function(chosen, rejected) {\n  f(chosen.concat(n), rejected);\n });\n}\nfunction NamedSubsets(a, k, f) {\n NamedSubsetsSlice(a, 0, a.length, k, f);\n}\n<\/pre>\n
\nWe could use an accumulator to avoid having to generate closures.\n<\/p>\n
\nfunction AccumulateNamedSubsets(a, begin, end, k, f, chosen, rejected) {\n if (k == 0) { f(chosen, rejected.concat(a.slice(begin, end))); return; }\n if (begin == end) { return; }\n var n = a[begin];\n AccumulateNamedSubsets(a, begin + 1, end, k-1, f, chosen.concat(n), rejected);\n AccumulateNamedSubsets(a, begin + 1, end, k, f, chosen, rejected.concat(n));\n}\nfunction NamedSubsetsSlice(a, begin, end, k, f) {\n AccumulateNamedSubsets(a, begin, end, k, f, [], []);\n}\nfunction NamedSubsets(a, k, f) {\n NamedSubsetsSlice(a, 0, a.length, k, f);\n}\n<\/pre>\n
\nFor bonus style points, I recurse on the start of the range rather\nthan the beginning so that\nthe results are in a prettier order.\n<\/p>\n
\nWe can also get rid of the temporary accumulator objects by manipulating the\naccumulators destructively.\n<\/p>\n
\nfunction AccumulateNamedSubsets(a, begin, end, k, f, chosen, rejected) {\n if (k == 0) { f(chosen, rejected.concat(a.slice(begin, end))); return; }\n if (begin == end) { return; }\n var n = a[begin];\n chosen.push(n);<\/font>\n AccumulateNamedSubsets(a, begin + 1, end, k-1, f, chosen<\/font>, rejected);\n chosen.pop();\n rejected.push(n);<\/font>\n AccumulateNamedSubsets(a, begin + 1, end, k, f, chosen, rejected<\/font>);\n rejected.pop();<\/font>\n}\n<\/pre>\n
\nAnd then we can take advantage of the accumlator version to\npre-select the first player when building teams.\n<\/p>\n
\nfunction Teams(a, m, f) {\n var n = a.length \/ m;\n if (m == 1) { f([a]); return; }\n AccumulateNamedSubsetsSlice(a, 1, a.length, n - 1, function(team, rest) {\n  Teams(rest, m - 1, function(teams) {\n    f([team].concat(teams));\n  });\n }, [a[0]], []);\n}\n<\/pre>\n
\nThere is still a lot of potential for improvement here.\nFor example, you can switch to the iterative version of\nSubsets<\/code> to avoid the recursion on subset generation.\nYou can use an accumulator in Teams<\/code> to avoid\ngenerating closures.\nAnd\nif you are really clever, you can eliminate many more temporary arrays\nby reusing the elements in the various\nrecursively-generated arrays by shuffling them around.\nBut I’ve sort of lost interest in the puzzle by now, so I won’t bother.<\/p>\n","protected":false},"excerpt":{"rendered":"
Suppose you have a bunch of people, and you want to break them up into m teams of size n. (Therefore you have a total of nm people.) Today’s Little Program will enumerate the ways this can be done. Formally, let’s say that you have a collection of size nm, and you want to enumerate […]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-343","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Suppose you have a bunch of people, and you want to break them up into m teams of size n. (Therefore you have a total of nm people.) Today’s Little Program will enumerate the ways this can be done. Formally, let’s say that you have a collection of size nm, and you want to enumerate […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/343","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=343"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/343\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=343"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=343"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=343"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}