In diesem Artikel wird das, was in der Bit-Vollsuche ausgewählt oder nicht ausgewählt wurde, als "Ziel" bezeichnet.
Eine Kombination kann ausgedrückt werden, indem die Menge als Bitarray ausgedrückt wird und bei Auswahl des Ziels 1 und bei Nichtauswahl des Ziels 0 gesetzt wird.
Kombinationsbeispiel: Wählen Sie B, C, E von A bis F.
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 1 | 0 |
Die Bit-Vollsuche ist eine Methode zum Auflisten und Durchsuchen aller Muster der Kombination von "Auswählen" und "Nicht auswählen".
Es gibt verschiedene Methoden für die Bit-Vollsuche.
Ein direkter Produktsatz ist ein Satz, der alle Muster sammelt, wenn Elemente einzeln für mehrere Sätze herausgenommen und zu einem Satz verarbeitet werden.
Als konkretes Beispiel ist das Beispiel von Trump sehr leicht zu verstehen.
Trump ist eine direkte Produktmenge aus einer Reihe von Zahlen (A, 2, 3 ... 10, J, Q, K) und einer Reihe von Markierungen (♤, ♧, ♡, ♢).
[Beispiel eines direkten Produktsatzes (Wikipedia)](https://ja.wikipedia.org/wiki/%E7%9B%B4%E7%A9%8D%E9%9B%86%E5%90%88#%E7% 9B% B4% E7% A9% 8D% E9% 9B% 86% E5% 90% 88% E3% 81% AE% E4% BE% 8B)
Unter der Annahme, dass es eine Menge $ A $ und eine Menge $ B $ gibt, wird die direkte Produktmenge im Folgenden als $ A × B $ ausgedrückt.
Zum Beispiel ist Trump eine direkte Produktmenge $ Rank x Suit $ aus einer Reihe von Zahlen $ Rank $ und einer Reihe von Markierungen $ Suit $.
Der direkte Produktsatz drückt die Kombination bitweise aus.
Lassen Sie uns zunächst überlegen, wie Sie zwei Ziele auswählen.
Es gibt vier Kombinationen zur Auswahl von zwei Zielen A und B: "Nicht beide auswählen", "Nur A auswählen", "Nur B auswählen" und "Beide auswählen".
Wenn in Bit ausgedrückt, entspricht dies der folgenden Tabelle.
| A\B | 0 | 1 |
|---|---|---|
| 0 | (0, 0) | (0, 1) |
| 1 | (1, 0) | (1, 1) |
Wenn beispielsweise die Reihenfolge der Menge ** (A, B) ** und das Bit ** (1, 0) ** ist, bedeutet dies "** A auswählen, nicht B ** auswählen".
Hier hat die Menge $ A = \ {0, 1 \} $ zwei Elemente: "wähle (= 1)" und "wähle nicht (= 0)" für das Ziel A und "wähle" auch für das Ziel B. Man kann sagen, dass es eine Menge $ B = \ {0, 1 \} $ gibt, die zwei Elemente enthält: "Nicht wählen".
In einem solchen Fall sind alle Muster der Kombination, die Ziel A (= $ \ {0, 1 \} $) und Ziel B (= $ \ {0, 1 \} $) auswählt, direkte Produktmengen
Kann vertreten werden durch.
Als nächstes erweitern wir das Ziel auf ** 3 oder mehr **.
Erstens kann ein direkter Produktsatz aus drei oder mehr Sätzen bestehen. Da der direkte Produktsatz ein Satz ist, der alle Muster sammelt, wenn die Elemente einzeln für mehrere Sätze herausgenommen und zu einem Satz zusammengefügt werden, kann der direkte Produktsatz auch mit drei oder mehr Sätzen problemlos erstellt werden.
Ich denke, es wird verwirrend sein, weil ich das direkte Produkt früher in eine zweidimensionale Tabelle gesetzt habe, also werde ich es erklären, damit ich davon überzeugt werden kann, dass drei oder mehr in Ordnung sind. Unter der Annahme, dass es eine Menge $ A $, eine Menge $ B $ und eine Menge $ C $ gibt, wird die direkte Produktmenge $ A × B × C $ dargestellt.
Zunächst sei $ P $ die direkte Produktmenge $ A x B $ der Menge $ A $ und der Menge $ B $. Das direkte Produktset $ P $ ist ein Set, daher können Sie natürlich ein direktes Produktset mit anderen Sets kombinieren.
Die direkte Produktmenge der Menge $ P $ und der Menge $ C $, $ P × C $, kann durch eine zweidimensionale Tabelle dargestellt werden.
Lassen Sie uns als konkretes Beispiel eine Tabelle zur Auswahl der Ziele A, B und C erstellen. Jedes hat eine Menge mit zwei Elementen, "wähle (= 1)" und "wähle nicht (= 0)".
Finden Sie zuerst $ P = A × B $.
Dies ist in der Tabelle zuvor gezeigt.
| A\B | 0 | 1 |
|---|---|---|
| 0 | (0, 0) | (0, 1) |
| 1 | (1, 0) | (1, 1) |
Das heißt, $ P = \ {(0, 0), (0, 1), (1, 0), (1, 1) \} $.
Als nächstes wird $ P x C $ durch die folgende Tabelle dargestellt.
| P\C | 0 | 1 |
|---|---|---|
| (0, 0) | (0, 0, 0) | (0, 0, 1) |
| (0, 1) | (0, 1, 0) | (0, 1, 1) |
| (1, 0) | (1, 0, 0) | (1, 0, 1) |
| (1, 1) | (1, 1, 0) | (1, 1, 1) |
(* Vielleicht sieht $ P x C $ aus wie ((0, 0), 0), aber es interessiert mich nicht ...)
Ich denke, Sie sind überzeugt, dass Sie ein direktes Produktset für drei oder mehr Sets erhalten können. Gleiches gilt natürlich auch für Objekte mit Mengen wie $ \ {"wählen" und "nicht wählen" \} $.
Beispiel: Alle Muster von Kombinationen, die die Ziele A bis F auswählen
Es kann durch den direkten Produktsatz von $ A × B × C × D × E × F $ dargestellt werden.
Python hat eine Funktion in der Standardbibliothek, die einen direkten Produktsatz erzeugt. Dies ist die "Produkt" -Funktion des "itertools" -Moduls.
Das Folgende ist eine Implementierung, die alle Muster von Kombinationen auflistet und ausgibt, die A bis F auswählen.
from itertools import product
items = ["A", "B", "C", "D", "E", "F"]
A = (0, 1)
B = (0, 1)
C = (0, 1)
D = (0, 1)
E = (0, 1)
F = (0, 1)
for bits in product(A, B, C, D, E, F):
comb = [x for x, bit in zip(items, bits) if bit == 1]
print(comb)
Ausgabe
[]
['F']
['E']
['E', 'F']
['D']
['D', 'F']
['D', 'E']
['D', 'E', 'F']
...(Kürzung)...
['A', 'B', 'C']
['A', 'B', 'C', 'F']
['A', 'B', 'C', 'E']
['A', 'B', 'C', 'E', 'F']
['A', 'B', 'C', 'D']
['A', 'B', 'C', 'D', 'F']
['A', 'B', 'C', 'D', 'E']
['A', 'B', 'C', 'D', 'E', 'F']
Beachten Sie, dass es sich um eine direkte Produktmenge der Menge $ \ {0, 1 \} $ handelt.
In dieser Implementierung werden die Sätze $ \ {0, 1 \} $ von A bis F "auswählen" und "nicht auswählen" vorbereitet, aber sie sind alle gleich wie $ \ {0, 1 \} $. Wenn Sie also das Schlüsselwortargument "product" verwenden, wird es prägnanter.
from itertools import product
items = ["A", "B", "C", "D", "E", "F"]
for bits in product((0, 1), repeat=len(items)):
comb = [x for x, bit in zip(items, bits) if bit == 1]
print(comb)
Das Ausgabeergebnis ist das gleiche wie oben.
――Bit Full Search ist eine Sammlung aller Muster von "Auswählen" und "Nicht auswählen" für jedes Ziel.
Es gibt auch einen Artikel über die Vollbit-Suche nach 冪 set, also schauen Sie bitte mal rein.
Einfache vollständige Bit-Suche (Easy Set)
Recommended Posts