What I mean by only having four options refers to the fact that competitor A1 cannot compete against two members of another school, thus violating rule #1. You are correct in saying that A1 has more than four possible groupings.

I haven't tried to keep track of each panel (yet) but I do like your idea. The reason my solution doesn't really work is because I was just making and shifting rows back and forth, much like a bad carnival game with ducks on a track.

My question, I suppose, is trying to find out 1) is there a simple (or complex, but doable) mathematical solution to find matches (factorials just tell you how many possible combinations, but not unique combinations for each unit). 2) is there a better way to structure a program to fill these panels.

I like your idea of keeping track of each user/panel. I'll have to think about that one for a little while.

I'm sorry about the ambiguity -- you're right about the jargon I am using. Let me try to clarify a few things as best I can.

For simplicity in the program, I make the assumption that each school registers the maximum number of students as competitors. Let's say we have 10 schools register monologues. The maximum a school can enter in this category is 3. This would give us a maximum total of 30 competitors (in this case, 30 students). Let "A1" stand for school A, entry 1, and so on:



A1  B1  C1  D1  E1  F1  G1  H1  I1  J1
A2  B2  C2  D2  E2  F2  G2  H2  I2  J2
A3  B3  C3  D3  D3  F3  G3  H3  I3  J3
[download]

There are 3 rounds. Each competitor must compete in each round. In order to accomplish this, we divide the total number of competitors into groups and send them into separate rooms, each one adjudicated by a single judge. These are the panels. Panels = Rooms. We want to keep the number of competitors in each room under six for timing purposes (each competitor performs between 3 - 5 minutes).

At this point, we do not need to worry about the number of judges needed. In the example above, we have 30 competitors. We could use 6 rooms and 6 judges with 5 competitors in each room. Round one might look like this:

Round 1
---+----+----+----+----+----
A1 | A2 | A3 | B1 | B2 | B3
C1 | C2 | C3 | D1 | D2 | D3
E1 | E2 | E3 | F1 | F2 | F3
G1 | G2 | G3 | H1 | H2 | H3
I1 | I2 | I3 | J1 | J2 | J3
[download]

One thing that I think would be most valuable, would be to find out if it is even possible to make round 2 and 3 work without breaking the competitions "rules." I think this is the reason I was told about factorials. If I could find out whether or not a certain set would or would not work, I could modify the program to work only when the number of schools is > X (for example).

Factorials only tell you the possible matches. It doesn't factor in if a match fits my criteria. Does that make sense?

This was why I tried to illustrate using a diagram. I was tying to see if there was a mathematical solution to figure out "how many matches are left." In my illustration, I stated that for competitor A1, after round one, his possible matches are reduced by 4. I'm not a math major, so I don't really know how to state this very clearly, but it seems like it should be some kind of simple algebra. Maybe?

I thought that if I could figure out the "number of matches left", I might be able to use that information to find out what matches are left and use them for the next round (instead of iterating through a random list over and over). Doing it randomly seems like it would take a very long time to compute. However, if I knew mathematically what matches wouldn't work, I wouldn't have to do the randomness, per se.

Since the possible matches is reduced each round, it is like an intricate puzzle --- the pieces can only fit a certain way.

I hope this helps someone. I keep wanting to have a mathematical solution I can use with Perl that would help take some of the guesswork out of it. I don't mind putting Perl to work in a random recursive subroutine, but it seems like that breaks the Perl laziness rule :)

It would be great if there were a pattern in the way you assign competitors into panels. Anyone see a pattern?

Here's a couple of sample runs:

[pimento:~] simonm% perl -w /tmp/t.pl 1 2 3
Competing: 3 schools, 6 entrants
Structure: 3 rounds of 3 panels
Panel Size: 2 entries each
Calculation: required 5 attempts in 0 seconds

Teams:
- A1
- B1, B2
- C1, C2, C3

Round 1:
- B2, C3
- C1, B1
- C2, A1

Round 2:
- C3, B1
- A1, C1
- B2, C2

Round 3:
- C2, B1
- A1, C3
- C1, B2

perl -w /tmp/t.pl 3 3 3 3 3 3 3 3 3 3
Competing: 10 schools, 30 entrants
Structure: 3 rounds of 6 panels
Panel Size: 5 entries each
Calculation: required 1062 attempts in 12 seconds

Teams:
- A1, A2, A3
- B1, B2, B3
- C1, C2, C3
- D1, D2, D3
- E1, E2, E3
- F1, F2, F3
- G1, G2, G3
- H1, H2, H3
- I1, I2, I3
- J1, J2, J3

Round 1:
- B2, C2, D1, J2, A2
- C3, I2, H3, J3, G3
- E1, F1, I1, B3, A3
- F3, B1, H1, C1, G2
- E3, H2, F2, D2, A1
- D3, E2, J1, G1, I3

