Union Find木を使って問題を解く

前回記事で実装した Union Find木 を使って、下記の問題を解いてみます。

[問題]

人 1 から 人 N までのN 人の人がいます。

「人Ai と人 Bi は友達である」という情報が M 個与えられます。

同じ情報が複数回与えられることもあります。

X と Y が友達、かつ、Y と Z が友達ならば、X と Z も友達です。

また、M 個の情報から導くことができない友達関係は存在しません。

いじわるな高橋君は、このN人をいくつかのグループに分け、全ての人について「同じグループの中に友達がいない」という状況を作ろうとしています。

最小でいくつのグループに分ければ良いでしょうか？

[条件]

・人数Nは、2以上 200000以下です。

・友達関係の数Mは、0以上 200000以下です。

・AiとBiは、1以上 N以下です。

・AiとBiは、異なる数字です。

[解き方]
Union Find木 を使って友達同士のグループを作ります。

同じグループの中に友達がいない 状況を作るためには、友達の数が一番多いグループの人数分グループ数に分ければよいことになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

n = 5
lst = [(1, 2), (3, 4), (5, 1)]
#-----------入力２---------------
# n = 4
# lst = [(1, 2), (2, 1), (1, 2), (2, 1), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
#-----------入力３---------------
#n = 10
#lst = [(3, 1), (4, 1), (5, 9), (2, 6)]
#--------------------------------
uf = UnionFind(n)   # 前回記事で実装した「Union Find木」を使う

for l in lst:       # 友達関係から友達グループを作成する
    uf.union(l[0]-1, l[1]-1)

ans = 0             # 友達がいない状況をつくるためのグループ数
for g in uf.all_group_members().values():   # 友達グループごとにループ
    print(f'友達グループ', g)               # 友達グループのメンバー
    g_size = len(g)         # 友達の数
    # 友達の数が「友達がいない状況をつくるためのグループ数」より大きかったら
    if g_size > ans:
        ans = g_size        # グループ数に友達数を設定

print('答え =>', ans)

[実行結果（入力１の場合）]

友達グループ [0, 1, 4]
友達グループ [2, 3]
答え => 3

１つ目の友達グループが３人ともっとも人数が多いので、３グループに分ければよいことになります。

例えば｛0, 2｝｛1, 3｝｛4｝と分ければ、だれも友達がいないグループとなります。

[実行結果（入力２の場合）]

友達グループ [0, 1, 2, 3]
答え => 4

４人全員が友達なので、４グループに分けて全員をばらばらにする必要があります。

[実行結果（入力３の場合）]

友達グループ [0, 2, 3]
友達グループ [1, 5]
友達グループ [4, 8]
友達グループ [6]
友達グループ [7]
友達グループ [9]
答え 3

１つめの友達グループが３人ともっとも人数が多いので、３グループに分けます。

友達が２人の場合は、３グループのうちいずれかの２グループに振り分ければよいですし、友達がいない人は、３グループのどこに分けても友達関係はできません。

Union Find木

Union Find木 は、グループ分けを管理することができるデータ構造です。

次のようなことを効率的に行うことができます。

• 要素aと要素bが同じグループに属しているかどうかをチェックする。
• 要素aと要素bのグループを一つにまとめる。

グループ同士をまとめることはできますが、要素をグループから除いたり、グループを分けたりすることはできません。

Union Find木 を実現するためのクラスは以下のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

from collections import defaultdict

# n個の要素を0 ～ n - 1のインデックスで管理する
class UnionFind():
    def __init__(self, n):
        self.n = n                # 要素の数
        self.parents = [-1] * n   # 各要素の親要素の番号を格納するリスト

    def find(self, x):            # 要素[x]が属するグループの親を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):        # 要素[x]が属するグループと要素yが属するグループとを併合
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):            # 要素[x]が属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):         # 要素[x],要素[y]が同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):         # 要素[x]が属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):              # すべての親の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):        # グループの数を返す
        return len(self.roots())

    def all_group_members(self):  # 全グループの全要素を返す
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

    def __str__(self):  # printでの表示用。ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
        return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())

動作確認

実装した Union Find木 の動作を確認してみます。

要素数5個（0,1,2,3,4）のUnion Find木を定義し、[0,1]のグループと[2,3,4]のグループに分けます。

