How to make a random names list without repeat in PHP?

Question

My task is simple - I get a list of names say:

John
Rose
Dave
Jade

and I need to assign each name two other names following these rules:

1. each name cannot repeat more than twice
2. subname != root name
3. root name cannot have equal subnames.

which means:

------ this is valid: --------------------------------------- this is not: -------

John - Rose, Dave  -------------------------------  John - Dave, Dave  
Rose - John, Jade    -------------------------------- Rose - Rose, Jade  
Dave - Jade, Rose    ------------------------------- Dave - Jade, John  
Jade - John, Dave   -------------------------------- Jade - John, Dave  

(dave's showing more than twice,
and John got him twice
and Rose got herself)

I've been trying to solve this problem for hours - assigning names for subnames1 and subnames2 is easy but when trying to allocate them to the root name, everything is getting messy.

Here is my latest failure:

$arr1 = $arr2 = $names = $arr;
        shuffle($arr1);
        shuffle($arr2);

        foreach ($arr1 as $key => $value) {
            $arr1[$key]['name2'] = $arr2[$key]['name'];
            $count = 0;
            foreach ($arr1 as $name) {
                if (in_array($arr2[$key]['name'], $name)) {
                    $count++;
                }
            }


            while ($arr1[$key]['name2'] == $arr1[$key]['name'] || $count > 2) {
                shuffle($arr2);
                $arr1[$key]['name2'] = $arr2[$key]['name'];
                foreach ($arr1 as $name) {
                    if (in_array($arr2[$key]['name'], $name)) {
                        $count++;
                    }
                }
            }
        }

        foreach ($names as $key => $name) {
            $randName = $names[array_rand($names)]['name'];
            while (in_array($randName, $arr1[$key]) || array_key_exists($randName, $arr1)) {
                $randName = $names[array_rand($names)]['name'];
            }
            $arr1[$randName] = $arr1[$key];
            unset($arr1[$key]);
        }

Any idea how this problem can be solved?

Answer 1

How about this?

<?php
        $names = array("John","Rose","Dave","Jade");
        $pickedupOnce = array();
        $pickedupTwice = array();

        for($i=0; $i <count($names); $i++) {
            echo "$names[$i] <br/>";
            // this is rootname
            // now pick two random subnames

            $loop =0;
            do {
                $subOne = array_rand($names,1);
                $loop++;
            } while($subOne === $i || in_array($subOne, $pickedupTwice) && $loop<10 );

            if(in_array($subOne, $pickedupOnce)) {
                array_push($pickedupTwice, $subOne);
            }
            else {
                array_push($pickedupOnce, $subOne);
            }

            $loop = 0;
            do {
                $subTwo = array_rand($names,1);
                $loop++;

            } while($subTwo === $i || $subTwo === $subOne || in_array($subTwo, $pickedupTwice) && $loop<10 );

            if(in_array($subTwo, $pickedupOnce)) {
                array_push($pickedupTwice,$subTwo);
            }
            else {
                array_push($pickedupOnce, $subTwo);
            }

            echo "Group = $names[$i] -- $names[$subOne],$names[$subTwo] <br/>\n";
            echo "Picked Once - ";
            for($j=0; $j<count($pickedupOnce); $j++) {
                echo "$pickedupOnce[$j],";
            }

            echo "<br />Picked Twice - ";
            for($j=0; $j<count($pickedupTwice); $j++) {
                echo "$pickedupTwice[$j],";
            }
            echo "<br/>";
        }



        ?>

Hope this helps...

Answer 2

I am not familiar with PHP syntax, so I will try a pseudo-code implementation, hope it is ok for you

Input: nameList as string[].
Output: resultList as string[]

def secNames as string[]
    name1 as string
    name2 as string 

// make a list with two copies of all names 
for (i=0;i<length(nameList);i+1)
{ 
  secNames[i]=nameList[i]
  secNames[2*length(nameList)-i-1]=nameList[i]
}
// N.B.: first half of secondary names list is the same 
// as original, the second half is reversed so in your
// example we get: 
// "John","Rose","Dave","Jade","Jade","Dave","Rose","John"


// scan list of primary names 
for (i=0;i<length(nameList);i+1)
{
   resultList[i]=nameList[i]+" - "
   name1=""
   name2=""

   for (j=0;j<length(secNames);j+1) // scan secondary names
   {
     if (name1 <> secNames[j] and 
         name1 ="" and // skip this if found 1st sec.name 
         nameList[i] <> secNames[j]) // never pick main name
          {
            name1=secNames[j] // found first name
            secNames[j]="" // make this choice not  
                           // available on next pass
          }
       if (name2 <> secNames[j] and 
          name2 ="" and // skip this if found 2nd sec.name 
          nameList[i] <> secNames[j] and //never pick main 
          name1 <> secNames[j] // name is not used already 
          {                 
            name2=secNames[j])
            secNames[j]="" // remove choice for next pass
          }
    }
    if (name1="" or name2="")
    {
       //input does not allow for solution
       throw("Problem cannot be solved!!!") 
    }
    //assembly result
    resultList[i]=nameList[i]+name1+","+name2 

}

Basically from the list of name we create a second list where all the names are duplicated (but second copy is in reversed order). We scan that list for first and second choices, and every time we pick a name we remove it from the list of secondary names. Your example should return:

John - Rose,Dave
Rose - John,Jade
Dave - Jade,Rose
Jade - Dave,John

Note that this is not really "random" - it will always return the same list when invoked with the same input, but it will also always try to satisfy your requirements.