The implementation of full bit search using bit operation is a little heavy. The bit full search itself is no different from the full search of the power set, so based on the idea of enumerating each subset of the power set, any programming language (Python, Ruby, Rust, etc.) that has a library that enumerates combinations It can be easily implemented. This article will introduce its implementation.
A power set is a set that is newly created from a given set as a whole of its subset in mathematics.
Bit full search is a method of searching all patterns of a subset of a set.
A combination can be expressed by expressing the set as a bit array, setting 1 when selecting a certain element and 0 when not selecting it.
Combination example: Select B, C, E from A to F
A | B | C | D | E | F |
---|---|---|---|---|---|
0 | 1 | 1 | 0 | 1 | 0 |
If you collect all the patterns of the combinations listed in the bit full search, it will be just a power set.
I want to invite some of my N friends to an online drinking party. However, I don't want to have a bad group. Find the maximum number of people you can invite.
Example
Friends I want to invite |
---|
Alice |
Bob |
Charlie |
Dave |
Elizabeth |
Bad friends |
---|
Alice,Charlie |
Alice,Elizabeth |
Charlie,Dave |
Combination example
Alice | Bob | Charlie | Dave | Elizabeth | OK? |
---|---|---|---|---|---|
○ | ○ | × | ○ | × | Yoshi |
○ | × | ○ | × | ○ | No good |
× | × | ○ | ○ | ○ | No good |
List all the combinations of friends you invite. Find a combination that is not bad for you. The maximum number of people in the combination is output.
We will use the theme of this article, "Easy bit full search". In other words, it is a simple enumeration of each subset of the power set.
There are already many very easy-to-understand articles about bit full search using bit operation, so please refer to that.
https://drken1215.hatenablog.com/entry/2019/12/14/171657 --Kenchon-san https://qiita.com/gogotealove/items/11f9e83218926211083a-@gogotealove https://qiita.com/hareku/items/3d08511eab56a481c7db-@ hareku
In this article, I will show you how to easily enumerate power sets.
First, a power set is a set that is a collection of subsets of a set.
It enumerates all combinations when selecting 0 pieces, all combinations when selecting 1 piece, all combinations when selecting 2 pieces, ..., and all combinations when selecting N pieces from a set with N elements. You can do it if you go.
Python has a library (combinations
) that lists combinations, so you can easily implement it. In addition to Python, most programming languages that have a library that lists combinations such as Ruby and Rust are possible.
Below is an implementation example in Python.
from itertools import combinations
friends = ["Alice", "Bob", "Charlie", "Dave", "Elizabeth"]
dislike_pairs = [{"Alice", "Charlie"}, {"Alice", "Elizabeth"}, {"Charlie", "Dave"}]
#A function that determines if there are any bad pairs
def ok(comb):
comb_set = set(comb)
return not any(pair.issubset(comb_set) for pair in dislike_pairs)
ans = 0
#Easy bit full search
for i in range(len(friends)+1):
for comb in combinations(friends, i):
if ok(comb):
ans = max(ans, i)
print(ans)
The main lines of this article are:
#Easy bit full search
for i in range(len(friends)+1):
for comb in combinations(friends, i):
if ok(comb):
...
The combinations for selecting 0 pieces from the set with N elements, the combination for selecting 1 piece, the combination for selecting 2 pieces, ..., and the combination for selecting N pieces are listed respectively.
Since each subset of the power set is listed in these few lines, it means that a full bit search is performed.
--bit full search is a full search of power set --In order to enumerate each subset of the power set, enumerate 0 to N combinations respectively. --Easy to implement in any programming language that has a library that lists combinations
Recommended Posts