[Google Colaboratory]

1
2
3
4
5
6

uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
uf.union(3, 4)

print(uf)

[実行結果]

0: [0, 1]

2: [2, 3, 4]

２つのグループに分けることができました。

親の要素(一番もとになる要素)がグループのキーとなっていることが確認できます。

次に、要素1と要素3が所属するグループを調べてみます。

[Google Colaboratory]

1
2

print(uf.find(1))
print(uf.find(3))

[実行結果]

0

2

要素1がグループ0に所属し、要素3がグループ2に所属していることが分かりました。

今度は、要素0,要素2が同じグループに属するかどうかと、要素3,要素4が同じグループに属するかどうかを調べます。

[Google Colaboratory]

1
2

print(uf.same(0, 2))
print(uf.same(3, 4))

[実行結果]

False

True

要素0,要素2は違うグループであり、要素3,要素4は同じグループに属することを確認できました。

最後に、要素3が所属するグループの全要素を表示します。

[Google Colaboratory]

1

print(uf.members(3))

[実行結果]

[2, 3, 4]

要素3が所属するグループの全要素は、2,3,4であることが分かりました。

次回は、Union Find木 を使って問題を解いてみます。

線形計画問題

線形計画問題 は、ある条件下での 領域の最大・最小 を求める問題です。

数理最適化ライブラリのPuLP を使うと、線形計画問題 を解くことができます。

[問題]

ある工場では製品 p と製品 q を製造しています。

製品 p と製品 q を製造するには原料 m と原料 n が必要で、次のような条件となっています。

・製品 p を１ｋｇ製造するには原料 m が１ｋｇ、原料 n が２ｋｇ必要。

・製品 q を１ｋｇ製造するには原料 m が３ｋｇ、原料 n が１ｋｇ必要。

・原料 m の在庫は３０ｋｇ、原料 n の在庫は４０ｋｇあります。

・単位量当たりの利益は、製品 p が１万円、製品 q が２万円です。

この条件で利益を最大にするためには、製品 p と製品 q をそれぞれ何ｋｇ製造すればよいでしょうか。

製品 p の製造量を x ｋｇ、と製品 q の製造量を y ｋｇとすると以下のように不等号をつかった式にまとめることができます。

x + 3y ≦ 30
2x + y ≦ 40
x ≧ 0、y ≧ 0

連立方程式との違いは、等号（==） が 不等号（≧、≦） になっている点です。


 ソースコード

上記の条件式をもとにソースコードを作成すると下記のようになります。

[Google Colaboratory]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import pulp

# 第１引数は任意の名前、第２引数は最大化問題を解く指定
problem = pulp.LpProblem('Test', pulp.LpMaximize)

x = pulp.LpVariable('x')    # 製品pを製造する量。変数xをpulp.LpVariable関数を定義。
y = pulp.LpVariable('y')    # 製品qを製造する量。変数yをpulp.LpVariable関数を定義。

# 線形計画問題の条件式
problem += 1 * x + 3 * y <= 30
problem += 2 * x + 1 * y <= 40
problem += x >= 0
problem += y >= 0

problem += x + 2 * y        # 目的関数。最大化する式。

status = problem.solve()    # 数理モデルを解く

print('Status:', pulp.LpStatus[status])   # 結果
print('x =', x.value(), 'y =', y.value(), 'obj =', problem.objective.value()) # xとyの解と利益の関数値


[実行結果]
Status: Optimal

x = 18.0 y = 4.0 obj = 26.0


製品 p の製造量を １８ｋｇ、と製品 q の製造量を ４ｋｇとしたときに利益を最大にできることが導きだされました。
obj = 26.0 は最大化しようとした利益の関数値です。（15行目）
x + 2 * y = 26 となることが確認できます。

      
    

数理最適化

数理最適化ライブラリ PuLP を使って、連立一次方程式を解いてみます。

本来の数理最適化ライブラリの使い方とは少々異なりますが、数理モデルを初めて実装するにはとてもよい題材です。

[問題]

１個１２０円のリンゴと１個１５０円のミカンを合わせて１０個買ったら代金の合計が１４４０円でした。

リンゴとミカンをそれぞれ何個買ったでしょうか。

この問題は、リンゴの個数を x、ミカンの個数を y として連立一次方程式を立てることができます。

