http://qs1969.pair.com?node_id=584963

tomazos has asked for the wisdom of the Perl Monks concerning the following question:

Suppose I have a list of peoples names:

my @people = ("Peter", "Paul", "Jane", "Mary", "Fred");

I want to arrange them into teams:

my @example_teams = (["Peter", "Mary"], ["Paul"], ["Jane", "Fred"]);

In fact, I want to get all possible teams:

my @all_teams = ( [["Peter"], ["Mary"], ["Paul"], ["Jane"], ["Fred"]], [["Peter", "Paul"], ["Mary"], ["Jane"], ["Fred"]], . . . [["Peter", "Mary", "Paul", "Jane", "Fred"]] );

But not by iterating over them and storing them in a table, because there isn't enough memory.

Instead I want a function that takes a scalar number and returns a given grouping and visa-versa:

lookupteam(\@people, \@example_team); # returns 42 constuctteam(\@people, 42); # returns [["Peter", "Mary"], ["Paul"], ["Jane", "Fred"]]

I understand this has something to do with algorithms for perumtations, combinatorics, stirling numbers of the second kind, etc, etc.

Can anyone give me some pointers on where to look, or what the algorithm is called? Or even write a quick version of lookupteam and constructteam?

Thanks, Andrew.

Replies are listed 'Best First'.
Re: Permutation of groups
by Limbic~Region (Chancellor) on Nov 19, 2006 at 18:58 UTC
    tomazos,
    I believe what you are looking for is combinations not permutations. This is because the team ('Sarah', 'John', 'Ashley') is the same any which way you order the members. There are a couple ways of doing your rank/unrank scheme.

    The first is to use binomial rankings as seen here. This approach is a bit cumbersome because it gives unique ranks for teams of a specific size only. This is fine as long as you pay attention to the size and adjust accordingly. For instance, you would need to specify the size of the team and the rank to retrieve the group:

    A B C D Size 4 = ABCD rank 1 Size 3 = ABC ABD ACD BCD rank 1 .. 4 Size 2 = AB AC AD BC BD CD rank 1 .. 6 Size 1 = A B C D rank 1 .. 4

    The second is to look at all the possible combinations and count in binary. This is the technique I used here (C code). Basically, the idea is to assign each element in the complete list a value and then for each combination to add them up. For instance:

    A = 2^0 = 1 B = 2^1 = 2 C = 2^2 = 4 D = 2^3 = 8 A C D = 1 + 4 + 8 = 13
    It should be pretty clear how to convert 13 back into powers of 2 and then get the original set back.

    If you need fully working code let me know.

    Cheers - L~R

Re: Permutation of groups
by ww (Archbishop) on Nov 19, 2006 at 19:03 UTC
Re: Permutation of groups
by blokhead (Monsignor) on Nov 20, 2006 at 15:05 UTC
    Actually this looks more like set partitions than combinations to me. You are splitting up a set into smaller subsets, and order and size of subsets doesn't matter. There is some sample code for a set partition iterator in one of my nodes Re: Generator of integer partitionts of n for starters, and plenty of other places too, probably, if you super search with that term.

    blokhead

      blokhead,
      I can see your point of view too. I admit that I focused on:

      In fact, I want to get all possible teams:

      While my solution addresses the above statement in isolation, taken in context with the rest of the post it is likely lacking. For instance:

      • For any given game, do all teams need to have the same number of players?
      • For any given game, can a player participate in more than one team?
      • For any given game, do all players need to play or can they "sit out"?

      I am not sure how much of your code addresses those points either but I am pretty sure it misses how to convert a team to a "number" and its reciprocal. Any ideas on that front?

      Cheers - L~R

        Specifically for a given partitioning ever person must belong to exactly one team.

        Teams do not have to be of the same size.

        eg For three people: 1. A B C 2. AB C 3. A BC 4. AC B 5. ABC

Re: Permutation of groups
by Limbic~Region (Chancellor) on Nov 21, 2006 at 01:11 UTC
    tomazos,
    This was an extremely tough cookie to crack so chances are I overcomplicated it. I plan on making a seperate writeup on this later.

    I updated the rank()/unrank() though they still assume player names are are unique. If your real data is not unique, you will need to handle that by using indices of the group instead of values of the group.

    Cheers - L~R