Enumerate permutation

Question

A lot of combinatorial problems have the form of n!/(m!*p!*q!...) for the number of distinct permutations. Is there any efficient algorithm to enumerate all distinct permutations ?

Let’s use an example to clear things up. Let’s say that 10 persons want to play a 5v5 game. In order to help them build a matchup (ie who goes in each team), we would like to enumerate all possible matchups. How many matchups are there ? Overall, there is 10! = 3628800 possible ways of arranging the players. However, swapping players inside team 1 does not change anything (A+B+C+D+E vs F+G+H+I+J is the same as B+A+C+D+E vs F+G+H+I+J), so we must divide this number by 5!. Same for swapping players inside team 2. Swapping team 1 and team 2 results to the same matchup, so we want to divide the final result by 2. In the end, there is 10!/(5!*5!*2!)=126 distinct matchups. Is there any way to find them ?

The naive algorithm would be to enumerate all players permutations, and only return "canonical" representation of a matchup (for example, inside a team players must be ordered in the lexicographical order). That is however awfully inefficient ; for a 8 vs 8 game, we must enumerate and evaluate 16! (more than 20 trillions) permutations in order to enumerate the 6435 distinct matchups. Is there any non-naive alternative ?

As a basis to go on - take the list of players, sorted by whatever rule you want (e.g. lexicographical) that ensures if you skip an element it cannot appear later (e.g. [A, B, C] can be [A], [A, B], [A, B, C], [A, C] or [B, C] but never [A, C, B]). It's then just a regular tree of "you either pick the next player or skip them", until you run out of players or have 5. If you traverse all possible decisions you could make on this - you'll have all possible unique teams without duplicates. The only 'inefficiencies' are the teams you make that are too small. (I appreciate this is an example) — , Oct 13 '17 at 13:57
This problem already has an answer on [cs.se](https://cs.stackexchange.com/questions/11/generating-combinations-from-a-set-of-pairs-without-repetition-of-elements) — , Oct 13 '17 at 14:14
The team problem (divide 2n players into 2 teams of size n) can be trivially solved by selecting A and n-1 of the remaining 2n-1 players for the first team and the rest of the players for the second team. I assume you are looking for something more general but it is not clear to me what sort of generalisation you seek. — rici, Oct 13 '17 at 17:14

score 0 · Answer 1 · answered Oct 13 '17 at 14:33

"A" has to be in one of the teams so we can just create all Teams that have "A" inside to avoid getting the same combination.

For each group we have a look at all possible new elements that could be added. If you add one element then only allow elements to be added that come later in that list ( done in still_available = available[i:]) to not get every permutation for each team.

If one group has enough members (5) add it to the list with all possibilities.

Since you need atleast 5 members you need to add one of the members of index 0, ..., len(available) - ( 5 - len(fixed_group) - 1) because else there would be only the len(fixed_group) that you already chose and (5 - len(fixed_group) - 1) available left which is less than 5.

input = ["B", "C", "D", "E", "F", "G", "H", "I", "J"]
global_poss_groups = []

def recursive_find_groups(fixed_group, available):
    if len(fixed_group) == 5:
        global_poss_groups.append(fixed_group)
        return -1
    for i in range(len(available) - ( 5 - len(fixed_group) - 1)):
        still_available = available[i:]
        new_element = still_available.pop(0)
        new_group = fixed_group[:]
        new_group.append(new_element)
        recursive_find_groups(new_group, still_available)

recursive_find_groups(["A"], input)
print(global_poss_groups)
print(len(global_poss_groups))

rici · Accepted Answer · 2017-10-16T06:43:55.863

The key to enumerating without repetition is often to select a canonical ordering. For example, to enumerate combinations of k elements selected from a universe of size n, we can ensure uniqueness by only generating combinations in sorted order. (This can be made to work even if the universe contains repeated elements, but that's not relevant here.)

In the case of assigning players to teams, we are looking for a partition of a universe of size kn into k teams of n players each. (In your example, k is two, but it is easy to generalize to any value of k.) We make a canonical selection by:

sorting the players in each team
sorting the teams by first player

We enumerate partitions recursively on the parameter k.

If k is 1, then the solution is simply the set of players (in sorted order) as a single team. For any larger value of k, we place the first player into the first team, and then:

for each first team created with the selected player and some (sorted) combination of n-1 players from the remaining set of players:
- recursively enumerate all partitions of the remaining (k-1)*n players into k-1 teams.

A different (but similar) partition enumeration problem is solved in this SO post. That answer contains a general iterative mechanism which can be used for many similar problems, including this one.

Enumerate permutation

2 Answers2

Linked