Round 2:
- A1, G1, C3, B1, J2
- D3, A2, J3, I1, H2
- B3, H1, I3, G3, D2
- E2, A3, H3, F3, C2
- E3, J1, C1, F1, B2
- G2, F2, D1, I2, E1

Round 3:
- F1, H1, I2, E2, J2
- B1, A2, G3, J1, F2
- I3, C2, E1, J3, A1
- C1, H2, A3, D1, G1
- B3, C3, F3, D3, E3
- I1, G2, D2, H3, B2
[download]

And here's the source code:

use strict;

### Constants

my $number_of_rounds = 3;
my $max_per_panel = 6;
my $max_per_team = 3;

# Make this number bigger to get better results at the cost of running
+ slower
my $attempts_before_enlarging_panels = 1000; 

### Parse Arguments

unless ( scalar @ARGV ) {
  print "Usage: pass the number of participants from each team as argu
+ments\n";
  exit;
}
my @entrants = @ARGV;

### Build Teams

my %teams;
my $team_id = 'A';
foreach my $count ( @entrants ) {
  die "Too many people on team $team_id: $count" if ( $count > $max_pe
+r_team );
  foreach my $j ( 1 .. $count ) {
    $teams{$team_id}->[ $j - 1 ] = "$team_id$j";
  }
  $team_id ++;
}

my @participants = map { @$_ } values %teams;

### Declare Result Variable

my @rounds;
my $start_time = time();
my $attempts = 1;

### Determine Panel Size

my $panels_required = int( .99 + scalar(@participants) / $max_per_pane
+l );
$panels_required = $max_per_team if ( $panels_required < $max_per_team
+ );

PANEL_EXPANSION: {
  
  my $base_per_panel = int( scalar(@participants) / $panels_required )
+;
  my $oversize_panels = scalar(@participants) - ($panels_required * $b
+ase_per_panel );
  my $most_per_panel = $base_per_panel + ( $oversize_panels ? 1 : 0 );
  my @panel_sizes = ( 
      ( $oversize_panels ? ( $most_per_panel ) x $oversize_panels : ()
+ ),  
      ( $base_per_panel ) x ( $panels_required - $oversize_panels )
  );

### Attempt to Build Panels 

  ATTEMPT: {
    
    # The "zero round" contains the teams themselves
    @rounds = [ map $teams{$_}, sort keys %teams ];
    foreach my $round ( 1 .. $number_of_rounds ) {
      # warn "Building round $round\n";
    
      my %exclusions;
      foreach my $panel ( map @$_, @rounds ) {
        foreach my $a ( @$panel ) {
          foreach my $b ( @$panel ) {
            $exclusions{$a}->{$b} = 1;
          }
        }
      }
    
      # warn "Should exclude: " . join(', ', map { my $a = $_; map "$a
+-$_", sort keys %{$exclusions{$a}} } sort keys %exclusions) . "\n";
    
      my @available = @participants;
      my @panels;
      foreach my $panel ( 1 .. $panels_required ) {
        # warn "  Building panel $panel ($panel_sizes[$panel - 1])\n";
        my @entries;
        foreach ( 1 .. $panel_sizes[$panel - 1] ) {
          last unless scalar @available;
          my %exclude = map { $_ => 1 } 
                                map { sort keys %{$exclusions{$_}} } @
+entries;
          # warn "      Avoiding " . join(', ', sort keys %exclude) . 
+"\n";
          my @candidates = ( grep { ! $exclude{$_} } @available ) or d
+o {
            # warn "Can't find a candidate in: " . join(', ', @availab
+le);
            if ( $attempts ++ % $attempts_before_enlarging_panels ) {
              # warn "Trying again..."
              redo ATTEMPT;
            } else {
              # warn "This is taking too long; expanding number of pan
+els...";
              $panels_required ++;
              redo PANEL_EXPANSION;
            }
          };
          my $candidate = $candidates[ int rand scalar @candidates ];
          # warn "    Selecting $candidate\n";
          push @entries, $candidate;
          @available = grep { $_ ne $candidate } @available;
        }
        # @entries = map $teams{$_}->[$panel - 1], sort keys %teams;
        $panels[$panel - 1] = \@entries;
      }
      $rounds[$round] = \@panels;
    }
  }

### Display Competition Info

  print "Competing: " . scalar(@entrants) . " schools, " . 
                        scalar(@participants) . " entrants\n";
  print "Structure: $number_of_rounds rounds of $panels_required panel
+s\n";
  print "Panel Size: $most_per_panel entries " . ( $oversize_panels ? 
        "or less (" . join(', ', @panel_sizes) . ")" : 'each' ) . "\n"
+;
  print "Calculation: required $attempts attempts in " . 
        ( time - $start_time ) . " seconds\n";
  
}

### Display Teams and Rounds

