Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Sports Team allocation

by thealienz1 (Pilgrim)
on Jul 18, 2002 at 16:25 UTC ( #182891=perlquestion: print w/replies, xml ) Need Help??

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

Alright right now I am a bit confused... I have been given a challenge to perform in any programming language of my choosing. I don't have to tell you whihc one I picked to use.

The problem seems like a simple one. Here are the rules to the program/challenge/algorithm I need to implement.

  • There are n number of people.
  • These people need to be divided up into x amount of teams, evenly.
  • This needs to be done d time(s), so that no two people are ever in the same group again.

Currently I have worked out my own implementation of the algorithm, but my only problem is that it takes forever to generate the teams. I was wondering if anyone had any idea how to do this more efficiently. I would post my code, but I am sort of away from the computer that has it. Damn vacations... :)

thealienz

Replies are listed 'Best First'.
Re: Sports Team allocation
by atcroft (Abbot) on Jul 18, 2002 at 17:02 UTC

    Have you considered Algorithm::Permute? It might be helpful, but I have not used it much myself. Just a thought.

Re: Sports Team allocation
by Aristotle (Chancellor) on Jul 18, 2002 at 17:26 UTC
    Unless I'm overlooking something, it sounds like a job for backtracking.. Abigail-II recently posted a meditation on using the regex engine in Perl to solve backtracking problems (in his case, the N-queens problem).

    Makeshifts last the longest.

Re: Sports Team allocation
by flounder99 (Friar) on Jul 18, 2002 at 17:40 UTC
    merlyn has a nice writeup about permutations and combinations here. You may want to do a super search on permutations and combinations.

    --

    flounder

Re: Sports Team allocation
by Abigail-II (Bishop) on Jul 19, 2002 at 14:29 UTC
    There's no need to calculate all the permutations or combinations. Think people, think! You have 48 players, arrange them in a 6 x 8 matrix:
        0    6   12   18   24   30   36   42
        1    7   13   19   25   31   37   43
        2    8   14   20   26   32   38   44
        3    9   15   21   27   33   39   45
        4   10   16   22   28   34   40   46
        5   11   17   23   29   35   41   47
    
    Then you can create teams by going around horizontally, vertically, and diagonally. You just have to skip to a different column or row whenever to cross an edge. Or, in other words, we're going to tile the plane with the above matrix, but each time we put down another time, we shift a bit. We shift a row if a place a tile to the right, and a column if we place a tile above. We can then start any place and either go to the right, go down, or go up-right and make a team from each of the next 6 numbers; repeating that 8 times.

    This boils down to the following program:

    #!/usr/bin/perl use strict; use warnings 'all'; my @people = (0 .. 47); my @data; my @z = (0, 0, 0); my @inc = (1, 6, 5); my @skew = (0, 1, 0); my @drift = (0, 0, 12); for (my $x = 0; $x < 8; $x ++) { for (my $y = 0; $y < 6; $y ++) { for (my $z = 0; $z < @z; $z ++) { push @{$data [$z] [$x]} => $people [$z [$z]]; $z [$z] += $inc [$z]; $z [$z] += $drift [$z] if 5 == $z [$z] % 6; $z [$z] -= @people - $skew [$z] if $z [$z] >= @people; } } } my $r = 0; foreach my $info (@data) { printf "Round %d\n", ++ $r; my $t = 0; foreach my $team (@$info) { printf "Team %d: ", ++ $t; map {printf "%2d " => $_} @$team; print "\n"; } print "\n"; } __END__ Round 1 Team 1: 0 1 2 3 4 5 Team 2: 6 7 8 9 10 11 Team 3: 12 13 14 15 16 17 Team 4: 18 19 20 21 22 23 Team 5: 24 25 26 27 28 29 Team 6: 30 31 32 33 34 35 Team 7: 36 37 38 39 40 41 Team 8: 42 43 44 45 46 47 Round 2 Team 1: 0 6 12 18 24 30 Team 2: 36 42 1 7 13 19 Team 3: 25 31 37 43 2 8 Team 4: 14 20 26 32 38 44 Team 5: 3 9 15 21 27 33 Team 6: 39 45 4 10 16 22 Team 7: 28 34 40 46 5 11 Team 8: 17 23 29 35 41 47 Round 3 Team 1: 0 17 22 27 32 37 Team 2: 42 11 16 21 26 31 Team 3: 36 5 10 15 20 25 Team 4: 30 47 4 9 14 19 Team 5: 24 41 46 3 8 13 Team 6: 18 35 40 45 2 7 Team 7: 12 29 34 39 44 1 Team 8: 6 23 28 33 38 43

    Abigail

Re: Sports Team allocation
by thealienz1 (Pilgrim) on Jul 19, 2002 at 03:44 UTC

    Some people asked me to give an example. The example I was give to work with was 48 people that needed to be divided up into 8 teams, which means 6 people per team. And then there needed to be 3 sets of these 8 teams, so that the people in the first set did not have the same people on their team in the second and third set.

      The first step would be to find the number of choices. In this case, we would use a combination rather than a permutation, since the order of our choices is irrelevant. We can find this number with:

      sub choose { my ($n, $k) = @_; my ($result, $j) = (1, 1); return 0 if $k > $n || $k < 0; $k = ($n - $k) if ($n - $k) < $k; while ( $j <= $k ) { $result *= $n--; $result /= $j++; } return $result; } my $people = 48; my $teams = 8; my $seasons = 3; print choose($people, ($people/$teams));
      In your case, there are a possible 12271512 different team combinations, but this isn't the complete answer yet. You'll actually want to generate these teams such that you can find which of them have repeated couples.

      I've got some coding for work to do, but I'll crunch on this throughout the day and update as I can, barring someone else having more freetime and posting a solution before I do.

      C-.

      Update: Or you could completely ignore my intellectually overstimulated response and go with what Abigail-II suggested, which will actually solve the problem. Thanks for the instruction.

      ---
      Flex the Geek

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://182891]
Approved by TStanley
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (4)
As of 2019-10-19 06:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Notices?