Bit full search and direct product set

In this article, what is selected or not selected in the bit full search is called "target".

bit full search

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)

Cartesian product

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 $.

Bit full search and direct product set

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.

\\{0, 1\\} × \\{0, 1\\}(= \\{(0, 0), (0, 1), (1, 0), (1, 1)\\})

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 $.

Implementation by Python

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.

Summary

――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

Bit full search and direct product set
Easy bit full search (easy power set)
python bit full search
Confirm bit full search
Bit full search with Go
Full bit search with Python
Solve with Python [100 selected past questions that beginners and intermediates should solve] (010 --014 Full search: Bit full search)
Aggregate and analyze product prices using Rakuten Product Search API [Python]