The problem asks for the number of ways to choose eight disjoint 5-card poker straights from a standard 52-card deck, under the extra condition that none of the eight straights is a straight flush. The only admissible rank windows are the ten usual poker straights: \(A2345\), \(23456\), \(34567\), \(\dots\), \(TJQKA\).
A direct search through 40-card subsets would be hopeless. The successful strategy is to separate the problem into two layers. First decide how many of the eight straights use each of the ten rank windows. Then, for that fixed rank pattern, count suit assignments that keep all cards distinct and force every straight to use at least two suits. The implementations validate the model with the exact checks \(N_1=10200\) and \(N_2=31832952\).
The mathematics is a clean two-stage count: rank windows determine which ranks are demanded, and a compact dynamic program counts the legal suit histories.
Let \(C_0,\dots,C_9\) denote the ten straight windows, ordered as
\[ C_0=A2345,\quad C_1=23456,\quad C_2=34567,\quad \dots,\quad C_9=TJQKA. \]
Instead of selecting eight straights directly, we first choose a multiplicity vector
\[ p=(p_0,p_1,\dots,p_9),\qquad p_s\ge 0,\qquad \sum_{s=0}^{9} p_s=8. \]
Here \(p_s\) records how many of the eight straights use the window \(C_s\).
For each rank \(r\), define its occupancy by
\[ o_r=\sum_{s:\,r\in C_s} p_s. \]
At rank \(r\) the deck contains exactly four cards, one per suit, so any feasible collection must satisfy \(o_r\le 4\). This condition is also sufficient at the rank level: once the occupancies do not exceed four, the only remaining issue is how to assign distinct suits to the straight copies that need the same rank.
The implementations recursively enumerate exactly those vectors \(p\) with \(\sum p_s=8\) and \(o_r\le 4\) for all 13 ranks. For eight straights there are only \(1599\) feasible multiplicity patterns, so the outer search space is already very small.
Fix one feasible multiplicity vector. If a certain rank window occurs several times, those copies are temporarily labeled during the count. This is important because two straights with the same ranks can still evolve differently through their suit choices. The counting is therefore done on labeled copies first, and the artificial symmetry is removed only at the end.
Process the ranks in the order \(2,3,4,5,6,7,8,9,T,J,Q,K,A\). Suppose \(m\) labeled straights are active at some rank \(r\). Then those \(m\) cards must use \(m\) distinct suits, so the local choice is an ordered injection from the active straight labels into the four suits. The number of possibilities is
\[ P(4,m)=4\cdot 3\cdots (4-m+1)=\frac{4!}{(4-m)!},\qquad 0\le m\le 4. \]
Because the occupancy condition guarantees \(m\le 4\), this completely captures the card-distinctness restriction at a single rank.
For each unfinished straight, the full suit history is unnecessary. The future only depends on whether all cards seen so far are still in one common suit and, if so, which suit. That gives exactly five states:
\[ x\in\{0,1,2,3,F\}. \]
The states \(0,1,2,3\) mean "still monochromatic in that suit." The state \(F\) means "already mixed, so a straight flush has become impossible." If a new card of suit \(s\) is appended, the update rule is
\[ T(x,s)= \begin{cases} s, & \text{for the first card of the straight},\\ x, & \text{if }x\in\{0,1,2,3\}\text{ and }x=s,\\ F, & \text{otherwise}. \end{cases} \]
This is the crucial invariant: once two different suits have appeared, no later choices can ever turn the straight back into a straight flush.
The window \(A2345\) is the only non-consecutive pattern in the scan order \(2,\dots,A\). After rank \(5\) it disappears for several ranks and returns at rank \(A\). The dynamic program therefore keeps its five-state summary alive even while that straight is temporarily inactive. In other words, "inactive" does not mean "finished"; it only means that the current rank does not contribute a card to that straight.
After some rank has been processed, suppose the unfinished labeled straights have five-state values \(x_0,\dots,x_{k-1}\). Encode them as a base-5 integer
\[ z=\sum_{i=0}^{k-1} x_i 5^i. \]
A dynamic-programming table stores, for each code \(z\), the number of partial suit assignments that lead to it. At the next rank, every current state branches over all ordered suit injections for the active straights. Each active straight updates its state through \(T\). If that straight ends at the current rank, the branch is accepted only when the updated state is \(F\); ending in one of the four suit states would mean that all five cards share a suit, which is forbidden. The unfinished straights are then re-encoded into the next base-5 state.
Take one copy of \(A2345\) and one copy of \(23456\), with no other straights. Then
\[ o_2=o_3=o_4=o_5=2,\qquad o_6=o_A=1, \]
and every other occupancy is \(0\), so the pattern is feasible. At ranks \(2,3,4,5\) both labeled straights are active, which means each of those ranks contributes an ordered injection of two suits, hence \(P(4,2)=12\) local choices. At rank \(6\) the straight \(23456\) ends and must already be in state \(F\). Meanwhile the wheel straight is inactive from \(6\) through \(K\), but its state is carried unchanged through that gap. Finally the Ace is processed, and the wheel is accepted only if its updated state is also \(F\). This small example shows why the algorithm needs both injective suit assignments and a memory for dormant-but-unfinished straights.
If a window \(C_s\) occurs \(p_s\) times, then permuting those \(p_s\) identical copies does not change the final unordered collection of straights. Therefore every genuine solution has been counted
\[ \prod_{s=0}^{9} p_s! \]
times in the labeled dynamic program. Dividing by this factor converts the labeled count for the pattern \(p\) into the desired unlabeled count. As a quick check, one straight gives \(10(4^5-4)=10200\), because each of the ten windows has \(4^5\) suitings and exactly four of them are straight flushes.
The C++, Python, and Java implementations first generate all feasible multiplicity vectors \(p\). For each one, they build the temporarily labeled straight copies and record which ranks are active for each copy, where it first appears in the scan, and at which rank it finally ends. They also precompute the ordered suit injections for \(m=0,1,2,3,4\).
For every rank, the implementation knows which labeled straights are active now and which ones remain unfinished afterward. It iterates through the current base-5 states, tries every allowed ordered suit injection at that rank, updates the five-state summaries, rejects branches that would end as straight flushes, and adds the surviving counts to the next state table.
After the Ace has been processed, only the empty terminal state is valid. Its count is divided by \(\prod p_s!\) to undo the artificial labeling, and that value is added to the global answer. The C++ and Java implementations distribute the independent pattern counts across worker threads; the Python implementation uses worker processes when that is worthwhile and otherwise uses the same serial recurrence.
The outer loop visits only \(1599\) feasible patterns for eight straights. Within one pattern, at most eight labeled straights can be unfinished at the same time, so the encoded state space is bounded by
\[ 5^8=390625, \]
although the reachable portion is much smaller. At any rank, at most four straights can demand a card, so the local branching factor is at most
\[ P(4,4)=24. \]
Memory use is modest: the dynamic program only keeps the current and next state tables for one pattern, together with small metadata about the labeled straight copies. The decisive improvement is conceptual rather than asymptotic: the implementations never enumerate 40-card subsets of the deck, but instead count legal suit histories symbolically over a tiny family of feasible rank patterns.
Gesucht ist die Anzahl ungeordneter Familien von acht disjunkten 5-Karten-Straights aus einem Standarddeck mit 52 Karten, unter der Zusatzbedingung, dass keiner dieser acht Straights ein Straight Flush ist. Zulässig sind genau die zehn üblichen Rangfenster \(A2345\), \(23456\), \(34567\), \(\dots\), \(TJQKA\).
Eine direkte Durchmusterung aller 40-Karten-Auswahlen wäre völlig unpraktisch. Die Lösung trennt deshalb Rangstruktur und Suit-Struktur. Zuerst wird festgelegt, wie oft jedes der zehn Rangfenster vorkommt. Danach zählt eine dynamische Programmierung für dieses feste Rangmuster alle Suit-Belegungen, die Kartenkollisionen vermeiden und gleichzeitig sicherstellen, dass jeder Straight mindestens zwei verschiedene Suits enthält. Die Implementierungen prüfen das Modell unter anderem mit \(N_1=10200\) und \(N_2=31832952\).
Die Herleitung besteht aus zwei Ebenen: Zunächst werden nur die Rangfenster gezählt, anschließend werden die zulässigen Suit-Verläufe per DP bestimmt.
Bezeichne die zehn Straight-Fenster mit \(C_0,\dots,C_9\), in der Reihenfolge
\[ C_0=A2345,\quad C_1=23456,\quad C_2=34567,\quad \dots,\quad C_9=TJQKA. \]
Anstatt acht Straights direkt zu wählen, betrachtet man zunächst einen Vielfachheitsvektor
\[ p=(p_0,p_1,\dots,p_9),\qquad p_s\ge 0,\qquad \sum_{s=0}^{9} p_s=8. \]
Die Komponente \(p_s\) sagt, wie viele der acht Straights das Fenster \(C_s\) verwenden.
Für jeden Rang \(r\) definiert man die Belegung
\[ o_r=\sum_{s:\,r\in C_s} p_s. \]
Zu jedem Rang gibt es im Deck genau vier Karten, nämlich eine pro Suit. Daher ist \(o_r\le 4\) notwendig. Mehr noch: Auf Rangebene ist dies bereits hinreichend. Sobald diese Ungleichungen für alle 13 Ränge gelten, kann eine mögliche Kollision nur noch daher kommen, dass mehrere Straight-Kopien am selben Rang dieselbe Suit erhalten. Genau das erledigt später die Suit-Zählung.
Die Implementierungen erzeugen rekursiv genau die Vektoren \(p\) mit \(\sum p_s=8\) und \(o_r\le 4\) für alle Ränge. Für acht Straights bleiben nur \(1599\) zulässige Rangmuster übrig.
Ist ein Rangmuster fest gewählt, dann werden gleiche Straight-Kopien zunächst künstlich markiert. Das ist nötig, weil zwei Kopien desselben Rangfensters unterschiedliche Suit-Verläufe besitzen können. Gezählt werden also zuerst markierte Objekte; die dadurch eingeführte Symmetrie wird am Ende wieder herausdividiert.
Die Ränge werden in der Reihenfolge \(2,3,4,5,6,7,8,9,T,J,Q,K,A\) verarbeitet. Sind an einem Rang \(r\) gerade \(m\) markierte Straights aktiv, dann müssen diese \(m\) Karten verschiedene Suits erhalten. Die lokale Entscheidung ist daher eine geordnete Injektion der aktiven Straight-Labels in die vier Suits. Ihre Anzahl ist
\[ P(4,m)=4\cdot 3\cdots (4-m+1)=\frac{4!}{(4-m)!},\qquad 0\le m\le 4. \]
Wegen \(o_r\le 4\) kann kein größerer Wert von \(m\) auftreten.
Für einen noch nicht abgeschlossenen Straight muss man nicht die gesamte bisherige Suit-Folge kennen. Entscheidend ist nur, ob alle bisher gesehenen Karten noch denselben Suit tragen und falls ja, welchen. Das liefert genau fünf Zustände:
\[ x\in\{0,1,2,3,F\}. \]
Die Werte \(0,1,2,3\) bedeuten „bisher noch einfarbig in diesem Suit“, und \(F\) bedeutet „bereits gemischt, also kann kein Straight Flush mehr entstehen“. Fügt man eine neue Karte mit Suit \(s\) an, gilt
\[ T(x,s)= \begin{cases} s, & \text{bei der ersten Karte des Straights},\\ x, & \text{falls }x\in\{0,1,2,3\}\text{ und }x=s,\\ F, & \text{sonst}. \end{cases} \]
Damit ist die Zukunft vollständig beschrieben: Sobald zwei verschiedene Suits aufgetreten sind, kann dieser Straight nie wieder zu einem Straight Flush werden.
Das Fenster \(A2345\) ist im Scan \(2,\dots,A\) das einzige nicht zusammenhängende Muster. Nach der \(5\) verschwindet es für mehrere Ränge und taucht erst beim Ass wieder auf. Deshalb trägt die DP seinen Fünf-Zustands-Wert durch diese inaktiven Ränge unverändert weiter. „Inaktiv“ heißt hier also nicht „beendet“, sondern nur „am aktuellen Rang wird keine Karte verbraucht“.
Nach einem bearbeiteten Rang seien die Fünf-Zustands-Werte der noch offenen markierten Straights \(x_0,\dots,x_{k-1}\). Sie werden als Basis-5-Zahl codiert:
\[ z=\sum_{i=0}^{k-1} x_i 5^i. \]
Eine DP-Tabelle speichert für jeden Code \(z\), wie viele partielle Suit-Belegungen dorthin führen. Am nächsten Rang verzweigt jeder Zustand über alle geordneten Suit-Injektionen für die aktuell aktiven Straights. Jeder aktive Straight wird mit \(T\) aktualisiert. Endet ein Straight an diesem Rang, so ist der Übergang nur dann zulässig, wenn der neue Zustand \(F\) ist; einer der vier Suit-Zustände würde bedeuten, dass alle fünf Karten denselben Suit besitzen. Danach werden die weiterhin offenen Straights wieder als neuer Basis-5-Code zusammengesetzt.
Betrachte genau eine Kopie von \(A2345\) und eine Kopie von \(23456\), sonst nichts. Dann gilt
\[ o_2=o_3=o_4=o_5=2,\qquad o_6=o_A=1, \]
alle übrigen Belegungen sind \(0\), also ist das Muster zulässig. An den Rängen \(2,3,4,5\) sind beide markierten Straights aktiv, also hat jeder dieser Ränge \(P(4,2)=12\) lokale Suit-Zuordnungen. Beim Rang \(6\) endet \(23456\) und muss dann bereits im Zustand \(F\) sein. Das Wheel ist von \(6\) bis \(K\) inaktiv, sein Zustand wird aber unverändert mitgetragen. Erst beim Ass wird es abgeschlossen, wiederum nur dann gültig, wenn der aktualisierte Zustand \(F\) lautet. Das Beispiel zeigt zugleich die injektive Suit-Zuweisung und den Bedarf an einem Gedächtnis für ruhende, aber noch nicht beendete Straights.
Wenn ein Fenster \(C_s\) genau \(p_s\)-mal vorkommt, dann ändert eine Permutation dieser \(p_s\) identischen Kopien die endgültige ungeordnete Straight-Familie nicht. Jede echte Lösung wurde daher im markierten DP
\[ \prod_{s=0}^{9} p_s! \]
mal gezählt. Die Division durch diesen Faktor liefert aus dem markierten Musterbeitrag den gewünschten unmarkierten Beitrag. Als schneller Test ergibt ein einzelner Straight den Wert \(10(4^5-4)=10200\): zehn Rangfenster und pro Fenster genau vier verbotene Straight Flushes unter \(4^5\) Suitings.
Die C++-, Python- und Java-Implementierungen erzeugen zuerst alle zulässigen Vielfachheitsvektoren \(p\). Für jedes Muster werden die vorübergehend markierten Straight-Kopien aufgebaut und mit den dazugehörigen Informationen versehen: welche Ränge für diese Kopie aktiv sind, bei welchem Rang sie beginnt und bei welchem Rang sie endet. Zusätzlich werden alle geordneten Suit-Injektionen für \(m=0,1,2,3,4\) vorab bereitgestellt.
Für jeden Rang ist bekannt, welche markierten Straights aktuell eine Karte benötigen und welche nach diesem Rang noch nicht beendet sind. Die Implementierung durchläuft alle aktuellen Basis-5-Zustände, probiert jede zulässige Suit-Injektion, aktualisiert die Fünf-Zustands-Werte, verwirft Äste mit Straight Flush am Endrang und akkumuliert die übrigen Beiträge in der nächsten Zustandstabelle.
Nach dem Ass ist nur noch der leere Endzustand gültig. Dessen Anzahl wird durch \(\prod p_s!\) dividiert und zum Gesamtergebnis addiert. Die C++- und Java-Versionen verteilen diese voneinander unabhängigen Musterberechnungen auf mehrere Threads; die Python-Version benutzt bei Bedarf getrennte Worker-Prozesse und ansonsten dieselbe serielle Rekurrenz.
Die äußere Enumeration besucht nur \(1599\) zulässige Muster für acht Straights. Innerhalb eines Musters können höchstens acht markierte Straights gleichzeitig offen sein, daher ist der codierte Zustandsraum durch
\[ 5^8=390625 \]
beschränkt, wobei der tatsächlich erreichbare Teil deutlich kleiner ist. An einem Rang können höchstens vier Straights gleichzeitig eine Karte verlangen; die lokale Verzweigung ist also höchstens
\[ P(4,4)=24. \]
Der Speicherbedarf bleibt klein, weil immer nur die aktuelle und die nächste DP-Tabelle eines einzelnen Musters gehalten werden, plus wenig Metadaten über die markierten Straight-Kopien. Der entscheidende Gewinn besteht darin, dass nicht 40-Karten-Teilmengen explizit enumeriert werden, sondern symbolisch über eine sehr kleine Menge zulässiger Rangmuster gezählt wird.
İstenen şey, standart 52 kartlık desteden seçilen sekiz adet ayrık 5 kartlık poker straight ailesinin sayısını bulmaktır; ek koşul, bu sekiz straight'in hiçbirinin straight flush olmamasıdır. Kullanılabilecek rank pencereleri yalnızca klasik on straight'tir: \(A2345\), \(23456\), \(34567\), \(\dots\), \(TJQKA\).
40 kartlık altkümeleri doğrudan taramak pratik değildir. Çözüm bunun yerine problemi iki katmana ayırır. Önce sekiz straight'in bu on rank penceresini kaç kez kullandığını belirleriz. Sonra, bu sabit rank deseni için, tüm kartların farklı kalmasını sağlayan ve her straight'i en az iki suit kullanmaya zorlayan suit atamalarını sayarız. Uygulamalar bu modeli \(N_1=10200\) ve \(N_2=31832952\) kontrolleriyle doğrular.
Çözüm iki aşamalı bir sayımdır: rank pencereleri hangi rank'lerin talep edildiğini belirler, daha sonra sıkıştırılmış bir dinamik program bu talep için geçerli suit geçmişlerini sayar.
On straight penceresini \(C_0,\dots,C_9\) ile gösterelim:
\[ C_0=A2345,\quad C_1=23456,\quad C_2=34567,\quad \dots,\quad C_9=TJQKA. \]
Straight'leri doğrudan seçmek yerine önce şu çokluk vektörünü seçeriz:
\[ p=(p_0,p_1,\dots,p_9),\qquad p_s\ge 0,\qquad \sum_{s=0}^{9} p_s=8. \]
Burada \(p_s\), \(C_s\) penceresinin kaç kez kullanıldığını söyler.
Her rank \(r\) için doluluğu
\[ o_r=\sum_{s:\,r\in C_s} p_s \]
olarak tanımlayalım. Aynı rank'ta destede yalnızca dört fiziksel kart vardır, yani dört suit bulunur. Bu yüzden her geçerli çözümde \(o_r\le 4\) olmalıdır. Ayrıca rank düzeyinde başka bir engel de yoktur: bu eşitsizlikler sağlandıktan sonra geriye kalan tek sorun, aynı rank'ı isteyen straight kopyalarına farklı suit'ler vermektir.
Uygulamalar tam olarak \(\sum p_s=8\) ve tüm rank'ler için \(o_r\le 4\) koşullarını sağlayan vektörleri üretir. Sekiz straight için olası çokluk desenlerinin sayısı yalnızca \(1599\)'dur.
Sabit bir çokluk vektörü için, aynı rank penceresini kullanan straight kopyaları geçici olarak etiketlenir. Bunun nedeni, aynı rank kümesine sahip iki straight'in suit seçimleri yüzünden farklı biçimde ilerleyebilmesidir. Dolayısıyla önce etiketli nesneler sayılır, sonra bu yapay simetri düzeltilir.
Rank'leri \(2,3,4,5,6,7,8,9,T,J,Q,K,A\) sırasıyla işleyelim. Bir rank \(r\) üzerinde \(m\) etiketli straight aktifse, bu \(m\) kartın \(m\) farklı suit kullanması gerekir. O halde yerel seçim, aktif straight etiketlerinden dört suit'e yapılan sıralı bir enjeksiyondur. Seçenek sayısı
\[ P(4,m)=4\cdot 3\cdots (4-m+1)=\frac{4!}{(4-m)!},\qquad 0\le m\le 4 \]
olur. Zaten \(o_r\le 4\) olduğundan daha büyük bir \(m\) hiç oluşamaz.
Henüz bitmemiş bir straight için bütün suit geçmişini saklamaya gerek yoktur. Gelecek açısından önemli tek bilgi şudur: şimdiye kadar görülen kartların hepsi tek bir suit'te mi kaldı, kaldıysa hangisinde? Bu da tam olarak beş durum verir:
\[ x\in\{0,1,2,3,F\}. \]
\(0,1,2,3\) durumları "şimdilik tek suit'te, üstelik bu suit'te" anlamına gelir. \(F\) ise "artık karıştı; bundan sonra straight flush olması imkansız" demektir. Yeni gelen kartın suit'i \(s\) ise güncelleme
\[ T(x,s)= \begin{cases} s, & \text{straight'in ilk kartıysa},\\ x, & \text{eğer }x\in\{0,1,2,3\}\text{ ve }x=s,\\ F, & \text{aksi halde}. \end{cases} \]
Bu özet tamdır. Bir kez iki farklı suit görülmüşse, sonraki kartlar süreci yeniden straight flush durumuna geri döndüremez.
\(A2345\) penceresi, \(2,\dots,A\) tarama sırasına göre bakıldığında tek kopuk desendir. \(5\)'ten sonra birkaç rank boyunca görünmez, sonra As ile geri döner. Bu nedenle dinamik program onun beş durumlu bilgisini, straight o rank'lerde aktif olmasa bile taşımaya devam eder. Yani "aktif değil" demek "bitmiş" demek değildir.
Belli bir rank işlendiğinde, henüz tamamlanmamış etiketli straight'lerin durumları \(x_0,\dots,x_{k-1}\) olsun. Bunlar taban 5'te
\[ z=\sum_{i=0}^{k-1} x_i 5^i \]
şeklinde kodlanır. Dinamik program, her \(z\) kodu için kaç adet kısmi suit atamasının oraya ulaştığını tutar. Bir sonraki rank'te her mevcut durum, aktif straight'ler için mümkün olan bütün sıralı suit enjeksiyonları üzerinden dallanır. Her aktif straight, \(T\) kuralıyla güncellenir. Eğer straight bu rank'te bitiyorsa, yeni durumun mutlaka \(F\) olması gerekir; dört suit durumundan biriyle bitmek, beş kartın da aynı suit'te olduğu anlamına gelir ve straight flush oluşturur. Bitmemiş straight'ler yeniden taban-5 koduna yazılır.
Bir tane \(A2345\), bir tane de \(23456\) alalım; başka straight olmasın. O zaman
\[ o_2=o_3=o_4=o_5=2,\qquad o_6=o_A=1 \]
ve diğer tüm doluluklar \(0\) olur; yani desen geçerlidir. \(2,3,4,5\) rank'lerinde iki straight birden aktiftir; dolayısıyla bu rank'lerin her birinde \(P(4,2)=12\) yerel suit seçimi vardır. \(6\) rank'inde \(23456\) straight'i biter ve bu anda mutlaka \(F\) durumunda olmalıdır. Wheel straight ise \(6\) ile \(K\) arasında aktif değildir ama durumu aynen taşınır. En son As işlendiğinde wheel de ancak güncellenmiş durumu \(F\) ise kabul edilir. Bu küçük örnek, hem enjeksiyon şartını hem de arada uyuyan ama bitmemiş straight'ler için hafıza tutulmasının neden gerekli olduğunu açıkça gösterir.
Eğer \(C_s\) penceresi \(p_s\) kez kullanılıyorsa, bu \(p_s\) özdeş kopyanın kendi aralarında yer değiştirmesi son ayrık straight koleksiyonunu değiştirmez. Demek ki her gerçek çözüm, etiketli dinamik programda
\[ \prod_{s=0}^{9} p_s! \]
kez sayılmıştır. Bu faktöre bölmek, etiketli sayımı istenen etiketsiz sayıya çevirir. Hızlı bir kontrol olarak, tek straight için \(10(4^5-4)=10200\) elde edilir; çünkü on pencerenin her birinde \(4^5\) suit seçimi vardır ve bunların tam 4 tanesi straight flush'tır.
C++, Python ve Java uygulamaları önce bütün geçerli çokluk vektörlerini üretir. Sonra her desen için geçici olarak etiketlenmiş straight kopyalarını oluşturur; her kopya için hangi rank'lerde aktif olduğunu, taramada ilk ne zaman göründüğünü ve hangi rank'te sona erdiğini kaydeder. Ayrıca \(m=0,1,2,3,4\) için tüm sıralı suit enjeksiyonları önceden hazırlanır.
Her rank'te, uygulama hangi etiketli straight'lerin o anda kart istediğini ve hangilerinin sonraki adımda hâlâ bitmemiş olacağını bilir. Mevcut taban-5 durumları üzerinden geçer, her uygun suit enjeksiyonunu dener, beş-durum bilgisini günceller, straight flush ile bitecek dalları eler ve kalan sayıları bir sonraki durum tablosuna ekler.
As rank'i de işlendikten sonra geçerli tek terminal durum boş durumdur. Bu durumun sayısı \(\prod p_s!\) ile bölünerek desen katkısı elde edilir ve küresel toplama eklenir. C++ ve Java uygulamaları, birbirinden bağımsız desen sayımlarını iş parçacıklarına dağıtır. Python uygulaması ise uygun olduğunda ayrı süreçler kullanır; aksi halde aynı yinelemeyi seri olarak uygular.
Dış döngü sekiz straight için yalnızca \(1599\) geçerli deseni gezer. Tek bir desen içinde aynı anda en fazla sekiz etiketli straight açık kalabilir; bu yüzden kodlanmış durum uzayı
\[ 5^8=390625 \]
ile sınırlıdır, fakat erişilebilen durum sayısı bunun oldukça altındadır. Bir rank'te en fazla dört straight aynı anda kart isteyebilir; dolayısıyla yerel dallanma en çok
\[ P(4,4)=24 \]
olur. Bellek kullanımı da küçüktür; her desen için yalnızca mevcut ve sonraki durum tabloları ile küçük straight metaverileri tutulur. Asıl kazanç, 40 kartlık deste altkümelerini saymak yerine çok küçük bir fizibilite desenleri ailesi üzerinde sembolik sayım yapılmasıdır.
Se pide contar las familias no ordenadas de ocho escaleras de póquer disjuntas de 5 cartas tomadas de una baraja estándar de 52 cartas, con la restricción adicional de que ninguna de esas ocho escaleras sea una escalera de color. Los únicos intervalos de rangos permitidos son las diez escaleras habituales: \(A2345\), \(23456\), \(34567\), \(\dots\), \(TJQKA\).
Explorar directamente subconjuntos de 40 cartas sería inviable. La idea correcta es separar la estructura de rangos de la estructura de palos. Primero se fija cuántas de las ocho escaleras usan cada una de las diez ventanas de rangos. Después, para ese patrón fijo, se cuentan las asignaciones de palos que mantienen todas las cartas distintas y obligan a que cada escalera use al menos dos palos. Las implementaciones comprueban el modelo con \(N_1=10200\) y \(N_2=31832952\).
La solución tiene dos capas: una cuenta de patrones de rangos y una programación dinámica compacta para los historiales de palos.
Llamemos \(C_0,\dots,C_9\) a las diez ventanas de escalera:
\[ C_0=A2345,\quad C_1=23456,\quad C_2=34567,\quad \dots,\quad C_9=TJQKA. \]
En vez de elegir las ocho escaleras una por una, primero elegimos un vector de multiplicidades
\[ p=(p_0,p_1,\dots,p_9),\qquad p_s\ge 0,\qquad \sum_{s=0}^{9} p_s=8. \]
El valor \(p_s\) indica cuántas copias de la ventana \(C_s\) aparecen en la colección.
Para cada rango \(r\), definimos
\[ o_r=\sum_{s:\,r\in C_s} p_s. \]
Como en cada rango solo existen cuatro cartas físicas, una por palo, toda solución válida debe cumplir \(o_r\le 4\). Y en realidad no hace falta nada más en la capa de rangos: una vez satisfechas esas desigualdades, el único problema restante es repartir palos distintos entre las copias de escalera que comparten ese rango.
Las implementaciones generan recursivamente exactamente los vectores \(p\) con \(\sum p_s=8\) y \(o_r\le 4\) para los 13 rangos. Para ocho escaleras solo sobreviven \(1599\) patrones viables.
Fijado un patrón viable, las copias idénticas de una misma ventana se etiquetan de manera temporal. Esto es necesario porque dos escaleras con los mismos rangos pueden seguir historiales de palos distintos. Por tanto, primero se cuentan configuraciones etiquetadas y al final se corrige la simetría introducida por esas etiquetas.
Se recorren los rangos en el orden \(2,3,4,5,6,7,8,9,T,J,Q,K,A\). Si en un rango \(r\) hay \(m\) escaleras etiquetadas activas, esas \(m\) cartas deben usar \(m\) palos distintos. Por tanto, la decisión local es una inyección ordenada desde las etiquetas activas hacia los cuatro palos. El número de posibilidades es
\[ P(4,m)=4\cdot 3\cdots (4-m+1)=\frac{4!}{(4-m)!},\qquad 0\le m\le 4. \]
La condición \(o_r\le 4\) garantiza que nunca aparece un valor mayor.
Para una escalera aún no terminada, no hace falta recordar todo su historial de palos. Solo importa si todas las cartas vistas hasta ahora siguen en un mismo palo y, en caso afirmativo, cuál. Eso produce exactamente cinco estados:
\[ x\in\{0,1,2,3,F\}. \]
Los estados \(0,1,2,3\) significan "todavía monocromática en ese palo". El estado \(F\) significa "ya se mezcló, luego una escalera de color es imposible". Si se añade una nueva carta de palo \(s\), la actualización es
\[ T(x,s)= \begin{cases} s, & \text{si es la primera carta de la escalera},\\ x, & \text{si }x\in\{0,1,2,3\}\text{ y }x=s,\\ F, & \text{en cualquier otro caso}. \end{cases} \]
Este resumen es completo: una vez que han aparecido dos palos distintos, ninguna decisión futura puede volver a convertir esa escalera en una escalera de color.
La ventana \(A2345\) es el único patrón no consecutivo en el recorrido \(2,\dots,A\). Después del \(5\) desaparece durante varios rangos y reaparece en el As. Por eso la programación dinámica conserva su estado de cinco valores incluso cuando esa escalera está temporalmente inactiva. Inactiva no significa terminada; solo significa que ese rango no aporta carta a esa escalera.
Supongamos que, tras procesar cierto rango, los estados de las escaleras etiquetadas aún abiertas son \(x_0,\dots,x_{k-1}\). Se codifican como un entero en base 5:
\[ z=\sum_{i=0}^{k-1} x_i 5^i. \]
Una tabla de DP almacena, para cada código \(z\), cuántas asignaciones parciales de palos llevan a él. En el siguiente rango, cada estado actual se ramifica sobre todas las inyecciones ordenadas de palos para las escaleras activas. Cada escalera activa actualiza su valor mediante \(T\). Si esa escalera termina en el rango actual, la transición solo se acepta cuando el nuevo estado es \(F\); acabar en uno de los cuatro estados de palo significaría que las cinco cartas comparten palo. Después se vuelve a codificar el conjunto de escaleras aún no terminadas.
Tomemos una copia de \(A2345\) y una copia de \(23456\), y ninguna otra escalera. Entonces
\[ o_2=o_3=o_4=o_5=2,\qquad o_6=o_A=1, \]
mientras que las demás ocupaciones valen \(0\), así que el patrón es factible. En los rangos \(2,3,4,5\) ambas escaleras etiquetadas están activas, de modo que cada uno de esos rangos aporta \(P(4,2)=12\) elecciones locales. En el rango \(6\), la escalera \(23456\) termina y debe estar ya en el estado \(F\). Mientras tanto, la rueda queda inactiva desde \(6\) hasta \(K\), pero su estado se arrastra sin cambios. Por último se procesa el As y la rueda solo se acepta si su estado actualizado también es \(F\). Este ejemplo explica a la vez la inyección de palos y la necesidad de recordar escaleras dormidas pero todavía no terminadas.
Si la ventana \(C_s\) aparece \(p_s\) veces, permutar esas \(p_s\) copias idénticas no cambia la colección final no ordenada. Por tanto, cada solución real ha sido contada
\[ \prod_{s=0}^{9} p_s! \]
veces en la DP etiquetada. Dividir por ese factor convierte la cuenta etiquetada en la cuenta buscada. Como comprobación rápida, una sola escalera produce \(10(4^5-4)=10200\): diez ventanas de rangos y, en cada una, exactamente cuatro asignaciones prohibidas que son escaleras de color.
Las implementaciones en C++, Python y Java generan primero todos los vectores de multiplicidades viables \(p\). Para cada patrón construyen las copias de escalera temporalmente etiquetadas y registran para cada copia en qué rangos está activa, en qué punto aparece por primera vez y en qué rango termina. También se precalculan todas las inyecciones ordenadas de palos para \(m=0,1,2,3,4\).
En cada rango, la implementación sabe qué escaleras etiquetadas necesitan carta en ese instante y cuáles seguirán abiertas después. Recorre todos los estados actuales en base 5, prueba cada inyección de palos permitida, actualiza los cinco estados, descarta las ramas que terminarían en escalera de color y acumula las cuentas supervivientes en la tabla del siguiente paso.
Después de procesar el As, el único estado terminal válido es el vacío. Su cuenta se divide por \(\prod p_s!\) para deshacer las etiquetas artificiales y se añade al total global. Las versiones en C++ y Java paralelizan el recorrido sobre patrones independientes; la versión en Python utiliza procesos trabajadores cuando compensa y, si no, ejecuta la misma recurrencia en serie.
El bucle exterior visita solo \(1599\) patrones viables cuando hay ocho escaleras. Dentro de un patrón, como mucho pueden permanecer abiertas ocho escaleras etiquetadas, así que el espacio de estados codificado queda acotado por
\[ 5^8=390625. \]
En la práctica, la parte alcanzable es bastante menor. En cualquier rango, a lo sumo cuatro escaleras pueden pedir carta simultáneamente, de modo que el factor máximo de ramificación local es
\[ P(4,4)=24. \]
La memoria también es moderada: para un patrón solo se conservan la tabla actual y la siguiente, además de unos pocos metadatos de las copias etiquetadas. La ganancia esencial es que no se enumeran subconjuntos de 40 cartas, sino que se cuentan historias de palos de forma simbólica sobre un conjunto muy pequeño de patrones factibles de rangos.
题目要求计算：从一副标准 52 张扑克牌中，选出 8 个互不重叠的 5 张顺子的方法数，并且这 8 个顺子里任何一个都不能是同花顺。允许的点数窗口只有通常的 10 种顺子： \(A2345\)、\(23456\)、\(34567\)、\(\dots\)、\(TJQKA\)。
如果直接枚举 40 张牌的子集，规模会大得无法处理。真正有效的做法是把“点数结构”和“花色结构”拆开。先决定 8 个顺子中每一种点数窗口各出现多少次；然后在这个固定的点数模式下，统计所有既不会发生卡牌冲突、又能保证每条顺子至少出现两种花色的花色分配。三种实现都用精确校验 \(N_1=10200\) 和 \(N_2=31832952\) 来验证这个模型。
整个推导可以看成两层计数：第一层只处理 10 种顺子窗口的出现次数，第二层用一个很紧凑的动态规划统计合法的花色历史。
记 10 种顺子窗口为 \(C_0,\dots,C_9\)，按照
\[ C_0=A2345,\quad C_1=23456,\quad C_2=34567,\quad \dots,\quad C_9=TJQKA \]
的顺序排列。与其直接挑选 8 条顺子，不如先选一个重数向量
\[ p=(p_0,p_1,\dots,p_9),\qquad p_s\ge 0,\qquad \sum_{s=0}^{9} p_s=8. \]
其中 \(p_s\) 表示第 \(s\) 个点数窗口被使用了多少次。
对每个点数 \(r\)，定义占用量
\[ o_r=\sum_{s:\,r\in C_s} p_s. \]
因为每个点数在整副牌中只有 4 张实体牌，也就是 4 种花色，所以任何可行方案都必须满足 \(o_r\le 4\)。而且在点数层面，这个条件已经足够了：只要所有 \(o_r\) 都不超过 4，剩下唯一需要解决的问题，就是当多条顺子同时需要同一点数时，如何给它们分配彼此不同的花色。
实现中先递归枚举所有满足 \(\sum p_s=8\) 且对 13 个点数都有 \(o_r\le 4\) 的向量 \(p\)。当总顺子数是 8 时，这样的可行模式只有 \(1599\) 个，所以外层搜索空间其实很小。
固定一个可行的重数向量以后，同一种点数窗口出现的多个副本会先被临时加上标签。原因在于：即使两条顺子拥有完全相同的点数集合，它们在花色选择过程中的历史仍然可能不同。因此第一步必须先数“带标签”的对象，最后再把这些人为引入的对称性消掉。
实现按照 \(2,3,4,5,6,7,8,9,T,J,Q,K,A\) 的顺序扫描 13 个点数。假设某个点数 \(r\) 上有 \(m\) 条带标签的顺子当前处于活跃状态，那么这 \(m\) 张牌必须来自 \(m\) 个不同花色。因此这一层的局部选择，就是把这 \(m\) 个活跃标签有序地单射到 4 种花色上。这样的选择数为
\[ P(4,m)=4\cdot 3\cdots (4-m+1)=\frac{4!}{(4-m)!},\qquad 0\le m\le 4. \]
由于已经有 \(o_r\le 4\)，所以绝不会出现更大的 \(m\)。
对于一条尚未结束的顺子，不需要保存完整的花色序列。未来是否合法，只取决于一件事：到目前为止，它看到的牌是否仍然全都属于同一种花色；如果是，那到底是哪一种。于是每条未完成顺子只需要 5 个状态：
\[ x\in\{0,1,2,3,F\}. \]
\(0,1,2,3\) 表示“目前仍然保持单一花色，而且是这一种花色”；\(F\) 表示“已经出现过至少两种花色，因此以后不可能再成为同花顺”。如果新加入一张花色为 \(s\) 的牌，状态更新规则为
\[ T(x,s)= \begin{cases} s, & \text{如果这是该顺子的第一张牌},\\ x, & \text{如果 }x\in\{0,1,2,3\}\text{ 且 }x=s,\\ F, & \text{其他情况}. \end{cases} \]
这就是整个状态压缩的关键。一旦某条顺子已经混入两种不同花色，后面的选择再怎么继续，也不可能把它“恢复”为同花顺。
\(A2345\) 是扫描顺序 \(2,\dots,A\) 中唯一一个不连续的窗口。它在处理完 \(5\) 之后会暂时消失，直到扫描到 \(A\) 才重新出现。因此动态规划必须在这段空档里继续保留它的 5 状态信息。也就是说，“当前不活跃”并不等于“已经结束”，它只是说明这个点数不属于那条顺子而已。
假设处理完某个点数以后，所有尚未完成的带标签顺子的状态是 \(x_0,\dots,x_{k-1}\)。把它们编码成一个 5 进制整数：
\[ z=\sum_{i=0}^{k-1} x_i 5^i. \]
动态规划表记录：每个编码 \(z\) 对应多少种部分花色分配。在下一个点数上，每个当前状态都会对所有允许的有序单射进行分支。每条活跃顺子按照 \(T\) 更新自己的 5 状态。如果某条顺子在这个点数结束，那么只有当更新后的状态是 \(F\) 时，该分支才合法；如果它结束时仍停留在 4 个具体花色状态之一，就说明 5 张牌全同花色，被题目禁止。然后把所有仍未结束的顺子重新编码成下一层的 5 进制状态。
考虑只取一条 \(A2345\) 和一条 \(23456\)，其余都不取。那么
\[ o_2=o_3=o_4=o_5=2,\qquad o_6=o_A=1, \]
其他点数的占用量都是 \(0\)，所以这个点数模式是可行的。在 \(2,3,4,5\) 这四个点数上，两条带标签的顺子同时活跃，因此每一层都有 \(P(4,2)=12\) 个局部花色选择。到点数 \(6\) 时，顺子 \(23456\) 结束，并且必须已经处于 \(F\) 状态。与此同时，轮子顺子从 \(6\) 到 \(K\) 都暂时不活跃，但它的状态要原样保留下来。最后扫描到 \(A\) 时，它也只有在更新后进入 \(F\) 状态才会被接受。这个例子同时解释了为什么需要“同点数用不同花色”的单射约束，以及为什么要给“暂时休眠但尚未结束”的顺子保留状态。
如果窗口 \(C_s\) 出现了 \(p_s\) 次，那么这 \(p_s\) 个完全相同的副本彼此交换，并不会改变最终的无序顺子集合。因此，每个真实解在带标签的动态规划中都被重复计算了
\[ \prod_{s=0}^{9} p_s! \]
次。对这个因子做除法，就把“带标签”的计数还原成题目要求的“无标签”计数。作为一个快速校验，当只取 1 条顺子时，答案应为 \(10(4^5-4)=10200\)：10 个点数窗口，每个窗口有 \(4^5\) 种花色方案，其中恰好 4 种是同花顺。
C++、Python 和 Java 实现都会先生成所有可行的重数向量 \(p\)。对于每个模式，再构造带临时标签的顺子副本，并记录每个副本在哪些点数活跃、在扫描过程中从哪里开始、到哪里结束。同时，还会预先生成 \(m=0,1,2,3,4\) 时全部可能的有序花色单射。
在每个点数上，实现都知道哪些带标签顺子当前需要这张牌，哪些顺子在这一层之后仍然未完成。它遍历当前所有 5 进制状态，尝试每一种允许的花色单射，更新 5 状态，丢弃那些会以同花顺结束的分支，并把剩余分支的计数累加到下一张状态表里。
当 \(A\) 也处理完之后，唯一合法的终态是空状态。它对应的计数除以 \(\prod p_s!\) 之后，就是该模式对总答案的贡献。C++ 和 Java 版本把这些彼此独立的模式分发给多个工作线程；Python 版本在值得并行时使用多个工作进程，否则执行同样的串行递推。
外层只需要遍历 \(1599\) 个可行模式。对单个模式来说，同时处于“尚未结束”状态的带标签顺子最多只有 8 条，因此编码后的状态空间上界是
\[ 5^8=390625. \]
实际上真正能到达的状态远少于这个上界。任意一个点数上，最多只有 4 条顺子会同时请求牌，因此局部分支数最多是
\[ P(4,4)=24. \]
内存开销也不大，因为对一个模式只保留当前和下一层的状态表，以及少量顺子元数据。真正的效率来源不在于暴力剪枝，而在于它从一开始就没有枚举 40 张牌的子集，而是只在极小的可行点数模式集合上做符号化计数。
Нужно посчитать число неупорядоченных семейств из восьми попарно непересекающихся 5-карточных стритов из стандартной колоды в 52 карты, причём ни один из этих стритов не должен быть стрит-флешем. Разрешены только десять обычных окон рангов: \(A2345\), \(23456\), \(34567\), \(\dots\), \(TJQKA\).
Прямой перебор 40-карточных подмножеств здесь бесполезен. Рабочая идея состоит в разделении задачи на ранговую и мастевую части. Сначала фиксируется, сколько из восьми стритов используют каждое из десяти окон рангов. Затем для этого фиксированного рангового шаблона считается число назначений мастей, которые не допускают совпадения карт и одновременно гарантируют, что в каждом стрите встречаются хотя бы две разные масти. Реализация проверяет модель точными значениями \(N_1=10200\) и \(N_2=31832952\).
Вся конструкция состоит из двух уровней: сначала считаются допустимые ранговые шаблоны, затем компактное DP считает легальные мастевые истории.
Обозначим десять окон через \(C_0,\dots,C_9\):
\[ C_0=A2345,\quad C_1=23456,\quad C_2=34567,\quad \dots,\quad C_9=TJQKA. \]
Вместо того чтобы сразу выбирать восемь стритов, сначала выбираем вектор кратностей
\[ p=(p_0,p_1,\dots,p_9),\qquad p_s\ge 0,\qquad \sum_{s=0}^{9} p_s=8. \]
Число \(p_s\) показывает, сколько раз используется окно \(C_s\).
Для каждого ранга \(r\) введём заполненность
\[ o_r=\sum_{s:\,r\in C_s} p_s. \]
У каждого ранга в колоде есть ровно четыре физические карты, по одной каждой масти, поэтому обязательно должно выполняться \(o_r\le 4\). Более того, этого уже достаточно на ранговом уровне: если ни один ранг не требуется более четырёх раз, то вся оставшаяся работа состоит только в том, чтобы выдать разным копиям стрита, использующим один и тот же ранг, разные масти.
Реализации рекурсивно перечисляют в точности те векторы \(p\), для которых \(\sum p_s=8\) и \(o_r\le 4\) для всех 13 рангов. Для восьми стритов таких шаблонов всего \(1599\).
После фиксации допустимого шаблона одинаковые копии одного и того же окна временно получают метки. Это необходимо, потому что два стрита с одинаковым набором рангов всё равно могут иметь разные мастевые траектории. Поэтому сначала считается число помеченных конфигураций, а потом устраняется искусственно внесённая симметрия.
Ранги обрабатываются в порядке \(2,3,4,5,6,7,8,9,T,J,Q,K,A\). Пусть на некотором ранге \(r\) активны \(m\) помеченных стритов. Тогда эти \(m\) карт обязаны иметь \(m\) различных мастей, и локальный выбор представляет собой упорядоченную инъекцию из активных меток в четыре масти. Число таких вариантов равно
\[ P(4,m)=4\cdot 3\cdots (4-m+1)=\frac{4!}{(4-m)!},\qquad 0\le m\le 4. \]
Благодаря условию \(o_r\le 4\) большие значения \(m\) не возникают.
Для незавершённого стрита не нужно хранить всю историю мастей. Важна только одна вещь: все ли уже увиденные карты пока принадлежат одной масти и если да, то какой именно. Отсюда получается пять состояний:
\[ x\in\{0,1,2,3,F\}. \]
Состояния \(0,1,2,3\) означают «пока ещё монохроматичен в этой масти», а \(F\) означает «уже смешался, поэтому стрит-флеш невозможен». Если добавляется новая карта масти \(s\), используется переход
\[ T(x,s)= \begin{cases} s, & \text{для первой карты стрита},\\ x, & \text{если }x\in\{0,1,2,3\}\text{ и }x=s,\\ F, & \text{иначе}. \end{cases} \]
Это и есть ключевой инвариант: как только у стрита появились две разные масти, никакие дальнейшие карты уже не могут снова сделать его стрит-флешем.
Окно \(A2345\) - единственный шаблон, который не является непрерывным в порядке сканирования \(2,\dots,A\). После ранга \(5\) оно надолго исчезает и возвращается только на тузе. Поэтому DP обязано переносить его пятисостояние через промежуточные ранги без изменений. Иными словами, «неактивен сейчас» не значит «уже завершён».
Пусть после обработки некоторого ранга состояния ещё не завершённых помеченных стритов равны \(x_0,\dots,x_{k-1}\). Они кодируются целым числом в системе счисления по основанию 5:
\[ z=\sum_{i=0}^{k-1} x_i 5^i. \]
DP-таблица хранит для каждого кода \(z\) количество частичных назначений мастей, приводящих к нему. На следующем ранге каждый текущий код ветвится по всем допустимым упорядоченным инъекциям мастей для активных стритов. Каждая активная копия обновляет своё состояние по правилу \(T\). Если стрит заканчивается на текущем ранге, то переход разрешён только тогда, когда новое состояние равно \(F\); завершение в одном из четырёх конкретных мастевых состояний означало бы, что все пять карт одной масти. После этого все ещё незавершённые стриты заново кодируются в следующий 5-ичный код.
Возьмём одну копию \(A2345\) и одну копию \(23456\), без остальных стритов. Тогда
\[ o_2=o_3=o_4=o_5=2,\qquad o_6=o_A=1, \]
а все остальные заполненности равны \(0\), значит шаблон допустим. На рангах \(2,3,4,5\) обе помеченные копии активны, поэтому на каждом из этих шагов имеется \(P(4,2)=12\) локальных мастевых вариантов. На ранге \(6\) стрит \(23456\) завершается и к этому моменту уже обязан находиться в состоянии \(F\). В то же время колесо неактивно с \(6\) по \(K\), но его состояние переносится без изменения. Наконец, на тузе колесо принимается только если его обновлённое состояние тоже равно \(F\). Этот пример одновременно показывает и инъективное назначение мастей, и необходимость помнить «спящие», но ещё не завершённые стриты.
Если окно \(C_s\) встречается \(p_s\) раз, то перестановка этих \(p_s\) одинаковых копий не меняет итоговое неупорядоченное семейство стритов. Значит, каждый настоящий ответ был посчитан в помеченном DP
\[ \prod_{s=0}^{9} p_s! \]
раз. Деление на этот множитель переводит помеченный счёт в требуемый непомеченный. Быстрая проверка: для одного стрита получаем \(10(4^5-4)=10200\), потому что у каждого из 10 окон есть \(4^5\) раскрасок по мастям, и ровно 4 из них являются стрит-флешами.
Реализации на C++, Python и Java сначала порождают все допустимые векторы кратностей \(p\). Для каждого шаблона они создают временно помеченные копии стритов и сохраняют нужную служебную информацию: на каких рангах эта копия активна, где она впервые появляется в сканировании и где окончательно заканчивается. Также заранее строятся все упорядоченные инъекции мастей для \(m=0,1,2,3,4\).
На каждом ранге реализация знает, какие помеченные стриты сейчас требуют карту, а какие останутся незавершёнными после этого шага. Далее перебираются текущие 5-ичные состояния, пробуются все допустимые локальные назначения мастей, обновляются пятисостояния, отбрасываются ветви, завершающиеся стрит-флешем, и выжившие количества суммируются в следующей таблице состояний.
После обработки туза допустим только пустой конечный код. Его число делится на \(\prod p_s!\), чтобы убрать искусственные метки, и добавляется к общему ответу. Версии на C++ и Java распараллеливают независимые подсчёты по шаблонам; версия на Python при выгоде использует отдельные рабочие процессы, а иначе выполняет ту же рекурсию последовательно.
Во внешнем цикле рассматриваются всего \(1599\) допустимых шаблонов для восьми стритов. Внутри одного шаблона одновременно незавершёнными могут быть не более восьми помеченных стритов, поэтому закодированное пространство состояний ограничено сверху величиной
\[ 5^8=390625. \]
На практике достижимых состояний намного меньше. На одном ранге максимум четыре стрита могут одновременно требовать карту, поэтому локальная ветвистость не превосходит
\[ P(4,4)=24. \]
Памяти тоже нужно немного: для одного шаблона достаточно текущей и следующей таблиц DP плюс небольших метаданных о помеченных копиях. Главный выигрыш в том, что алгоритм вообще не перебирает 40-карточные подмножества колоды, а символически считает мастевые истории на очень маленьком множестве допустимых ранговых шаблонов.
المطلوب هو عدّ العائلات غير المرتبة المؤلفة من ثمانية مستقيمات بوكر منفصلة، كل واحد منها من 5 بطاقات، مأخوذة من رزمة قياسية من 52 بطاقة، مع الشرط الإضافي أن أياً من هذه المستقيمات الثمانية لا يكون مستقيمًا ملوّنًا. نوافذ الرتب المسموح بها هي فقط المستقيمات العشرة المعتادة: \(A2345\)، \(23456\)، \(34567\)، \(\dots\)، \(TJQKA\).
العدّ المباشر لمجموعات من 40 بطاقة غير عملي تمامًا. الفكرة الصحيحة هي فصل بنية الرتب عن بنية الأشكال. أولاً نحدد كم مرة يستعمل كل واحد من نوافذ الرتب العشرة داخل المستقيمات الثمانية. بعد ذلك، وبالنسبة إلى هذا النمط الرتبي الثابت، نعدّ توزيعات الأشكال التي تمنع تكرار البطاقة نفسها وتضمن في الوقت نفسه أن كل مستقيم يستخدم شكلين مختلفين على الأقل. وتتحقق التطبيقات من صحة النموذج بالقيمتين الدقيقتين \(N_1=10200\) و\(N_2=31832952\).
الحل يتكون من مستويين في العد: مستوى يحدد أنماط الرتب الممكنة، ومستوى ثانٍ يستعمل برمجة ديناميكية مضغوطة لعدّ تواريخ الأشكال المسموح بها.
لنرمز إلى نوافذ المستقيم العشرة بـ \(C_0,\dots,C_9\) وفق الترتيب
\[ C_0=A2345,\quad C_1=23456,\quad C_2=34567,\quad \dots,\quad C_9=TJQKA. \]
بدلاً من اختيار المستقيمات الثمانية مباشرة، نختار أولاً متجه تعدد
\[ p=(p_0,p_1,\dots,p_9),\qquad p_s\ge 0,\qquad \sum_{s=0}^{9} p_s=8. \]
القيمة \(p_s\) تبيّن عدد المستقيمات التي تستعمل النافذة \(C_s\).
لكل رتبة \(r\) نعرّف الإشغال بـ
\[ o_r=\sum_{s:\,r\in C_s} p_s. \]
في كل رتبة توجد أربع بطاقات فعلية فقط، واحدة لكل شكل، ولذلك لا بد من تحقق \(o_r\le 4\). وفي الحقيقة هذا الشرط يكفي على مستوى الرتب: فإذا لم تتجاوز أي رتبة العدد 4، فالمشكلة الوحيدة المتبقية هي كيف نعطي أشكالًا مختلفة لنسخ المستقيم التي تحتاج إلى الرتبة نفسها.
التطبيقات تولّد على نحو عودي جميع المتجهات \(p\) التي تحقق \(\sum p_s=8\) و\(o_r\le 4\) لجميع الرتب الثلاث عشرة. وعندما يكون عدد المستقيمات ثمانية، لا يبقى إلا \(1599\) نمطًا رتبيًا صالحًا.
بعد تثبيت نمط رتبي صالح، تُعطى النسخ المتساوية من النافذة نفسها تسميات مؤقتة. والسبب أن مستقيمين لهما الرتب نفسها قد يسلكان تاريخين مختلفين من حيث الأشكال. لذلك يتم العد أولاً على كائنات معلّمة، ثم يُزال هذا التناظر المصطنع في النهاية.
تُفحص الرتب بالترتيب \(2,3,4,5,6,7,8,9,T,J,Q,K,A\). إذا كان هناك \(m\) مستقيمات معلّمة فعالة عند رتبة \(r\)، فيجب أن تستعمل هذه البطاقات \(m\) أشكالًا مختلفة. إذن القرار المحلي هو حقن مرتب من تسميات المستقيمات الفعالة إلى الأشكال الأربعة. وعدد هذه الخيارات هو
\[ P(4,m)=4\cdot 3\cdots (4-m+1)=\frac{4!}{(4-m)!},\qquad 0\le m\le 4. \]
وبفضل الشرط \(o_r\le 4\) لا يظهر أي \(m\) أكبر من ذلك.
بالنسبة إلى مستقيم لم يكتمل بعد، لا نحتاج إلى حفظ التاريخ الكامل للأشكال. كل ما يهم هو: هل جميع البطاقات التي ظهرت حتى الآن ما زالت من شكل واحد، وإذا كان الأمر كذلك فما هو ذلك الشكل؟ من هنا نحصل على خمس حالات فقط:
\[ x\in\{0,1,2,3,F\}. \]
الحالات \(0,1,2,3\) تعني «ما زال أحادي الشكل في هذا الشكل»، أما \(F\) فتعني «اختلط بالفعل، وبالتالي صار المستقيم الملوّن مستحيلاً». وإذا أضيفت بطاقة جديدة ذات شكل \(s\)، فإن التحديث هو
\[ T(x,s)= \begin{cases} s, & \text{first card},\\ x, & x\in\{0,1,2,3\}\text{ and }x=s,\\ F, & \text{otherwise}. \end{cases} \]
هذا هو الثابت الأساسي في الحل: ما إن يظهر شكلان مختلفان داخل مستقيم واحد، فلن تتمكن البطاقات اللاحقة أبدًا من إعادته إلى حالة المستقيم الملوّن.
النافذة \(A2345\) هي النمط الوحيد غير المتصل عند المسح بالترتيب \(2,\dots,A\). بعد الرتبة \(5\) تختفي لعدة رتب ثم تعود عند الآس. لذلك تحتفظ البرمجة الديناميكية بحالتها ذات القيم الخمس حتى عبر الرتب التي تكون فيها غير فعالة. فكون المستقيم غير فعّال مؤقتًا لا يعني أنه انتهى، بل يعني فقط أن الرتبة الحالية لا تزوده ببطاقة.
بعد معالجة رتبة معينة، لنفرض أن حالات المستقيمات المعلّمة التي لم تكتمل بعد هي \(x_0,\dots,x_{k-1}\). تُشفَّر هذه الحالات في عدد واحد بأساس 5:
\[ z=\sum_{i=0}^{k-1} x_i 5^i. \]
يخزّن جدول البرمجة الديناميكية، لكل رمز \(z\)، عدد التوزيعات الجزئية للأشكال التي تصل إليه. عند الرتبة التالية يتفرع كل وضع حالي عبر جميع الحقون المرتبة المسموح بها للأشكال عند تلك الرتبة. كل مستقيم فعّال يحدّث حالته وفق \(T\). وإذا انتهى المستقيم عند الرتبة الحالية، فلا يُقبل الفرع إلا إذا كانت حالته الجديدة هي \(F\)؛ أما انتهاؤه في واحدة من الحالات الأربع الخاصة بالأشكال فيعني أن البطاقات الخمس كلها من الشكل نفسه. بعد ذلك يعاد ترميز جميع المستقيمات التي ما زالت غير منتهية في الرمز التالي بأساس 5.
لنأخذ نسخة واحدة من \(A2345\) ونسخة واحدة من \(23456\) من دون أي مستقيمات أخرى. عندئذ
\[ o_2=o_3=o_4=o_5=2,\qquad o_6=o_A=1, \]
وجميع الإشغالات الأخرى تساوي \(0\)، لذا فالنمط صالح. عند الرتب \(2,3,4,5\) يكون المستقيمان المعلّمان فعّالين معًا، وبالتالي يساهم كل موضع بعدد محلي مقداره \(P(4,2)=12\) من توزيعات الأشكال. عند الرتبة \(6\) ينتهي المستقيم \(23456\)، ويجب أن يكون قد وصل بالفعل إلى الحالة \(F\). أما مستقيم العجلة فيبقى غير فعّال من \(6\) حتى \(K\)، لكن حالته تُحمل دون تغيير. وأخيرًا عند الآس لا يُقبل إلا إذا أصبحت حالته المحدّثة أيضًا \(F\). هذا المثال الصغير يوضح معًا سبب الحاجة إلى التوزيع الحقني للأشكال وسبب الحاجة إلى حفظ حالة مستقيم «نائم» لكنه غير منتهٍ بعد.
إذا ظهرت النافذة \(C_s\) عدد \(p_s\) من المرات، فإن تبديل هذه النسخ المتطابقة فيما بينها لا يغيّر العائلة النهائية غير المرتبة من المستقيمات. لذلك يكون كل حل حقيقي قد عُدّ في البرمجة الديناميكية المعلّمة
\[ \prod_{s=0}^{9} p_s! \]
مرة. والقسمة على هذا العامل تعيد العدّ من الحالة المعلّمة إلى الحالة المطلوبة غير المعلّمة. وكفحص سريع، عندما يكون لدينا مستقيم واحد فقط نحصل على \(10(4^5-4)=10200\): عشر نوافذ رتب، ولكل نافذة \(4^5\) توزيعات للأشكال، منها أربع فقط مستقيمات ملوّنة.
تبدأ تطبيقات C++ وPython وJava بتوليد جميع متجهات التعدد الصالحة \(p\). ثم تبني، لكل نمط، نسخ المستقيمات المعلّمة مؤقتًا وتسجل المعلومات اللازمة عن كل نسخة: في أي الرتب تكون فعّالة، وأين تظهر لأول مرة في المسح، وعند أي رتبة تنتهي. كما تُحضَّر مسبقًا جميع الحقون المرتبة للأشكال من أجل \(m=0,1,2,3,4\).
عند كل رتبة، يعرف التنفيذ أي المستقيمات المعلّمة تحتاج إلى بطاقة الآن، وأيها سيبقى غير مكتمل بعد هذه الخطوة. ثم يمر على جميع الحالات الحالية ذات التمثيل الخماسي، ويجرّب كل توزيع محلي مسموح للأشكال، ويحدّث الحالات الخمسية، ويرفض الفروع التي تنتهي بمستقيم ملوّن، ويضيف بقية العدادات إلى جدول الحالة التالي.
بعد معالجة الآس، لا تبقى إلا الحالة النهائية الفارغة. ويُقسَم عددها على \(\prod p_s!\) لإزالة أثر التسميات المصطنعة، ثم يُضاف إلى الجواب الكلي. وتوزع نسختا C++ وJava حسابات الأنماط المستقلة على عدة خيوط عمل، بينما تستعمل نسخة Python عمليات عاملة منفصلة عندما يكون ذلك مجديًا وتعود عند عدم الحاجة إلى التوازي إلى التكرار التسلسلي نفسه.
الحل الخارجي يمر فقط على \(1599\) نمطًا صالحًا عندما يكون عدد المستقيمات ثمانية. وداخل نمط واحد لا يمكن أن تبقى أكثر من ثمانية مستقيمات معلّمة غير منتهية في الوقت نفسه، ولذلك يكون فضاء الحالات المشفّر محدودًا بـ
\[ 5^8=390625. \]
لكن الجزء القابل للوصول عمليًا أصغر بكثير. وعند أي رتبة لا يمكن أن تطلب أكثر من أربعة مستقيمات بطاقة في الوقت نفسه، ولذلك فإن أقصى تفرع محلي هو
\[ P(4,4)=24. \]
استهلاك الذاكرة متواضع أيضًا، لأن التنفيذ يحتفظ لكل نمط بجدولي الحالة الحالي والتالي فقط، بالإضافة إلى قدر صغير من البيانات الوصفية الخاصة بالنسخ المعلّمة. والميزة الحاسمة هنا هي أن الخوارزمية لا تعدّ مجموعات من 40 بطاقة مباشرة، بل تعدّ تواريخ الأشكال بصورة رمزية فوق مجموعة صغيرة جدًا من الأنماط الرتبية الممكنة.