PHP | How to make a random names list without repeat

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?