120x + 150y = 1440
x + y = 10

 ソースコード

まずは 数理最適化ライブラリ PuLP をインストールできます。

[Google Colaboratory]
1
!pip install pulp


連立一次方程式をソースコードにすると下記のようになります。

[Google Colaboratory]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import pulp

# 第１引数は任意の名前、第２引数は最大化問題を解く指定（今回は連立一次方程式を解くのでとくに意味はない）
problem = pulp.LpProblem('Test', pulp.LpMaximize)

x = pulp.LpVariable('x')    # 変数xをpulp.LpVariable関数を定義
y = pulp.LpVariable('y')    # 変数yをpulp.LpVariable関数を定義

problem += 120 * x + 150 * y == 1440    # 連立一次方程式を定義
problem += x + y == 10                  # 連立一次方程式を定義

status = problem.solve()    # 数理モデルを解く

print('Status:', pulp.LpStatus[status])   # 結果
print('x =', x.value(), 'y =', y.value()) # xとyの解


[実行結果]
Status: Optimal
x = 2.0 y = 8.0


Optimal は、最適化計算をした結果最適解が得られたという意味です。
リンゴの個数は2、ミカンの個数は8となり、合わせて１０個 であり、代金の合計も １４４０円 で、連立一次方程式の解として正しいことが確認できます。

      
    

部分和問題

深さ優先探索では、一番はじめの状態から遷移を繰り返すことで 全ての状態 を生成します。

したがって、すべての状態に対して操作 を施したり、全状態を列挙 することが可能です。

[問題]

整数が n個 与えられます。

その中からいくつか選び、その和をちょうど k にすることができるか判定してください。

[条件]

・整数の個数 n は、1以上20以下
・各整数の値は、-100000000以上100000000以下
・目標とする数値（部分和） k は、-100000000以上100000000以下

[解き方]
各整数を１つ目から順番に加えるかどうかを決めていき、n個すべてについて決め終わったら、その和が k に等しいかどうかを判定します。

再帰関数を使用します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# ------------ 入力例１ ----------
lst = [1, 2, 4, 7]    # 各要素
k = 13                # 目標とする数値（部分和）
# ------------ 入力例２ ----------
# lst = [1, 2, 4, 7]  # 各要素
# k = 15              # 目標とする数値（部分和）
# --------------------------------
def dfs(i, total):
    print(i,total)
    if i == len(lst):       # 全部決め終わった場合
        return total == k   # 今までの和が[目標とする数値]と等しいかどうかを返す
    
    if dfs(i + 1, total):   # lst[i]を使わない場合
        return True
    
    if dfs(i + 1, total + lst[i]):  # lst[i]を使う場合
        return True

    # lst[i]を使うか使わないかにかかわらず[目標とする数値]がつくれないので False を返す
    return False

if dfs(0, 0):
    print('Yes')
else:
    print('No')

[実行結果（入力例1）]

Yes

2 + 4 + 7 を足し合わせると 13 になるので Yes が解となります。

[実行結果（入力例2）]

No

どんな組み合わせを行っても 15 となることはないので No が解となります。

半分全列挙

全パターンを列挙することができないようなサイズの問題でも、半分ならば全列挙を行うことができる ような場合があります。

このような場合、それぞれ半分ずつ全列挙されたものを組み合わせるという手法が有効なことがよくあります。

[問題]

要素数nの整数のリストA、B、C、Dがあります。

各リストから１つずつ取り出したとき、その和が０となる ような
組み合わせの個数を求めなさい。

ただし、１つのリストに同じ値が複数個含まれている場合、
それらは異なるものとして数えます。

[条件]

・要素数は、1以上4000以下

・リストの値の絶対値は、2の28乗以下

[解き方]
４つのリストからの取り出し方は全部で nの4乗通り もあるため、全てを調べることはできませんが、リストをABとCDという 半分ずつの組に分けて 考えることにより、効率的に解くことが可能になります。

２つのリストからの取り出し方は nの2乗通り しかないため、これならば全パターン列挙することができます。

