In this article, what is selected or not selected in the bit full search is called "target".
A combination can be expressed by expressing the set as a bit array and setting 1 when selecting the target and 0 when not selecting the target.
Combination example: Select B, C, E from A to F.
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 1 | 0 |
Bit full search is a method to enumerate and search all patterns of the combination of "select" and "do not select".
There are various methods for bit full search.
--Bit full search using bit operation (the best hit method if you search by bit full search) --Full bit search by exponentiation (https://qiita.com/conf8o/items/548d0baaf505f9bee91f) --Full bit search by Cartesian product (this article)
The Cartesian product set is a set that collects all the patterns when the elements are taken out one by one for multiple sets and made into a set.
As a concrete example, the example of playing cards is very easy to understand.
Trump is a Cartesian product of a set of numbers (A, 2, 3 ... 10, J, Q, K) and a set of marks (♤, ♧, ♡, ♢).
[Example of Cartesian product (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)
Hereafter, assuming that there is a set $ A $ and a set $ B $, the direct product set is expressed as $ A × B $.
For example, playing cards is the Cartesian product $ Rank x Suit $ of the set of numbers $ Rank $ and the set of marks $ Suit $.
The direct product set expresses the combination by bits.
First, let's think about how to select two targets.
There are four combinations of selecting two targets A and B: "do not select both", "select only A", "select only B", and "select both".
If expressed in bits, it will be as shown in the table below.
| A\B | 0 | 1 |
|---|---|---|
| 0 | (0, 0) | (0, 1) |
| 1 | (1, 0) | (1, 1) |
For example, if the order of the set is ** (A, B) ** and the bit is ** (1, 0) , it means " Select A, do not select B **".
Here, the set $ A = \ {0, 1 \} $ having two elements, "choose (= 1)" and "do not choose (= 0)" for the target A, and "choose" for the target B as well. It can be said that there is a set $ B = \ {0, 1 \} $ that has two elements, "don't choose".
In such a case, all patterns of the combination that selects target A (= $ \ {0, 1 \} $) and target B (= $ \ {0, 1 \} $) are Cartesian products.
Can be represented by.
Next, let's expand the target to ** 3 or more **.
First, the Cartesian product can be made up of three or more sets. A Cartesian product set is a set that collects all the patterns when elements are taken out one by one for multiple sets and made into a set, so a Cartesian product set can be created without problems even with three or more sets.
I think it will be confusing because I made the Cartesian product into a two-dimensional table earlier, so I will explain it so that I can be convinced that three or more are okay. Assuming that there is a set $ A $, a set $ B $, and a set $ C $, the direct product set $ A × B × C $ is represented.
First, let $ P $ be the direct product set $ A x B $ of the set $ A $ and the set $ B $. The Cartesian product $ P $ is a set, so of course you can take a Cartesian product with other sets.
The Cartesian product of the set $ P $ and the set $ C $, $ P × C $, can be represented by a two-dimensional table.
As a concrete example, let's make a table of how to select targets A, B, and C. Each has a set with two elements, "choose (= 1)" and "do not choose (= 0)".
First, find $ P = A × B $.
This is shown in the table earlier.
| A\B | 0 | 1 |
|---|---|---|
| 0 | (0, 0) | (0, 1) |
| 1 | (1, 0) | (1, 1) |
That is, $ P = \ {(0, 0), (0, 1), (1, 0), (1, 1) \} $.
Next, $ P x C $ is represented by the following table.
| 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) |
(* Maybe $ P x C $ looks like ((0, 0), 0), but I don't care ...)
You should be convinced that you can get a Cartesian product for three or more sets. Of course, the same applies to objects that have a set such as $ \ {"choose" or "do not choose" \} $.
Example: All patterns of combinations that select targets A to F
It can be represented by the Cartesian product of $ A × B × C × D × E × F $.
Python has a function in the standard library that produces a Cartesian product. This is the product function of the ʻitertools` module.
The following is an implementation that enumerates and outputs all patterns of combinations that select A to 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)
output
[]
['F']
['E']
['E', 'F']
['D']
['D', 'F']
['D', 'E']
['D', 'E', 'F']
...(abridgement)...
['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']
Note that it is a Cartesian product set of the set $ \ {0, 1 \} $.
In this implementation, A to F "select" and "do not select" sets $ \ {0, 1 \} $ are prepared respectively, but all are the same as $ \ {0, 1 \} $ So using the product function keyword argument repeat makes it more concise.
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)
The output result is the same as above.
――Bit full search is a collection of all patterns of "select" and "do not select" for each target. —— A Cartesian product is a collection of all patterns in a set of elements taken one by one from two or more sets. --In bit full search, the target has a set with elements of "select" and "do not select". --If you take the direct product set of $ \ {"choose", "do not choose" \} $ for all targets, you will get all the patterns of "choose" and "do not choose" for each target. (= If you use it, you can search all bits)
There is also an article about full bit search by power set, so please have a look.
Easy bit full search (Easy power set)
Recommended Posts