Найти все возможные способы обмена картами

Question

Я работаю над приложением PHP, которое находит все возможные способы обмена картами.У каждого пользователя есть хотя бы одна карточка.Когда пользователь запрашивает карту, приложение показывает ему все возможные способы поменять его карту в обмен на запрошенную карту.

Допустим, что:

user 1 has card type A
user 2 has card type B 
user 3 has card type C 

И давайте предположим, что:

user 1 wants card type C
user 2 wants card type A
user 3 wants card type B

Если пользователь 1 запрашивает карту C, единственное решение заключается в следующем:

user 1 gives user 2 his card
user 2 gives user 3 his card
user 3 gives user 1 his card

Но что, если бы было два других пользователя:

user 4 has card type B & wants card type A
user 5 has card type C & wants card type B

Теперь, если пользователь 1 запрашивает карточку C, есть еще одно решение, помимо приведенного выше, которое состоит в следующем:

user 1 gives user 4 his card
user 4 gives user 5 his card
user 5 gives user 1 his card

Не будет никакого ограничения в отношении количества карточек, которые пользователь может иметь или запросить.До сих пор я создал две таблицы SQL.Таблица «Карты» отслеживает каждый идентификатор пользователя и идентификатор карты.Таблица «Запросы» отслеживает каждый идентификатор пользователя и требуемый идентификатор карты.

Answer 1

Вы можете представить проблему с ориентированным графом.Пользователи будут вершинами графа, а ребро представляет тот факт, что у пользователя X есть карта, которую хочет пользователь Y.Вам не нужно представлять пользователей, у которых, как оказалось, есть карта, которую они хотят.

Решением проблемы может быть набор ребер, который гарантирует, что каждая вершина имеет ровно один выходной ребро и только одинкрай ввода.

РЕДАКТИРОВАТЬ

Я пропустил тот факт, что пользователь может иметь более одной карты.Я полагаю, ему также может понадобиться несколько карт.В этом случае я бы представлял каждого пользователя как вершину, и каждому X нужна карта, у которой Y * в качестве ребра, даже когда X равно Y. Тогда решением проблемы будет множество ребер, которыепозволяет каждому иметь нужные ему карты, и не позволяет никому пользователю давать одну и ту же карту более одного раза.

Я бы проверял это, назначая каждой карточке номер и отслеживая, сколько карточек каждойчисло, которое каждый пользователь имел в начале, и сколько выходных ребер у пользователя с тем же номером.

Answer 2

Если пользователь никогда не «хочет» тип, который он «имеет» для подсчета способа, которым это может быть сделано, достаточно комбинаторики, никакой алгоритм не требуется.Если вы хотите «показать», как происходит обмен, то:

Для визуализации проблемы расположите типы следующим образом:

        TYPE A       ...........................     TYPE N

    |          |                                   |          |   
    |          |                                   |          | 
    | USER 2   |                                   |          | 
    | USER 1   |                                   |          | 
    | USER 1   |                                   +..........+
    +----------+                              
        HAS


       WANTS
    +----------+ 
    | USER 3   |
    | USER 4   |
    | USER 5   |
    |          |                

В нашем примере Пользователь 1имеет две карты типа А, у пользователя 2 есть одна, а пользователям 3,4 и 5 требуется по одной карте типа А.

Давайте подумаем в данный момент только о картах типа А.

Вам необходимо сформировать пары для обмена карточек, например, последовательную:

 {{usr 1,usr3},{usr1, usr 4}, {usr2,usr5}}

Если каждый пользователь будет удовлетворен, у него будут те же владельцы, что и у спрашивающих.

Теперь, для формирования пар вы знаете, что вы должны выбрать один элемент каждого набора без репозиции.Поскольку могут быть повторения (пользователи хотят или имеют более одной карты одного типа), вы также должны учитывать это.Это для подсчета способов «обработки» каждого типа.И комбинаторики достаточно.

Для формирования пар вы можете:

1) Построить все различные перестановки из каждого набора:

    {2, 1, 1}  {1, 2, 1}  {1, 1, 2}  # == 3!/2!
    {3, 4, 5}  {5, 3, 4}  {4, 5, 3} {4, 3, 5} {5, 4, 3} {3, 5, 4} # == 3!

2) Для каждой пары перестановок у вас есть различный результатустановите 3 х 6 = 18 в нашем примере.....

Сделайте то же самое для всех типов карт ...

И, наконец, у вас есть N возможных наборов результатов для каждого типа карт.Чтобы получить ВСЕ возможные способы обмена всех карт, вам необходимо объединить все возможные способы для каждого типа ...

Answer 3

Я бы не использовал чистый PHP для этого.Скорее я бы создал таблицу MySQL, в которой хранится запись для каждого пользователя, в которой записывается, какая карта у этого пользователя, а также какая карта ему нужна.Затем я бы запустил что-то вроде этого:

$sql = "SELECT * FROM users";
$result = $this->db->query();
$users = $result->getAll(); //A list of all the users.

foreach ($users as $user)
{
   $sql = "SELECT * FROM users WHERE cardId = '$user->wantedCardId'";
   $result = $this->db->query($sql);

   if (! $result->has_rows())
   {
      echo "No other users with $user->wantedCardId were found.";
      continue;
   }

   $cardHolder = $result->row();
   echo: "User $cardHolder->id gives $user->id his card";
}

Если бы я делал это с помощью простого PHP, я бы сделал что-то вроде этого:

//Populate an array containing a list of all the users and their cards.

$users = array();

$user[1] = new StdClass();;
$user[1]->cardId = 2;
$user[1]->wantedId = 3;

$user[2] = new StdClass();
$user[2]->cardId = 3;
$user[2]->wantedId = 2;
// .....

foreach ($users as $userId=>$user)
{
   //Run a secondary loop through the users to find those that have the card that
   //this user wants.
   foreach ($users as $holderId=>$cardHolder)
   {
      if ($cardHolder->cardId != $user->wantedId)
         continue;
      echo "User $holderId gives $userId his card";
   }
}