カードを交換するための可能な方法のすべてを見つける

Question

私はカードを交換するためのすべての可能な方法を見つけるPHPアプリケーションに取り組んでいます。各ユーザーには少なくとも1枚のカードがあります。ユーザがカードを要求すると、アプリケーションは、彼が要求したカードのために彼のカードを交換するためのすべての可能な方法を彼に示します。

それを言うことができます：

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 

しかし、どのような場合他に2人のユーザーがいた：

ユーザー1を要求カードCは、1以外の一つの他の解決策がある場合

今、それを超えるものである：

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

ユーザーが持っているか、要求できるか多くのカードの面で制限はなくなります

。今までは、2つのSQLテーブルを作成しました。テーブル「カード」は、各ユーザIDとカードIDを追跡します。テーブル「要求」は、各ユーザIDおよび所望のカードIDを追跡する。

Answer 1

私はこのために純粋な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"; 
    } 
} 

Answer 2

あなたは有向グラフに問題があることを表すことができますし、私はこのような何かを実行します。ユーザはグラフの頂点であり、エッジはユーザXがユーザYが望むカードを有するという事実を表す。彼らはあなたが望むカードを持っているユーザーを表す必要はありません。

問題の解決策は、すべての頂点が正確に1つの出力エッジと1つの入力エッジしか持たないようにするエッジのセットです。

EDIT

私は、ユーザーが複数のカードを持っている可能性があるという事実を見逃していました。彼はまた、いくつかのカードが必要かもしれないと思います。その場合、私はすべてのユーザを頂点として表現し、すべてのユーザをXはYがの辺を持つカードを必要とします（XがYの場合でも同様です）。彼らが望むカードであり、同じカードを複数回使用することはできません。

私は、各カードに番号を割り当て、各ユーザーが召集に持っていた各番号のカード数と、同じ数のユーザーが持つ出力辺の数を追跡することで確認します。

Answer 3

ユーザがコンビネーションを行う方法を数えるために "持っている"タイプを決して "望んでいない"場合、アルゴリズムは必要ありません。あなたは「ショー」にしたい場合の方法はスワッピングが、その後場所、とり：問題を可視化するために

を、次のようにタイプを手配：

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

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


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

だから私たちの例では、ユーザー1は、2個のタイプAを持っていますユーザ2は1を有し、ユーザ3,4および5はそれぞれ1つのタイプAカードを必要とする。

タイプAカードのこの瞬間を考えてみましょう。

あなたは、このようなシーケンシャル一つとして、カードを交換するための対を形成する必要があります。

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

、すべてのユーザーが満足される場合は、askersと同じ所有者が存在します。

ここで、ペアを作成するには、各セットの1つの要素を再配置せずに選択する必要があることがわかります。繰り返しがあるかもしれないので（ユーザーがタイプのカードを複数必要としているか、または複数持っている）、それについても考慮する必要があります。これは、各タイプを処理する方法を数えるためのものです。コンビナトリアルで十分です。

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の可能な結果セットを持っています。すべてのカードを交換するためのすべての可能な方法を得るためには、それぞれのタイプのすべての可能な方法を組み合わせなければなりません...