Iterate (loop) through complicated range of numbers using groups to generate Bracket Sheet

Question

I'm trying to build an algorithm for processing bracket sheet of competitions. I need to go through a range of numbers. For each number there will be the athlete name. Numbers are assigned to athletes randomly but the number's pairing must always stay the same. There are two groups odd and even, i.e. A and B.

The only problem that I can't find the proper algorithm to iterate numbers the exact way as follows:

Group A:
--------
  1
  17

  9
  25
------
  5
  21

  13
  29
------
  3
  19

  11
  27
------                         
  7
  23

  15
  31


Group B:
--------
  2
  18

  10
  26
------                          
  6
  22

  14
  30
------   
  4
  20

  12
  28
------
  8
  24

  16
  32

Could someone please help with advice or example of how to get the output above?

EDIT 1:

The example above is the bracket sheet for 32 athletes! Same logic must be applied if you use a sheet for 4,8,16,64 or 128 athletes!

EDIT 2:

Let's make it more clear with examples of the sheet for 4 athletes and then the sheet for 16 athletes.

The sheet for 4 athletes:

Group A:
--------
  1
  3

Group B:
--------
  2
  4

The sheet for 16 athletes:

Group A:
--------
  1
  9

  5
  13
------
  3
  11

  7
  15

Group B:
--------
  2
  10

  6
  14
------                              
  4
  12

  8
  16

EDIT 3:

The last part, is that I'm planning to have an array with athlete name and its status in it. By status I mean that, if the athlete has been a champion previously (strong), then he/she gets 1 for status, if the athlete's previous achievements are not known or minimal (weak), then the status is 0. It's done that way, so we could separate strongest athletes into different groups and make sure that they will not fight against each other in the first fight but rather meet each other closer to the semi-final or final.

Example of PHP array:

$participants = array(
array("John", 0),
array("Gagan", 0),
array("Mike Tyson", 1),
array("Gair", 0),
array("Gale", 0),
array("Roy Johnes", 1),
array("Galip", 0),
array("Gallagher", 0),
array("Garett", 0),
array("Nikolai Valuev", 1),
array("Garner", 0),
array("Gary", 0),
array("Gelar", 0),
array("Gershom", 0),
array("Gilby", 0),
array("Gilford", 0)
);

