Acceder a pares de valores únicos desde una matriz sin repetirme

Estoy tratando de acceder a pares de valores únicos desde una matriz en orden aleatorio, sin repetirme hasta que sea necesario.

Por ejemplo, si tengo un conjunto de conjuntos A, B, C, D (en general, un número par de elementos, pero hasta 20), entonces la primera vez podría emparejar AB & CD. Pero quiero garantizar que la próxima vez que lo haga, evite repetir mi emparejamiento y que obtenga tanto AC & BD como AD y BC antes de que vuelva a obtener AB y CD. Cada artículo solo debe ser llamado una vez en cada ronda.

Empecé mezclando aleatoriamente el orden de la matriz y luego combinando dos valores, pero necesito una forma de evitar que aparezcan algunas parejas más frecuentemente que otras (lo ideal sería que boostan de la misma manera).

Así que me he movido a buscar permutaciones, y he logrado obtener una matriz completa que contiene todas las combinaciones posibles utilizando el siguiente código:

$this->items = array('A','B','C','D'); $input = $this->items; $input_copy = $input; $output = array(); $i = 0; foreach($input as $val) { $j = 0; foreach($input_copy as $cval) { if($j == $i) break; print $val.'-'.$cval.'
'; //$output[] = array($val => $cval); $j++; } $i++; } //print_r($output);

por ejemplo, para A, B, C, DI obtener:

 ba ca cb da db dc 

Quiero recorrer el conjunto n-1 veces y capturar los resultados en otra matriz, pero no estoy seguro de cómo generar el orden real a partir de estas opciones únicas

En otras palabras, quiero pasar la lista de arriba a la siguiente:

 1st run => 1=> AB, 2=> CD, 2nd run => 1=> AC, 2=> BD, 3rd run => 1=> AD, 2=> CB, 

Puede ser que pueda hacer esto más simplemente desde $ this-> items. También he echado un vistazo al paquete Math_Combinatorics PEAR, pero no estaba seguro de por dónde empezar.

¡Estaría agradecido por cualquier ayuda!

Puede usar el algoritmo de torneo round-robin

 Place elements in two rows. Fix one element - in this case A For next round shift all other elements in circular manner. Pair them. Repeat N-1 times AB DC ----- AD CB ---- AC BD ---- 

Supongo que quieres generar cada emparejamiento exactamente una vez, es decir, cada partición de tu secuencia completa en pares. Si solo quiere cada par exactamente una vez, ese es un problema diferente manejado en una respuesta diferente.

Piensa en este problema recursivamente: al principio tienes n elementos. A partir de estos, tome el primero y elija un socio para él de los elementos n- 1 restantes. Quite este par de la lista y recuse con los elementos n -2 restantes. Si haces que cada elección sea imparcial, el emparejamiento restante también será imparcial. Pero eso no garantiza que no se repita antes de lo necesario.

Si realmente quiere estar seguro de evitar repeticiones de emparejamientos, primero debe pensar en la cantidad de parejas posibles que existen. Por ahora supondré que n es par, por lo que solo tienes pares completos. Es fácil ajustar esto a n impar con un elemento no apareado. Para obtener el número total de emparejamientos posibles, debe multiplicar sus elecciones:

 m=(n-1)*(n-3)*(n-5)*...*7*5*3*1 

Entonces es un producto de números impares. Eso es A001147 , también escrito como un doble factorial m = ( n -1) !! Tenga en cuenta que estos números crecen con bastante rapidez, por lo que incluso para n moderados (como n = 16) no tendrá que preocuparse por repetirse simplemente porque hay tantas parejas posibles para elegir que una repetición es bastante improbable.

Si realmente quiere estar seguro de evitar repeticiones, puede simplemente generar toda la lista y mezclarla. Pero como acabo de indicar, esa lista también podría ser enorme . Entonces, en su lugar, le sugiero que divida este problema en dos pasos. Encuentre una forma de generar todos los números de 0 a m -1 cada uno exactamente una vez, y encuentre la manera de convertir dichos números en emparejamientos. Para este último, simplemente puede descomponer su número paso a paso. En cada paso, tome el index % (n-1) para hacer la elección actual, y elija (int)(index / (n-1)) como el índice para las elecciones posteriores en las llamadas recursivas.

Para el primero, lo más fácil que se me ocurre es usar un PRNG con un número primo p > m como su punto. Usar la aritmética modular, eso debería ser fácil de hacer. Entonces simplemente descarte todos los valores que sean mayores o iguales a m . Descartar significa saltar al próximo elemento de la secuencia. Esto dará todas las parejas en un orden que debería parecer bastante aleatorio. Si el punto de partida en esa secuencia debe ser aleatorio, asegúrese de que si al principio elige un valor que se va a descartar, entonces debe inicializar de nuevo, no saltearse al siguiente elemento. De lo contrario, algunos elementos serían más probables como puntos de partida que otros.