Wierd solution needed! PHP


#1

i have a while loop that returns for example persons ID 1, 2, 3 and 4 (can be even more)
i need them to assign in pairs randomly:

1 >> 2 line ok
2 >> 3 line ok
3 >> 4 line ok
4 >> 1 line ok

And to not be with the same id in pair again:

1 >> 2 line ok
2 >> 1 line not ok as pair repeats
3 >> 4 line ok
4 >> 3 line not ok as pair repeats

I hope i explained it well :confused:

Can anyone help me here?


#3

Short Answer: Shuffle the array. Duplicate it. Rotate the copy one position.

Long answer:
For any given values X and Y, a given valid index i, $a (the original array) and $b (the duplicate singularly-rotated array), if $a[i] = X, $b[i+1 % length($b)] = X.
To fail the repeat-pair test, $b[i] = Y and $a[i+1 % length($b)] = Y;
In a unique array, if $a[i+1 % length($b)] = Y, then $b[i+2 % length($b)] = Y by definition, and consequently $b[i] != Y by uniqueness.
If b[i] = Y, then $a[i-1] = Y by definition, and consequently $a[i+1 % length($b)] != Y by uniqueness.
Therefore it is impossible for Y to be in these positions with a fixed rotation of $b, if the length of the array is greater than 2. (If the array is equal to or less than length 2, it is impossible to generate such a list.)


#4

take an array of all unique IDs, shuffle them, then you have the new order.


#5

Is hard to understand what you mean :frowning:


#6

Hey, i tried this:

		$a = Array (12, 2, 13);
		$b = Array (12, 2, 13);

		print_r($a); echo '<br>';
		shuffle($b);


		$r=null;
		foreach($a as $aa)
		{
			
			foreach($b AS $bb){
				
				if($aa!=$bb){
					echo '<b>'.$aa.' '.$bb.'</b><br>';
				}
			
			}
		
		}

But its wrong and make it double :frowning:


#7

Then use the short answer and take it for granted that i have a mathematical explanation.

chorn’s answer is roughly the same, but uses one array and says “The paired value to $a[i] is $a[i+1 % count($a)]”


#8

I does not seems i m going there :frowning:


#9

Can you explain that? What should that mean. People only can help you if you say on which part you are struggeling. The way i think about this: you do not need two arrays. The data you want to have is arranged in a RING, the right value of your list is always the next value in the ring, so basically $i+1.

(plus the edge case when you get to the “end”, @m_hutley already posted a fix as PHP code)


#10

@m_hutley @chorn i think i managed to do it! But i just want to know if what i done is correct:

	$a = Array (12, 2, 13, 7);
	shuffle($a);

	$b = $a;
	array_push($b, array_shift($b));

	$length = count($a);
	for($i = 0; $i <= $length; ++$i) {
		
		echo $a[$i].' '.$b[$i].'<br>';

	}

#11

That would be a correct implementation of the two-array method.
The one-array method would be:

$a = Array (12, 2, 13, 7);
shuffle($a);
foreach($a AS $i => $x) {
  echo $x." ".$a[(($i+1) % count($a))]; //The outer parentheses are probably redundant.
}

It really just depends on your use case as to which you want to use.


#12

Yeah this one looks giving same result and code is shorter :slight_smile: Thanks man!


#13

Hey, my issue going further. … Now i added groups for users:

$user_group = Array
(
    //[user id] => user group 
    [12] => a
    [2] => b
    [13] => b
    [14] => a
    [15] => b
)

$participants = Array
(
    [0] => 12
    [1] => 2
    [2] => 13
    [3] => 14
    [4] => 15
)
	$a = $participants;
	shuffle($a);

	foreach($a AS $i => $x) {
	  echo $x." (".$user_group[$x].") ".$a[(($i+1) % count($a))]." (".$user_group[$a[(($i+1) % count($a))]].")<br>"; //The outer parentheses are probably redundant.
	}

Here i need that user group for users does not match (only if there is no more chance there can be same user group)

Bad Output:
14 (a) 13 (b)
13 (b) 15 (b) //BAD
15 (b) 2 (b) //BAD
2 (b) 12 (a)
12 (a) 14 (a)

Good Output:
13 (b) 15 (b)
15 (b) 12 (a)
12 (a) 2 (b)
2 (b) 14 (a)
14 (a) 13 (b)

How to achieve such a scenario?


#14

So lets do some Maths. Because Maths is fun and helps us think things through.

We have two groups, A and B. We’re trying to match things such that:

  1. Everyone gets matched
  2. Noone gets matched to someone in the same group if possible, and
  3. Noone gets matched in a 2-chain.

Well, the first one’s pretty easy: As long as there’s more than two people in the list, we’re going to be able to match everyone.

The second one is pretty easy too, it just requires a little bit of thinking. How can I guarantee that there will be enough people in A to match with B?

You can try drawing groups A and B standing in a line, and then draw arrows between them to see how this works.

The simple answer is: If the number of people in group A equals the number of people in group B, we can do this with no problem.
If they don’t match up, how many people get matched with a member of their own group? Well, the answer to that is equal to the difference between the groups. You’ve already proven that with your example output: We have 3 “B”'s, and 2 “A”'s, so there’s a difference of 1, and there’s 1 person who has a pairing with their own group. Try it with 5 "B"s and 2 "A"s, and check my statement.

The third condition can be handled roughly the same way as before; by ensuring everyone ends up in a single, looping, chain. As long as your group has more than 2 members, this chain will have a length greater than 2.

How do we do this? Well, there’s a couple of different ways. I’m going to come up with a couple, but i’m sure others can and will do better.

First, if you want to shuffle the array, shuffle them. Separate your group members into separate arrays. A and B.

Option 1: Remerging
Interleave your arrays, so that the combined array goes ABABAB… until you get to the end. (If the arrays arnt the same length, then you’ll end up with an ending that looks like BA, AA or BB).
As in the single-array structure before, each person is matched with the person after them, with the last person in the array looping back around.

Option 2: Bouncing
As before, we have two arrays, A and B. This time, bounce back and forth between the arrays, so that $a[0] matches to $b[0], $b[0] matches to $a[1], $a[1] matches to $b[1], $b[1] matches to $a[2], etc. This gets a little more tricky to do than Option 1, because you have to keep track of when you get to the end of one of the arrays, and instead match to their own array. The final person, which will either be $a[n] or $b[m], matches to $a[0], completing the chain.