[PYTHON] Easy bit full search (easy power set)

Introduction

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.

Power set

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

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

If you collect all the patterns of the combinations listed in the bit full search, it will be just a power set.

Realistic problem example

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

Combination example

policy

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.

Method

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.

Easy bit full search

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.

Summary

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

Task

1. Let's solve the problem of online drinking party by bit search using bit operation.
2. Online drinking party problems can be greatly reduced in calculation by pre-processing. For example, ** no one is on bad terms with Bob **, so you can invite him in advance. Since the computational complexity of bit full search is $ O (2 ^ N) $, the computational complexity can be greatly reduced if N is decremented by 1. Let's solve this problem by adding a process that repels friends who have no bad friends in advance.
3. The problem of online drinking parties is ** the problem of finding a combination that meets the constraints , so it can be said to be a small " constraint satisfaction problem ". Such a problem can be found more efficiently than a full bit search by a depth-first search called " backtrack method **". Let's solve it with the backtrack method.