Coincidencia circular. PHP/MySql

Question

Hola, necesito ayuda con la siguiente situación en php. Tengo una base de datos con usuarios que cada usuario tiene una ID, tarjeta_de_mesa y tarjeta_bus. Sé cómo hacer una coincidencia directa (un usuario comercia con otro usuario). Pero si no hay ninguna coincidencia directa, pero hay un intercambio circular como:

Usuario # 1 tiene la tarjeta A quiere tarjeta B

Usuario # 2 tiene la tarjeta B quiere tarjeta C

Usuario # 3 tiene la tarjeta C quiere la tarjeta A

En este escenario, no hay una coincidencia directa entre dos usuarios. Pero si:

Usuario # 1 da su tarjeta al usuario # 3

Usuario # 3 da su tarjeta al usuario # 2

Usuario # 2 entrega su tarjeta al usuario # 1

Cada unos felices.

Toda la información que tengo para comenzar es Usuario # 1 ¿Cómo puedo encontrar al Usuario # 2 y Usuario # 3?

Gracias a todos por sus respuestas.

Answer 1

Este es un escenario desafiante. Tuve que construir esto para una aplicación de intercambio de libros hace un tiempo y con una pizarra pude visualizar el problema con mayor facilidad.

Lo que hice fue utilizar la misma tabla dentro de la consulta varias veces, simplemente usando un nombre diferente.

En mi situación, los libros que se necesitaban estaban en una tabla separada de los libros que tenían los usuarios. Esperamos que usted será capaz de ver la lógica en esta consulta:

$query = "SELECT 
     A.Owner_ID as Owner_1, C.Owner_ID as Owner_2, E.Owner_ID as Owner_3 
    FROM 
     E_User_Books_Have as A, E_User_Books_Have as C, E_User_Books_Have as E, 
     E_User_Books_Needed as B, E_User_Books_Needed as D,E_User_Books_Needed as F 

    WHERE 
     A.Book_ID=D.Book_ID AND 
     C.Book_ID=F.Book_ID AND 
     E.Book_ID=B.Book_ID AND 
     A.Owner_ID='$ME' AND B.Owner_ID='$ME' AND A.ID='$ID'AND 
     C.Owner_ID=D.Owner_ID AND 
     E.Owner_ID=F.Owner_ID AND 
     C.Owner_ID!='$ME' AND 
     E.Owner_ID!='$ME'"; 

Answer 2

Esta es la forma en que lo haría: Crear un algoritmo recursivo de esta manera:

1 tome un usuario, ver lo que quiere

2 encontrar otro usuario que tenga lo que el usuario se quiere

- if user two wants, what user one has, everything is fine an we're done 
- if not, continue 

3 encontrar otro usuario que tenga lo que el usuario quiere dos

- if user three wants, what user one has, everything is fine and we're done 
- if not, continue ... 

... y así sucesivamente, pero debe tener un límite para los niveles recursivos para evitar la búsqueda sin fin.

Answer 3

Tal vez esto:

Encontrar posibles primeros partidos (usuarios que tienen la tarjeta de usuario # 1 Desea)

select name from user where has in (select wants from user where name = '1'); 

iterar a través de los partidos y tratar de encontrar el eslabón perdido:

select name from user where name in (select name from user where has in (select wants from user where name = <match>)); 

Answer 4

Curiosamente, me encontré con una cosa similar a esto con la BoardGameGeek Maths Trade.Básicamente, todo el mundo especifica que o quieren un juego o tienen un juego y el algoritmo maximiza los intercambios, incluidas las dependencias circulares.

Esto es exactamente lo que quiere.

Aquí hay un explanation of how TradeMaximizer works. Utiliza Dijkstra's algorithm y skew heaps para encontrar soluciones de coincidencia mínima (es decir, un círculo más pequeño es preferible a un círculo más grande).

Concedido esto se crea en Java pero los algoritmos son universales y puede volver a crearlos según sea necesario, especialmente una vez que comprenda lo que está haciendo y por qué.