From this example we see that those, who have status 1 must be in different groups, i.e. A and B. But we have only two groups of numbers odd and even and in this example, there are 3 strong athletes. Thus two of them will be at the same group. The final result must be, that those two strong athletes, that got in the same group, must not meet at the very first fight (it means that they will not be on the same pair of numbers and as far away from each other as possible, so they wouldn't meet on the second fight as well).

Then randomly, I'm planning to rearrange the array and send athletes to the bracket sheet - every time, with different numbers, every time, those that have a flag 1 go to different groups and/or never meet at the first fight and every time, athletes' names assigned to the same pair of numbers.

Answer 1

Considering the number of participants is always a power of 2, this piece of code should give you the order you're expecting.

function getOrder($numberOfParticipants) {
    $order = array(1, 2);

    for($i = 2; $i < $numberOfParticipants; $i <<= 1) {
        $nextOrder = array();
        foreach($order as $number) {
            $nextOrder[] = $number;
            $nextOrder[] = $number + $i;
        }
        $order = $nextOrder;
    }

    return $order; // which is for instance [1, 17, 9, 25, and so on...] with 32 as argument
}

About the way it works, let's take a look at what happens when doubling the number of participants.

Participants | Order
           2 | 1   2
           4 | 1   3=1+2   2   4=2+2
           8 | 1   5=1+4   3   7=3+4   2   6=2+4   4   8=4+4
         ... |
           N | 1         X         Y         Z         ...
          2N | 1   1+N   X   X+N   Y   Y+N   Z   Z+N   ...

The algorithm I used is the exact same logic. I start with an array containing only [1, 2] and $i is actually the size of this array. Then I'm computing the next line until I reach the one with the right number of participants.

On a side note: $i <<= 1 does the same than $i *= 2. You can read documentation about bitwise operators for further explanations.

---

About strong athletes, as you want to keep as much randomness as possible, here is a solution (probably not optimal but that's what I first thought):

1. Make two arrays, one with strongs and one with weaks
2. If there are no strongs or a single one, just shuffle the whole array and go to 8.
3. If there are more strongs than weaks (dunno if it can happen in your case but better be safe than sorry), shuffle the strongs and put the last ones with weaks so both arrays are the same size
4. Otherwise, fill up the strongs with null elements so the array size is a power of 2 then shuffle it
5. Shuffle the weaks
6. Prepare as many groups as they are elements in the strongs array and put in each group one of the strongs (or none if you have a null element) and complete with as many weaks as needed
7. Shuffle each group
8. Return the participants, ordered the same way than previous function resulting array

And the corresponding code:

function splitStrongsAndWeaks($participants) {
    $strongs = array();
    $weaks = array();

    foreach($participants as $participant) {
        if($participant != null && $participant[1] == 1)
            $strongs[] = $participant;
        else
            $weaks[] = $participant;
    }

    return array($strongs, $weaks);
}

function insertNullValues($elements, $totalNeeded)
{
    $strongsNumber = count($elements);
    if($strongsNumber == $totalNeeded)
        return $elements;
    if($strongsNumber == 1)
    {
        if(mt_rand(0, 1))
            array_unshift($elements, null);
        else
            $elements[] = null;
        return $elements;
    }
    if($strongsNumber & 1)
        $half = ($strongsNumber >> 1) + mt_rand(0, 1);
    else
        $half = $strongsNumber >> 1;
    return array_merge(insertNullValues(array_splice($elements, 0, $half), $totalNeeded >> 1), insertNullValues($elements, $totalNeeded >> 1));
}

function shuffleParticipants($participants, $totalNeeded) {
    list($strongs, $weaks) = splitStrongsAndWeaks($participants);

    // If there are only weaks or a single strong, just shuffle them
    if(count($strongs) < 2) {
        shuffle($participants);
        $participants = insertNullValues($participants, $totalNeeded);
    }
    else {
        shuffle($strongs);

        // If there are more strongs, we need to put some with the weaks
        if(count($strongs) > $totalNeeded / 2) {
            list($strongs, $strongsToWeaks) = array_chunk($strongs, $totalNeeded / 2);
            $weaks = array_merge($weaks, $strongToWeaks);
            $neededGroups = $totalNeeded / 2;
        }
        // Else we need to make sure the number of groups will be a power of 2
        else {
            $neededGroups = 1 << ceil(log(count($strongs), 2));
            if(count($strongs) < $neededGroups)
                $strongs = insertNullValues($strongs, $neededGroups);
        }

        shuffle($weaks);

        // Computing needed non null values in each group
        $neededByGroup = $totalNeeded / $neededGroups;
        $neededNonNull = insertNullValues(array_fill(0, count($participants), 1), $totalNeeded);
        $neededNonNull = array_chunk($neededNonNull, $neededByGroup);
        $neededNonNull = array_map('array_sum', $neededNonNull);

        // Creating groups, putting 0 or 1 strong in each
        $participants = array();            
        foreach($strongs as $strong) {
            $group = array();

            if($strong != null)
                $group[] = $strong;
            $nonNull = array_shift($neededNonNull);
            while(count($group) < $nonNull)
                $group[] = array_shift($weaks);
            while(count($group) < $neededByGroup)
                $group[] = null;

            // Shuffling again each group so you can get for instance 1 -> weak, 17 -> strong
            shuffle($group);
            $participants[] = $group;
        }

        // Flattening to get a 1-dimension array
        $participants = call_user_func_array('array_merge', $participants);
    }

    // Returned array contains participants ordered the same way as getOrder()
    // (eg. with 32 participants, first will have number 1, second number 17 and so on...)
    return $participants;
}

If you want the resulting array to have as indexes the number in the bracket, you can simply do:

$order = getOrder(count($participants));
$participants = array_combine($order, shuffleParticipants($participants, count($order)));