How to create equally distributed groups of three?

Question

For a website application I need to form random groups of three. The user him/herself cannot grade him/herself (so cannot be part of the group). There will always be a minimum of 4 users.

For example, if there were 5 users, I would have an array as such: Array(0,1,2,3,4) and I would want the output to be (where the key is the user and the data is the group of 3).

Array(
[0 : 1,2,3],
[1 : 0,2,4],
[2 : 1,4,3],
[3 : 0,1,4],
[4 : 0,2,3]
);

Notice the user is never in the group and every user is assigned exactly 3 times.

You cannot simply randomly select users to groups because it might be assigned more than 3 times and force some groups to have less than 3 users in the group.

I hope I explained this problem appropriately and someone will be able to help.

Here is some code that puts three random numbers in a dictionary and works fine for [0,1,2,3] but will (most likely) fail for anything larger because the number will not be equally distributed (and will continue in the while loop forever because there are no possible numbers left).

$rows = range(0,3);
$array_size = count($rows);
$peers_array = Array();
$number_count = array_fill(0, $array_size, 0);

foreach($rows as $index => $row){
    $randomNumbers = Array();
    for($x = 0; $x < 3; ++$x){
        $randomNumber = rand(0, $array_size-1);
        while($randomNumber==$index or in_array($randomNumber, $randomNumbers) or $number_count[$randomNumber]>2)
            $randomNumber = rand(0, $array_size-1);
        $number_count[$randomNumber]++;
        $randomNumbers[] = $randomNumber;
    }
    $peers_array[$index] = $randomNumbers;
}
print_R( $peers_array);

Answer 1

Ok so I've come up with my own solution. It took a little thought but thanks to suggestions I was able to come up with this solution:

First it generates a range from 0 to the number of users - 1 (e.g. for 5 it would give [0,1,2,3,4]) then every time after that it shifts the list one (e.g. [0,1,2,3,4] becomes [4,0,1,2,3]) then it takes each element at a given index of the array and puts it into a group (so if I only wanted groups of 2 it would give 0:[0,4] 1:[0,1] 2:[2,1] and so on...). You then shift the order between the number of users - the size of the group, don't ask just trust me. This guarantees all numbers appear an equal number of times but still randomizes the order.

The lines below accomplishes this:

function getUsers($user_num, $groups_of){
    $index_list = range(0,$user_num-1);
    $random_indexes = range(0,$user_num-1);
    shuffle($random_indexes);

    $groups = array();
    foreach($index_list as $user_num)
        $groups[] = array($random_indexes[$user_num]);

    for($i = 0; $i<($groups_of-1); ++$i){
        array_unshift($index_list, array_pop($index_list)); //puts the last element first

        foreach($index_list as $index => $user_num)
            $groups[$index][] = $random_indexes[$user_num];
    }

    $shift_number = rand(1, ($len_users-$groups_of));
    for($i = 0; $i<$shift_number; ++$i)
        array_unshift($groups, array_pop($groups));

    return $groups
}

Answer 2

I was thinking array_pop would be a good approach, it works well for the first part of the problem, easy to get the current item and make sure it isn't available for the next part, however then you end up having to keep track of too many moving parts.

In the end went for array_diff to remove the current row from the original array.

$rows = range(0,15);
$results = array();
foreach ($rows as $row) {
    $others = array_diff($rows,array($row));
    shuffle($others);
    $results[$row] = array_slice(array_values($others),0,3);
}
var_dump($results);

Results:

array (size=16)
  0 => 
    array (size=3)
      0 => int 9
      1 => int 1
      2 => int 10
  1 => 
    array (size=3)
      0 => int 10
      1 => int 11
      2 => int 14
  2 => 
    array (size=3)
      0 => int 3
      1 => int 15
      2 => int 14
  3 => 
    array (size=3)
      0 => int 9
      1 => int 4
      2 => int 1
      etc...

Answer 3

I think this:(to generalize)

function getUsers($users,$groups_of){
    $result = array();
    for($i = 0; $i < $users; $i++){
        $usernums = array();
        while(count($usernums) < $groups_of){ 
            $randomNumber = rand(0, $users-1);
            if($i != $randomNumber && !in_array($randomNumber, $usernums)){
                $usernums[] = $randomNumber;
            }
        }
        $result[$i] = $usernums;
    }
    return $result;
}


$users = 5;
$groups_of = 3;
print_r(getUsers($users,$groups_of));