Pythonで再帰呼び出しを並列して実行する方法

Python初心者です。再帰関数を用いて二次元リストの隣接する要素をグループ分けするコードを書きたいのですが上手くいきません。

例えば

Python
1H, W = 4, 4  # グリッドのサイズ
2
3select = [[0, 1, 0, 1],
4          [1, 1, 1, 0],
5          [0, 0, 0, 1],
6          [0, 1, 1, 1]]

上のような二次元リストがあった場合、

Python
1grp = [[0, 1, 0, 2],
2       [1, 1, 1, 0],
3       [0, 0, 0, 3],
4       [0, 3, 3, 3]]

という風に、リスト selectに対応したリスト grpで独立したグループに数字を割り振っていくといった処理をしたいです。

実際に書いてみたコード

Python
1import itertools
2
3H, W = 4, 4  # グリッドのサイズ
4
5def determine_next(h, w):
6    grp[h][w] = gp
7    
8    # 上に隣接する要素があった場合
9    if h >= 1 and grp[h-1][w] == 0 and select[h-1][w] == 1:
10        return determine_next(h-1, w)
11    # 左に隣接する要素があった場合
12    if w >= 1 and grp[h][w-1] == 0 and select[h][w-1] == 1:
13        return determine_next(h, w-1)
14    # 下に隣接する要素があった場合
15    if h < H-1 and grp[h+1][w] == 0 and select[h+1][w] == 1:
16        return determine_next(h+1, w)
17    # 右に隣接する要素があった場合
18    if w < W-1 and grp[h][w+1] == 0 and select[h][w+1] == 1:
19        return determine_next(h, w+1)
20
21select = [[0, 1, 0, 1],
22          [1, 1, 1, 0],
23          [0, 0, 0, 1],
24          [0, 1, 1, 1]]
25
26grp = [[0 for _ in range(W)] for _ in range(H)]  # グループ初期化
27c = itertools.count(1)
28
29for i in range(H):
30    for j in range(W):
31        if grp[i][j] == 0 and select[i][j] == 1:
32            gp = next(c)
33            determine_next(i, j)
34
35for i in grp:
36    print(i)

ネストした for文でリストの要素を左上から順番に調べ、グループが振り分けられて無い select[i][j] = 1の要素があった場合、そこを起点として再帰関数 determine_nextで隣接した要素を連続的に同じグループに分ける処理を書きました。

問題点

隣接した要素が複数あると再帰関数中の if returnが最初の一つしか実行されず、その結果上手く分類ができません。

実行結果

console
1[0, 1, 0, 2]
2[1, 1, 3, 0]
3[0, 0, 0, 4]
4[0, 4, 4, 4]

grp[1][2]が想定していた 1ではなく 3になってしまっている。

質問

再帰関数で複数の returnがあった場合、それらすべてを並列で実行したい場合はどのようにすればいいでしょうか。またグループ分けの処理をもっと最適化することはできるでしょうか。初めての質問なのでお見苦しい点などがありましたら申し訳ありません。

行動規範の内容に同意します

回答1件

ベストアンサー

隣接した要素が複数あると再帰関数中の if returnが最初の一つしか実行されず、

determine_next 関数は、以下の様になるのではないでしょうか。

python
1def determine_next(h, w):
2    grp[h][w] = gp
3    # 上に隣接する要素があった場合
4    if h >= 1 and grp[h-1][w] == 0 and select[h-1][w] == 1:
5        determine_next(h-1, w)
6    # 左に隣接する要素があった場合
7    if w >= 1 and grp[h][w-1] == 0 and select[h][w-1] == 1:
8        determine_next(h, w-1)
9    # 下に隣接する要素があった場合
10    if h < H-1 and grp[h+1][w] == 0 and select[h+1][w] == 1:
11        determine_next(h+1, w)
12    # 右に隣接する要素があった場合
13    if w < W-1 and grp[h][w+1] == 0 and select[h][w+1] == 1:
14        determine_next(h, w+1)

余談

またグループ分けの処理をもっと最適化することはできるでしょうか。

最適化ではありませんが、Scipy パッケージの scipy.ndimage.label メソッドで同様の処理を行うことができます。

scipy.ndimage.label — SciPy v1.9.1 Manual

python
1from scipy.ndimage import label
2import numpy as np
3
4arr = np.array([
5    [0, 1, 0, 1],
6    [1, 1, 1, 0],
7    [0, 0, 0, 1],
8    [0, 1, 1, 1],
9])
10
11lw, num = label(arr)
12print(lw)
13
14#
15[[0 1 0 2]
16 [1 1 1 0]
17 [0 0 0 3]
18 [0 3 3 3]]

投稿2022/10/04 05:48

編集2022/10/04 06:21

melian

総合スコア19703

scarlet256

2022/10/04 08:37

なるほど！そもそも `return`を使う必要が無かったのですね……考えてみたら確かに返り値で取得する必要はないですよね……。初心者用サイトに書かれていた基本例を改変して組み込んだので気づきませんでした！`scipy.ndimage.label`メソッドも非常に有用そうで助かります。教えていただきありがとうございました！！

行動規範の内容に同意します