リストAとリストBからそれぞれa,bを取り出したときに和を０にするには、リストCとリストDからの取り出し方 nの2乗通り 全てについて、その和を全て算出しておくことにより検索しやすくなります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#--------入力例１----------------
n = 6
a = [-45,-41,-36,-36,26,-32]
b = [-16,30,77,-46,62,45]
c = [42,56,-37,-75,-10,-6]
d = [22,-27,53,30,-38,-54]
#--------------------------------
# リストCとリストDからの取り出し方の組を全部列挙
cd = [c1 + d1 for c1 in c for d1 in d]

cnt = 0
for a1 in a:        # リストAを全部列挙
    for b1 in b:    # リストBを全部列挙
        # リストCとリストDからの和がabとなるように取り出す
        ab = (a1 + b1)*-1
        if ab in cd:
            cnt += 1
print(cnt)

[実行結果]

5

結果としては、組み合わせ数 5 だけが表示していますが、ソースを少し修正すると和が０になるときの組み合わせを表示することができます。

[組み合わせ]

①-45 30 42 -27
②26 -46 -10 30
③-32 30 56 -54
④-32 77 -75 30
⑤-32 -46 56 22

興味がある方は、組み合わせを表示するようにソースコードを修正してみてください。

二分探索

二分探索 は、データ数が増えても 高速に検索 することができるアルゴリズムです。

辞書や電話帳から探すときに似た方法で、目的の値がそれよりも 前か後ろか を判断して探す方法です。

データは昇順に並んでいる必要があります。

ソースコード

二分探索 では、昇順に並んでいるデータの中から目的のデータが、真ん中より右にあるか左にあるかを調べる作業を繰り返します。

実装すると下記のようなソースになります。

リストの左端と右端から、探す位置を半分に絞り込みながら順に検索しています。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def binary_search(data, value):
    left = 0                      # 検索する範囲の左側を設定
    right = len(data) - 1         # 検索する範囲の右側を設定
    while left <= right:          # 検索する範囲がなくなるまで実行
        mid = (left + right) // 2 # 検索する範囲の中央の値を算出
        if data[mid] == value:    # 中央の値と一致した場合
            return mid            # その位置を返す
        elif data[mid] < value:   # 中央の値より大きい場合
            left = mid + 1        # 検索範囲の左側を移動
        else:                     # 中央の値より小さい場合
            right = mid - 1       # 検索範囲の右側を移動
    return -1                     # 見つからなかったので-1を返す

data = [10,20,30,40,50,60,70,80,90]

print('値が見つかるケース１ =>', binary_search(data,80))
print('値が見つかるケース２ =>', binary_search(data,20))
print('値が見つかるケース３ =>', binary_search(data,60))
print('値が見つからないケース１ =>', binary_search(data,9))
print('値が見つからないケース２ =>', binary_search(data,23))
print('値が見つからないケース３ =>', binary_search(data,91))

[実行結果]

値が見つかるケース１ => 7
値が見つかるケース２ => 1
値が見つかるケース２ => 5
値が見つからないケース１ => -1
値が見つからないケース２ => -1
値が見つからないケース３ => -1

値が見つかった場合はその インデックス を、見つからなかった場合は -1 を返すことを確認できました。

ユークリッドの互除法

ユークリッドの互除法 は２つの自然数の 最大公約数 を効率的に求めることができるアルゴリズムです。

ユークリッドの互除法 は、次の定理に基づいており、その名の通り除法つまり 割り算 を繰り返して計算しています。

[定理]

２つの自然数 a, b について、a を b で割ったときの商 q、余りを r とすると、
a と b の最大公約数 は b と r の最大公約数 に等しい。

例として、a=1274、b=975 の場合、次のように 最大公約数 を求めることができます。

(1) 1274 ÷ 975 = 1 余り 299
(2) 975 ÷ 299 = 3 余り 78
(3) 299 ÷ 78 = 3 余り 65
(4) 78 ÷ 65 = 1 余り 13
(5) 65 ÷ 13 = 5 余り 0

ソースコード

上記の例をコードにすると下記のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7

# ユークリッドの互除法
def gcd(a, b):
    while b != 0:         # 余りが0になるまで繰り返す
        a, b = b, a % b   # [割る数]と[割られる数]を入れ替え、[余り]を[割る数]に代入
    return a              # 最大公約数を返す(余りが0になったときの[割る数])

print(gcd(1274, 975))

[実行結果]

13

効率的に 最大公約数 を求めることができました。