I'm sorry, but your problem just isn't very clear. Having read your question and the discussion I am not sure that I understand a number of basic things. The cause of this is that you have created a private language from familiarity with the problem, and are not aware that you have not communicated what this language is clearly to bystanders. Unfortunately this means that nobody can help you because they don't understand you.

But I think I have puzzled out your real question. Please correct this description if it is wrong.

Many schools register many particpants (a participant can be one person, or a team of 2-3 people) for many different competitions. A participant is also called a competitor. Each competition takes place in 3 rounds. In each round the participants are divided into a series of panels. The members of a panel all compete in front of some judge who scores the round. For logistical reasons panels should be around the same size as each other, and their size should not exceed 6. For resource reasons you would like to do this with as few judges as possible for the competition.

The maximally flexible situation is one where your program gets information about how many schools are in a given competition, how many participants each provides, and optionally the number of judges that you need. It is then supposed to devise up the best schedule that it can for the 3 rounds of competition. It appears from running your code that you have set the number of students per school to 3, and you decide the number of judges according to some rule that I didn't look up.

And there are two additional complex requirements. First you don't want to ever have 2 participants from the same school on the same panel. You would also like to avoid having pairs of participants appear in different rounds on the same panel as each other.

Is this right? If so then a few observations.

You claim to have found that setting this up by hand for a small number of participants is fairly easy. But you can't always satisfy all of the rules. My guess is that when you went to the math people asking to find the perfect solution, they taught you factorials to show you how many different possible solutions you had to search through to find the perfect answer. (You might have even written code that should work, but it didn't finish?)

My first suggestion is that if you really can assume that there are always 3 competitors per school then you should pre-build a set of optimal solutions in a data file, and then have your CGI script just return the one that matches the size that you have handled. That leaves the problem of generating those optimal solutions..once.

My suggestion for that is that you write a program to look for good solutions, but not worry about perfection. Here is a possible algorithm that I would try writing for the absolutely general problem (arbitrary number of schools, arbitrary number of participants per school, fixed number of judges handed to me).

  1. Decide the sizes of each panel so that they are as close to even as possible (we are not worrying about your "6 participants" rule here - just break them up as evenly as you can).
  2. Randomly assign participants to panels, taking care not to assign 2 people from the same school to the same panel.
  3. Calculate how many undesired "collisions" you have (2 people from the same school on the same panel, people meeting in different rounds).
  4. Go through each round and pair of participants (I would do this in random order), and decide whether to switch them. You won't switch if it puts two people from the same school on the same panel. You won't switch if it increases the number of times that 2 people meet multiple times on the same panel. You will if it reduces number of pairs that meet twice. When it is a wash, randomly choose whether or not to flip them.
  5. Repeat the previous step while there are any collisions left and you managed to reduce the number of collisions any time in the last 3 passes. (3 is an arbitrary number.)
  6. Write out your "best I could do" solution.
Then I would work out your optimal solutions to your original problem by, for each number of schools, starting with as few judges as you can, and apply the above program to find the best solution that it finds. Stop with the number of judges that gives you the first perfect solution.

In reply to Re: Perl for Adjudication by tilly
in thread Perl for Adjudication by dejoha

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.