foreach my $round ( 0 .. $#rounds ) {
  print( "\n" . ( $round ? "Round $round" : "Teams" ) . ":\n" );
  my @panels = @{ $rounds[$round] };
  foreach my $panel ( @panels ) {
    print( "- " . join(', ', @$panel) . "\n" )
  }
}
[download]

As you can see, it's not terribly elegant, and there's a chance that it will needlessly allocate one or two more panels than are strictly needed, but it handles arbitrary numbers of entries from each school, and it does seem to work consistently.

Actually, I must say that your response really floored me. I told a friend of mine that someone helped solved my problem and he replied, "you mean a total stranger helped you?" I guess I hadn't thought of that but it has really hit home.

It is this kind of sharing that really motivates me. I am reminded of a quote by Wm. Danforth, "Our greatest possessions, when shared, multiply."

This kind of "sharing" is really motivating for me. I hope I can "give back" as equally (although, right now, I'm afraid all the easy questions I can help answer are already taken).

I'll try to help give back as I have been given.

Thanks again!

This is AMAZING! Wholly cow! This was more than I ever expected. Thank you! Thank you! Thank you!

The Monks Have Spoken!

Seriously, I am very grateful. I am still looking over this code to figure it so I can learn from your example.

Let me know when you're coming down to Cedar City, and I'll get you some tickets to any show! Well, as long as you act within the next few months -- I'll soon be off to my final capstone/thesis project.

All the best!

I probably won't get out to Utah any time soon, but I'm glad to have helped!

(If you want to express your appreciation in some more concrete way, consider donating the cost of a ticket to the PerlMonks Offering Plate.)

I was on a debate team in high school, so the application area was already quite familiar to me... I was somewhat surprised to not find pre-existing software that solved this problem, since it must exist somewhere, but perhaps I just didn't come up with the right combination of search terms.

A panel includes a group of competitors and one judge.

Here you probably want to solve for various sizes of the problem and save the tables for later use. If the event is mandating the number of players a school must bring, that would help.

Create a table containing each panel of each round. Each panel in the table contains a spot for every player in the event. In very simplistic progression load each panel in order, after each panel is loaded check for legality, if there is a conflict, back up, and try the next pattern in the progression. When you get to the last panel and have no conflicts you have a solution. Apparently you need only one per round.

This is a N-queens problem with one extra dimension. To simplify your problem for any particular case, solve for the next exact fit larger. That is if you have 100 players going into 21 panels add 5 dummy-players so your panels are all the same. (Dummy players so each school has the same number of players could help also.)

In the case above each panel could contain 5 player numbers. The progression for each panel could be:

 0  0  0  0  0
 1  0  0  0  0
 1  2  0  0  0
 1  2  3  0  0
 1  2  3  4  0
 1  2  3  4  5  # first possibly valid set, though having
 1  2  3  4  6    # 1 2 3 be from the same school lets you
 1  2  3  4  7    # quickly skip obviously invalid matchings
 ...              # getting to something like
 1  4  7  11 14   # <- fairly quickly
 ...              
 1  2  3  4 105   
 ...
 1  2  3 104 105
 ...
101 102 103 104 105 # last possible value
[download]

There are a lot of possibilities so look for efficiencies. Each round should not redo the work of the prior rounds but continue to solve from that position. Find the first and last non-self-conflict state for a panel for each round and eliminate checking some useless states.

I spent some time thinking along these lines, but the scale of the problem made me cautious -- with over 100 entries per event, there are a massive number of possible combinations. Even with a fair amount of optimization, we're probably talking about days, or at least hours, of computation to work through them...

And given the real-world possibility that some teams may be added at the last minute or fail to show up on the day of the event, you'd probably need to pre-calculate the choices for different numbers of entries from different numbers of schools, which means repeating the above computation thousands or millions of times.

Given those constraints, it seemed the best real-world solution for the OP would be an approximate, non-exhaustive one -- although I'm sure that the solution I posted above could be improved with further effort.

Good questions!

1. Nearly sixty schools from six states are expected to compete.
2. Each school is limited to up to 3 mono acts and 2 duo/trio scenes.
3. Panels should have at least 2 competitors but no more than 6 (more panels may be created to accomodate).
4. Monologues only compete against monologues and the same for duo/trios.
5. The two "events" are scheduled seperately but occur at the same time.
6. Unlike sporting competitions, the rounds/panels do not eliminate competitors. In a drama competition you are judged on specific criteria and are given points. At then end of three rounds, the top-three competitiors with the most points are awarded first, second, and third places.
7. Parings can be as random as needed, so long as the rules are adhered to (e.g. you cannot compete against your own school and cannot compete against someone you've already competed against.

It is also useful to know that an automated system is only really helpful where there are over 6 participating schools. Under this number it is easy to do the paneling by hand, partly because it is likely that you will have to compete against someone again.