三重ループを使わずにコードをかきなおしたい。

下記の二次元配列のインプットデータに対して、縦横に隣接する数字の塊を一つとしてカウントするコードを三重ループを利用せずにかきたいと思っています。
例えば、4という数字は、4つの塊があります。　5という数字は、1つしかないので1つの塊です。

もし、こうできそう、この辺リファクタできるとよくなりそうなどのアドバイス頂けますと助かります。

input data

python
1A = [
2    [5,4,4], 
3    [4,3,4], 
4    [3,2,4], 
5    [2,2,2], 
6    [3,3,4], 
7    [1,4,4], 
8    [4,1,1]
9]

output data

コード

python
1# calculate max values
2import numpy as np
3max_value = np.amax(A) +1  # 5

python
1# mapping the indexies of each value
2r_length = len(A[0])
3c_length = len(A)
4
5map = {}
6for n in range(1,max_value):
7    ind = []
8    for i in range(c_length):  # 行
9        for j in range(r_length):  # 列
10            if A[i][j] == n: 
11                ind.append([j, i])
12                map[n] = ind
13
14# map
15#{1: [[0, 5], [1, 6], [2, 6]],
16# 2: [[1, 2], [0, 3], [1, 3], [2, 3]],
17# 3: [[1, 1], [0, 2], [0, 4], [1, 4]],
18# 4: [[1, 0], [2, 0], [0, 1], [2, 1], [2, 2], [2, 4], [1, 5], [2, 5], [0, 6]],
19# 5: [[0, 0]]}

python
1count = 0
2for v in map.values():
3    length = len(v)
4    static_length = len(v)
5    for i in range(1, static_length):
6        first = v[i-1]
7        dynamic_length  = len(v[i:])
8        for i in range(1, dynamic_length):
9            next = v[i]
10            if first[0] == next[0]:
11                if first[1] == next[1] + 1 or first[1] == next[1] - 1:
12                    length -= 1
13
14            if first[1] == next[1]:
15                if first[0] == next[0] + 1 or first[0] == next[0] - 1:
16                    length -= 1
17
18            if first[0] == next[1]:
19                if first[1] == next[0] + 1 or first[1] == next[0] - 1:
20                    length -= 1
21
22            if first[1] == next[0]:
23                if first[0] == next[1] + 1 or first[0] == next[1] - 1:
24                    length -= 1
25                    
26    count+=length
27
28# count
29# 11

Soei

2020/12/04 03:35 編集

リファクタの前に、このコードは正しく動作しますか? A = [ [1,1,1], [1,1,1], [1,1,1] ] とした場合、私の手元ではcountの値は-11になりました。

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

回答2件

scipyにndimage.labelという機能があります。
これを使用すると、0以外の数字が隣接している場合に一つの塊とみなして塊の数をカウントすることができます。
scipy.ndimage.labelの説明

ndimage.labelをそのまま使用すると、1〜5全てが1つの塊になってしまうので、以下のように処理します。
0. 元々の配列Aに含まれるユニークな要素iを抽出する(この例では [1, 2, 3, 4, 5]の5種類)
0. ユニークな値それぞれについて、以下の処理を行なう

配列の値がiの部分は1、それ以外は0にしたマスクデータを用意する
このマスクデータをndimage.labelで処理して塊の数をカウントする

全ての要素での塊の数を合計したものが求める答えになります。

python
1from scipy.ndimage import label
2import numpy as np
3
4A = [
5    [5,4,4],
6    [4,3,4],
7    [3,2,4],
8    [2,2,2],
9    [3,3,4],
10    [1,4,4],
11    [4,1,1]
12]
13
14arr = np.array(A)
15
16ans = 0                         # 塊の数のトータル
17for i in np.unique(arr):        # 元データに含まれるユニークな要素を順番に処理
18    mask = arr == i             # 現在注目する値のみを残して他を0にしたマスクを作成
19    res, num = label(mask)      # マスクを使って塊の数を確認
20    ans += num
21    print(f'値が{i}の塊')
22    print(res)
23    print('=' * 20)
24print(f'トータルの塊の数: {ans}\n')
25
26
27# 欲しいのはlabelが返すnumの部分だけなので、以下のように1行にまとめて書くこともできます
28ans2 = sum(map(lambda i: label(arr == i)[1], np.unique(arr)))
29print(ans2)

出力結果

text
1値が1の塊
2[[0 0 0]
3 [0 0 0]
4 [0 0 0]
5 [0 0 0]
6 [0 0 0]
7 [1 0 0]
8 [0 2 2]]
9====================
10値が2の塊
11[[0 0 0]
12 [0 0 0]
13 [0 1 0]
14 [1 1 1]
15 [0 0 0]
16 [0 0 0]
17 [0 0 0]]
18====================
19値が3の塊
20[[0 0 0]
21 [0 1 0]
22 [2 0 0]
23 [0 0 0]
24 [3 3 0]
25 [0 0 0]
26 [0 0 0]]
27====================
28値が4の塊
29[[0 1 1]
30 [2 0 1]
31 [0 0 1]
32 [0 0 0]
33 [0 0 3]
34 [0 3 3]
35 [4 0 0]]
36====================
37値が5の塊
38[[1 0 0]
39 [0 0 0]
40 [0 0 0]
41 [0 0 0]
42 [0 0 0]
43 [0 0 0]
44 [0 0 0]]
45====================
46トータルの塊の数: 11

投稿2020/12/01 11:55

退会済みユーザー

総合スコア0

sequelanonymous

2020/12/03 17:41

ご回答ありがとうございます。ご参考にさせていただきます。 numpyとscipyを利用しない場合、バブルソートを利用してできないかなと思っています。

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

Python
1for n in range(1,max_value):
2    ind = []
3    for i in range(c_length):  # 行
4        for j in range(r_length):  # 列
5            if A[i][j] == n: 
6                ind.append([j, i])
7                map[n] = ind

これは、次のように書き換えられます。ループは一つです。

Python
1n = 1
2i = 0
3j = 0
4ind = []
5while True:
6	if A[i][j] == n:
7		ind.append([j, i])
8		map[n] = ind
9	j += 1
10	if j == r_length:
11		j = 0
12		i += 1
13		if i == c_length:
14			i = 0
15			n += 1
16			if n > max_value:
17				break
18			ind = []

ただし、ループが 0回の場合がある時は、ちょっと変更が必要です。

追記
二重ループはいいんですよね。

Python
1a = [
2    [5, 4, 4], 
3    [4, 3, 4], 
4    [3, 2, 4], 
5    [2, 2, 2], 
6    [3, 3, 4], 
7    [1, 4, 4], 
8    [4, 1, 1]
9]
10r = len(a)
11c = len(a[0])
12b = [ [0] * c for i in range(r) ] 
13k = 0
14
15def proc(i, j):
16	if i >= 0 and i < r and j >= 0 and j < c and a[i][j] == n and b[i][j] == 0:
17		b[i][j] = k
18		proc(i-1, j)
19		proc(i, j-1)
20		proc(i, j+1)
21		proc(i+1, j)
22
23for i in range(r): 
24	for j in range(c):
25		if b[i][j] == 0:
26			k += 1
27			n = a[i][j]
28			proc(i, j)
29print(k)
30print()
31for e in a: print(e)
32print()
33for e in b: print(e)