手で同じ種類を見つけるためのアルゴリズム

Question

これは実際にはマジョンベースの質問ですが、ロムまたはポーカーベースの背景でさえ理解するのにも簡単に十分です。

Mahjongでは、14タイル（タイルはポーカーのカードのようなものです）は、4セットとペアに配置されています。通り（ "123"）は常に正確に3つのタイルを使用しますが、それ以上ではなく、それ以上ではありません。同じ種類（ "111"）のセットも、正確に3つのタイルで構成されています。これにより、3 * 4 + 2 = 14タイルの合計につながります。

カンや13の孤児のようなさまざまな例外がありますが、ここでは関連していません。色と値の範囲（1-9）もアルゴリズムにとって重要ではありません。

上記の方法で手を配置できるかどうかを判断しようとしています。特定の理由により、14個だけでなく、任意の数のタイルに対処できるはずです。 （次のステップは、手を整えることができるように交換する必要があるタイルの数を見つけることです。）

例：

11122233344455 - 簡単に、4セットとペア。
12345555678999 - 123, 456, 789, 555, 99
11223378888999 - 123, 123, 789, 888, 99
11223344556789 - 有効な手ではありません

私の現在の実装されていないアイデアはこれです。各タイルについて、a）a）at street b）a set c）a pairを作るようにしてください。機能しない場合（または1ペアを超えるペアがあります）、前の反復に戻り、次のオプションを試してください。これが最高レベルの場合は失敗します。それ以外の場合、残りのタイルのリストから使用したタイルを削除し、次の反復を続けます。

このアプローチは機能し、かなり速いと思います（パフォーマンスは「素晴らしいボーナス」です）が、これについてのあなたの意見に興味があります。代替ソリューションを考えられますか？これか似たようなものはすでに存在していますか？

（宿題ではない、 私はマジョンを演じることを学んでいます。)

Answer 1

通りとセット内の値の合計は、3で分割できます。

• n + n + n = 3n
• （n-1） + n +（n + 1）= 3n

したがって、解決された手ですべての数字を一緒に追加すると、3n + 2mのフォームがいくつか取得され、mはペアのタイルの値です。部門の残りの部分（total % 3）は、mの各値に対して：

total % 3 = 0  -> M = {3,6,9}
total % 3 = 1  -> M = {2,5,8}
total % 3 = 2  -> M = {1,4,7}

したがって、9つの可能なペアをテストする代わりに、単純な追加に基づいて3つを試す必要があります。可能なペアごとに、その値で2つのタイルを削除し、アルゴリズムの次のステップに進み、可能かどうかを判断します。

これを手に入れたら、最低値から始めます。その値の3つ未満のタイルがある場合、それはそれらが必ずしも通りの最初の要素であることを意味するので、その通りを取り除きます（タイルn+1またはn+2が欠落しているためにできない場合、それは手を意味します有効ではありません）そして、次の低い値に進みます。

最低値の少なくとも3つのタイルがある場合は、セットとしてそれらを削除します（「もしそれらが通りの一部だったら？」と尋ねると、彼らがそうであれば、3つのタイルn+1と3つのタイルもあると考えてください。タイルn+2の。これもセットに変換できます）。

空の手に届くと、手は有効です。

たとえば、無効な手の場合、合計は60です。つまり、m = {3,6,9}を意味します。

Remove the 3: 112244556789
 - Start with 1: there are less than three, so remove a street
   -> impossible: 123 needs a 3

Remove the 6: impossible, there is only one

Remove the 9: impossible, there is only one

2番目の例で 12345555678999, 、合計は78です。つまり、m = {3,6,9}を意味します。

Remove the 3: impossible, there is only one

Remove the 6: impossible, there is only one

Remove the 9: 123455556789
 - Start with 1: there is only one, so remove a street
   -> 455556789
 - Start with 4: there is only one, so remove a street
   -> 555789
 - Start with 5: there are three, so remove a set
   -> 789
 - Start with 7: there is only one, so remove a street
   -> empty : hand is valid, removals were [99] [123] [456] [555] [789]

3番目の例112233788888999にも合計78があり、バックトラッキングが発生します。

Remove the 3: 11227888899
 - Start with 1: there are less than three, so remove a street
   -> impossible: 123 needs a 3

Remove the 6: impossible, there are none

Remove the 9: 112233788889
 - Start with 1: there are less than three, so remove streets
   -> 788889
 - Start with 7: there is only one, so remove a street
   -> 888
 - Start with 8: there are three, so remove a set
   -> empty, hand is valid, removals were : [99] [123] [123] [789] [888]

Answer 2

あなたがそれを正しくするために何らかの仕事をする必要があるという特別なケースがあります。これは、同じ値（ただし異なるスーツ）を持つ3回とペアがある場合に発生します。

Bに竹を否定し、Cはキャラクターを寄付し、Dはドットを寄付し、この手を試してみてください。

b2,b3,b4,b5,b6,b7,c4,c4,c4,d4,d4,d6,d7,d8

d4,d4 should serve as the pair, and c4,c4,c4 should serve as the run-of-3 set.

しかし、3 "C4"タイルが2 d4 tilessの前に表示されるため、最初の2つのC4タイルがペアとしてピックアップされ、Orphan C4と2 D4Sが残り、これらの3つのタイルは有効なセットを形成しません。

この場合、2つのC4タイルを手に戻す（そして手を整理したまま）し、基準を満たす次のタイルを検索する必要があります（値== 4）。そのためには、C4を試したことを「覚えておいてください」とする必要があります。次の反復では、C4をスキップし、値== 4の他のタイルを探す必要があります。コードは少し乱雑ですが、実行可能です。

Answer 3

私はそれを2つのステップに分解します。

1. 可能な組み合わせを把握します。これらの数字では、徹底的なチェックが実行可能であると思います。このステップの結果は、各組み合わせにタイプ（セット、ストリート、またはペア）があり、使用したカード（ビットマップ）があるパターンがある組み合わせのリストです。
2. 以前の情報を使用して、組み合わせの可能なコレクションを決定します。これは、ビットマップが役立つ場所です。ビットワイズ演算子を使用すると、異なるコンビネーターの同じタイルの使用の重複がわかります。

また、各タイプが十分であるかどうかを確認するためにチェックするだけのステップ1.5を実行することもできます。このステップとステップ2は、一般的なアルゴリズムを作成できる場合になります。最初のステップは、すべての数のタイルと可能な組み合わせで迅速に同じになります。