Dans cet article, ce qui est sélectionné ou non dans la recherche complète de bits est appelé «cible».
Une combinaison peut être exprimée en exprimant l'ensemble sous forme de tableau de bits et en définissant 1 lors de la sélection de la cible et 0 lorsque vous ne sélectionnez pas la cible.
Exemple de combinaison: sélectionnez B, C, E de A à F.
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 1 | 0 |
La recherche complète de bits est une méthode pour énumérer et rechercher tous les modèles de la combinaison de «sélectionner» et «ne pas sélectionner».
Il existe différentes méthodes pour une recherche de bits complète.
--Bit recherche complète en utilisant l'opération sur bit (la meilleure méthode de recherche si vous recherchez par recherche complète de bit)
Un ensemble de produits directs est un ensemble qui rassemble tous les modèles lorsque les éléments sont retirés un par un pour plusieurs ensembles et transformés en un ensemble.
À titre d'exemple concret, l'exemple de Trump est très facile à comprendre.
Trump est un ensemble de produits directs d'un ensemble de nombres (A, 2, 3 ... 10, J, Q, K) et d'un ensemble de marques (♤, ♧, ♡, ♢).
[Exemple d'ensemble de produits direct (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)
Par la suite, en supposant qu'il existe un ensemble $ A $ et un ensemble $ B $, l'ensemble de produits directs est exprimé comme $ A × B $.
Par exemple, Trump est un ensemble de produits directs $ Rank x Suit $ d'un ensemble de nombres $ Rank $ et d'un ensemble de marques $ Suit $.
L'ensemble de produits directs exprime la combinaison par bit.
Tout d'abord, réfléchissons à la manière de sélectionner deux cibles.
Il existe quatre combinaisons de sélection de deux cibles A et B: "ne pas sélectionner les deux", "sélectionner uniquement A", "sélectionner uniquement B" et "sélectionner les deux".
S'il est exprimé en bits, il sera comme indiqué dans le tableau ci-dessous.
| A\B | 0 | 1 |
|---|---|---|
| 0 | (0, 0) | (0, 1) |
| 1 | (1, 0) | (1, 1) |
Par exemple, si l'ordre de l'ensemble est ** (A, B) ** et que le bit est ** (1, 0) , cela signifie " Sélectionnez A, ne sélectionnez pas B **".
Ici, l'ensemble $ A = \ {0, 1 \} $ ayant deux éléments, "choisissez (= 1)" et "ne choisissez pas (= 0)" pour la cible A, et "choisissez" pour la cible B également. On peut dire qu'il existe un ensemble $ B = \ {0, 1 \} $ qui a deux éléments, "ne pas choisir".
Dans ce cas, tous les modèles de la combinaison de sélection de la cible A (= $ \ {0, 1 \} $) et de la cible B (= $ \ {0, 1 \} $) sont des ensembles de produits directs.
Peut être représenté par.
Ensuite, étendons la cible à ** 3 ou plus **.
Premièrement, un ensemble de produits directs peut être composé de trois ensembles ou plus. Étant donné que l'ensemble de produits direct est un ensemble qui rassemble tous les modèles lorsque les éléments sont retirés un par un pour plusieurs ensembles et transformés en un ensemble, l'ensemble de produits direct peut être créé sans aucun problème, même avec trois ensembles ou plus.
Je pense que ce sera déroutant parce que j'ai fait un ensemble de produits directs dans un tableau bidimensionnel plus tôt, donc je vais l'expliquer afin de pouvoir être convaincu que trois ou plus sont bien. En supposant qu'il existe un ensemble $ A $, un ensemble $ B $ et un ensemble $ C $, l'ensemble de produits directs $ A × B × C $ est représenté.
Tout d'abord, soit $ P $ l'ensemble de produits direct $ A x B $ de l'ensemble $ A $ et l'ensemble $ B $. L'ensemble de produits directs $ P $ est un ensemble, vous pouvez donc bien sûr prendre un ensemble de produits directs avec d'autres ensembles.
L'ensemble de produits directs de l'ensemble $ P $ et l'ensemble $ C $, $ P × C $, peuvent être représentés par une table à deux dimensions.
À titre d'exemple concret, faisons un tableau sur la façon de sélectionner les cibles A, B et C. Chacun a un ensemble avec deux éléments, "choisir (= 1)" et "ne pas choisir (= 0)".
Tout d'abord, trouvez $ P = A × B $.
Ceci est indiqué dans le tableau ci-dessus.
| A\B | 0 | 1 |
|---|---|---|
| 0 | (0, 0) | (0, 1) |
| 1 | (1, 0) | (1, 1) |
Autrement dit, $ P = \ {(0, 0), (0, 1), (1, 0), (1, 1) \} $.
Ensuite, $ P x C $ est représenté par le tableau suivant.
| 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) |
(* Peut-être que $ P x C $ ressemble à ((0, 0), 0), mais je m'en fiche ...)
Je pense que vous êtes convaincu que vous pouvez obtenir un ensemble de produits direct pour trois ensembles ou plus. Bien entendu, il en va de même pour les objets qui ont un ensemble tel que $ \ {"choisir" ou "ne pas choisir" \} $.
Exemple: Tous les modèles de combinaisons qui sélectionnent les cibles A à F
Il peut être exprimé comme un ensemble de produits directs de $ A × B × C × D × E × F $.
Python a une fonction dans la bibliothèque standard qui produit un ensemble de produits direct. C'est la fonction product du module ʻitertools`.
Ce qui suit est une implémentation qui énumère et produit tous les modèles de combinaisons qui sélectionnent A à F.
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)
production
[]
['F']
['E']
['E', 'F']
['D']
['D', 'F']
['D', 'E']
['D', 'E', 'F']
...(réduction)...
['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']
Notez qu'il s'agit d'un ensemble de produits directs de l'ensemble $ \ {0, 1 \} $.
Dans cette implémentation, les ensembles A à F "choisir" et "ne pas choisir" $ \ {0, 1 \} $ sont préparés respectivement, mais ils sont tous identiques à $ \ {0, 1 \} $. Ainsi, l'utilisation de l'argument de mot-clé de la fonction produit`` répéter le rend plus concis.
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)
Le résultat de sortie est le même que ci-dessus.
――Bit full search est une collection de tous les modèles de «sélectionner» et «ne pas sélectionner» pour chaque cible.
Il y a aussi un article sur la recherche de bits complète par 冪 set, alors jetez un œil.
Easy bit full search (Easy set)
Recommended Posts