Finding all possible ways to swap cards

I am working on a PHP application that finds all possible ways to swap cards. each user has at least one card. When a user request a card, the application shows him all possible ways to swap his card in excange for the card that he requested.

Lets say that:

user 1 has card ty开发者_如何转开发pe A
user 2 has card type B 
user 3 has card type C 

And lets assume that:

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

If user 1 requests card C, the only solution is that:

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

But what if there were two other users:

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

Now, If user 1 requests card C, there is one other solution besides the one above which is that :

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

There will be NO limit in terms of how many cards a user may have or request. So far, I created two SQL tables. The table "cards" keeps track of each userID and cardID. The Table "requests" keeps track of each userID and the desired cardID.

I wouldn't use pure PHP for this. Rather I would create a MySQL table which stores a record for each user, recording which card that user has as well as which card he wants. Then, I would run something like this:

$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";
}

If I were to do this using plain PHP, I would do something like this:

//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";
   }
}

You can represent the problem with a directed graph. The users would be the vertexs of the graph, and an edge represents the fact that user X has the card that user Y wants. You don't need to represent the users who happen to have the card that they want.

A solution to the problem would be the set of edges that ensures that every vertex has exactly one output edge, and only one input edge.

EDIT

I had missed the fact that a user may have more than one card. I suppose he may also need several cards. In that case I would represent every user as a vertex, and every X needs a card that Y has as an edge, even when X equals Y. Then a solution to the problem would be the set of edges that makes everyone have the cards they want, and doesn't allow any user to give the same card more than once.

I would check that by assigning each card a number, and keeping track of how many cards of each number each user had at the begging, and how many output edges the user has with the same number.

If a User never "wants" a type he "has" for counting the way it can be done combinatorics is enough, no algorithm needed. If you want to "show" the ways the swapping takes place, then :

For visualizing the problem, arrange the types in the following way:

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

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


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

So in our example User 1 has two Type A cards, user 2 has one, and users 3,4 and 5 wants one type A card each.

Let's think at this moment of just Type A cards.

You need to form pairs for exchanging cards such as the sequential one:

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

If every user will be satisfied, there will be same owners than askers.

Now, for forming pairs you know you have to pick one element of each set without reposition. As there may be repetitions (users wants or has more than one card of a type), you have to account for that also. This is for counting the ways each type should be "processed". And combinatorics is enough.

For forming the pairs you may:

1) Construct all different permutations of each set:

    {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) For each pair of permutations you have a different result set 3 x 6 = 18 in our example. ....

Do the same for all card types ...

And finally you have N possible result sets for each card type. For getting ALL possible ways to exchange all the cards, you have to combine all possible ways for each type ...