二次元リスト内の各要素を比較したい

Question

前提・実現したいこと

N行N列の二次元リストの各要素を比較し、上下左右の要素より大きい要素を出力したいです。
上下左右に要素がない場合は、その方向より大きかったとみなします。

発生している問題・エラーメッセージ

エラーメッセージは解決したものの、4/10ケースで出力結果が間違っています。

教えて頂きたいこと

より簡単に、エラーを起こしにくい書き方があれば教えて頂きたいです。
以下のコードは上下左右の要素と比較する関数を定義し、インデックスの値を変化させながら関数を実行しています。比較して大きかった場合のみカウンタを+1し、カウンタが4になった(=上下左右の要素より大きかった)要素をリストに格納しました。
エラーを解決しながらコードを書き、100分近くかかってしまっています。
それ自体は勉強になって良いのですが、より良い他の書き方が思いつきません。

該当のソースコード

x = 0
y = 0
# 以降のaは2次元リストで、全ての要素はint型です
def r(a):  # 右の要素と比較
    if y + 1 < N:
        return a[x][y] - a[x][y + 1]
    else:
        return a[x][y]
def l(a):  # 左の要素と比較
    if 0 < y:
        return a[x][y] - a[x][y - 1]
    else:
        return a[x][y]
def t(a):  # 上の要素と比較
    if x - 1 > 0:
        return a[x][y] - a[x - 1][y]
    else:
        return a[x][y]
def u(a):  # 下の要素と比較
    if x + 1 < N:
        return a[x][y] - a[x + 1][y]
    else:
        return a[x][y]

while y < N:
    while x < N:
        count = 0
        cul = r(a)
        if cul > 0:
            count +=1
        cul = l(a)
        if cul > 0:
            count +=1
        cul = t(a)
        if cul > 0:
            count +=1
        cul = u(a)
        if cul > 0:
            count += 1
        if count == 4:
            high.append(a[x][y])
        x += 1
    x = 0
    y += 1

どんな細かい点でもご指摘頂けると幸いです。

Answer 1

scipy.ndimage.maximum_filter()を使うと任意の範囲の中の最大値を算出してくれます。

import numpy as np
from scipy import ndimage

A = np.array([[3, -9, 10, 6],
              [2, 6, -3, -8],
              [9, -7, 7, -8]])

FP = [[0, 1, 0],
      [1, 1, 1],
      [0, 1, 0]]

filtered = ndimage.maximum_filter(A, footprint=FP)
print(filtered)
# [[ 3 10 10 10]
#  [ 9  6 10  6]
#  [ 9  9  7  7]]

out = A[ndimage.maximum_filter(A, footprint=FP) == A]

print(out)  # -> [ 3 10  6  9  7]

Comments

[退会済みユーザー]

ご回答ありがとうございます！そんな便利なものが有るのですね、まだscipyには手を出せていなかったので勉強になります。以下、理解が合っているか確認して頂けるととても助かります。
引数のfootprintは、
・FPのように3行3列のnumpy配列で構成されるもので、要素は0または1
・入力配列の各要素に対して、FP[1,1]を各要素とし、1としたところを範囲とする
・入力配列の各要素が任意の範囲をとれない(A[0,0]で上と左の要素が存在しない等)場合でも、範囲をとれた部分(A[0,0]なら右と下)のみを範囲とする

また、out = A[]とすることで、bool型がTrueであるAの要素をoutに代入していることは分かったのですが、[]の最後の == Aは何を意味しているのか分かりません。お時間がございましたら教えていただけますか？よろしくお願いいたします。

[kirara0048]

この十字のFPでmaximum_filter()を使うと、「Aの各値が『自身・上隣・下隣・左隣・右隣のうち、最も大きい値』に変換された配列」が返されます。

今回、取り出す条件が「上下左右と比較して大きい値」ですから、つまり「自身・上隣・下隣・左隣・右隣のうち、最も大きい値」が「自身の値」と一致しているものを取りせばよいので、`.maximum_filter(~~) == A`を行ってインデックスを取得しています。

[退会済みユーザー]

丁寧で分かりやすい説明をありがとうございます。
また、コードも編集してくださったのでより理解しやすくなりました。
使える知識となるよう復習いたします。
この度はありがとうございました！

Answer 2

自分ならこうやりますかの〜ゆうん書いときますう。
最初にゆうときますけど、ワテ、便利なものは使いまくって楽したい派なんで、NumPy 使わせてもらいますわ。

それから問題のとらえ方やけど、たとえば、M=3、N=4として、3行4列の行列（に相当する二次元リスト）A が

[
 [ 3, -9, 10, 6],
 [ 2, 6, -3, -8],
 [ 9, -7, 7, -8]
]

というものであったとして、Aから以下のような、同じく3行4列の行列Bを得る問題として考えることにするで。

[
  [True, False, True, False],
  [False, True, False, False],
  [True, False, True, False]
]

つまり、Bの要素はbool値で、Aの同じ位置の要素が題意を満たしていればTrue、満たしていなければFalse になっとるゆう行列ですわ。こないなBをAから作るコードとして、こんなん思いついたで。

import numpy as np

# 行および列の数
M, N = 3, 4

# M行N列の二次元配列Aを作る。
A = np.array([
 [ 3, -9, 10, 6],
 [ 2, 6, -3, -8],
 [ 9, -7, 7, -8]
])


# 一次元配列 ary を受け取り、aryの各要素が、先頭要素であるか、もしくは左（ひとつ前）の要素より大きいかを示すブール値の配列を返す関数
def check_left(ary):
    return [i == 0 or x > ary[i-1] for (i, x) in enumerate(ary)]

# 一次元配列 ary を受け取り、aryの各要素が、末尾の要素であるか、もしくは右（次）の要素より大きいかを示すブール値の配列を返す関数
def check_right(ary):
    return [i == len(ary)-1 or x > ary[i+1] for (i, x) in enumerate(ary)]


# Bの初期値を設定（値がすべてTrueのM×N行列）
B = np.ones((M, N), dtype=bool)

# Aに対して、行方向および列方向それぞれに、check_leftおよびcheck_rightを適用した行列Cを得て、BとCの論理積を、Bに代入するループ
for axis in [0, 1]:
  for checker in [check_left, check_right]:
    C = np.apply_along_axis(checker, axis, A)
    B = np.logical_and(B, C)


# 結果の出力
print(B)
print()

for i, row in enumerate(B):
  for j, check in enumerate(row):
    if check:
      print(f'A({i}, {j}): ', A[i,j])

上のコード実行すると、

[[ True False True False]

[False True False False]
[ True False True False]]

A(0, 0): 3

A(0, 2): 10
A(1, 1): 6
A(2, 0): 9
A(2, 2): 7

ゆう出力になりますわ。ほな〜。

補足： まあ、ゆうてNumPy使わんでも、

def check(i, j, a):
  return (
    (i == 0 or a[i][j] > a[i-1][j]) 
    and 
    (i == M-1 or a[i][j] > a[i+1][j])
    and
    (j == 0 or a[i][j] > a[i][j-1])
    and
    (j == N-1 or a[i][j] > a[i][j+1])
  )


for i  in range(M):
  for j in range(N):
    if check(i, j, A):
      print(f'A({i}, {j}): ', A[i][j])

でもええわいね。

Comments

[退会済みユーザー]

ご回答ありがとうございます！NumPyを使わないコードは理解できました。題意を満たすか判定したbool値のリストを得るという問題の捉え方をすれば、これだけすっきりしたコードが書けるのですね！
NumPyのコードの以下の部分があまり理解できなかったので、もう少し教えて頂けませんか？

# Aに対して、行方向および列方向それぞれに、check_leftおよびcheck_rightを適用した行列Cを得て、BとCの論理積を、Bに代入するループ
for axis in [0, 1]: #? 行(0)、列(1)方向の順に処理を行・列単位で行わせる？
for checker in [check_left, check_right]:
C = np.apply_along_axis(checker, axis, A)
#? Aに対して、check_leftおよびcheck_rightを適用したbool値checkerを行・列単位で行列Cに代入？
引数axisの意味するものは?
B = np.logical_and(B, C)
#? Cを出力してみたのですが、何ができたのか理解できません、ですので値が全てTrueのBとの論理積を取る意味も理解できませんでした

また、for x in の最後にはfor下の処理を適用したい範囲を書くものと思っていたので、[0,1]や[check_left, check_right]が書かれていると何をしているのか分からないです。

質問攻めにして申し訳ございません。お時間がございましたらご回答頂けると大変嬉しく思います。よろしくお願いいたします。

Answer 3

機能(関数)分割がうまくないなと感じました。
最終的には suwmn50799さんのコードでみんな納得するのではないでしょうか。

さて、とりあえず分割を見直したコード

N = 3  # 1..30
# 以降のaは2次元リストで、全ての要素はint型です (1..1000)
a = [
    [1,2,3],
    [4,5,6],
    [7,8,9]
]
high = []

def check4(a,x,y):
        count = 0
        # 右の要素と比較
        if y + 1 < N:
            cul = a[x][y] - a[x][y + 1]
        else:
            cul = a[x][y]
        if cul > 0:
            count += 1
        # 左の要素と比較
        if 0 < y:
            cul = a[x][y] - a[x][y - 1]
        else:
            cul = a[x][y]
        if cul > 0:
            count += 1
        # 上の要素と比較
        if x - 1 > 0:
            cul = a[x][y] - a[x - 1][y]
        else:
            cul = a[x][y]
        if cul > 0:
            count +=1
        # 下の要素と比較
        if x + 1 < N:
            cul = a[x][y] - a[x + 1][y]
        else:
            cul = a[x][y]
        if cul > 0:
            count += 1
        return count
 
x = 0
y = 0
while y < N:
    while x < N:
        if check4(a,x,y) == 4:
            high.append(a[x][y])
        x += 1
    x = 0
    y += 1
print(high)

で、最終的に欲しいのは(countでなく)比較結果なので

N = 3  # 1..30
# 以降のaは2次元リストで、全ての要素はint型です (1..1000)
a = [
    [1,2,3],
    [4,5,6],
    [7,8,9]
]
high = []

def check4(a,x,y):
        # 右の要素と比較
        if y + 1 < N:
            if a[x][y] <= a[x][y + 1]:
                return False
        # 左の要素と比較
        if 0 < y:
            if a[x][y] <= a[x][y - 1]:
                return False
        # 上の要素と比較
        if x - 1 > 0:
            if a[x][y] <= a[x - 1][y]:
                return False
        # 下の要素と比較
        if x + 1 < N:
            if a[x][y] <= a[x + 1][y]:
                return False
        return True
 
x = 0
y = 0
while y < N:
    while x < N:
        if check4(a,x,y):
            high.append(a[x][y])
        x += 1
    x = 0
    y += 1
print(high)

ループも range() 使った方が手間がへりますね。

Comments

[退会済みユーザー]

ご回答ありがとうございます。
他の方の回答にもあったように、条件との合致をbool値で判断するという考え方があれば、簡潔な書き方ができるのですね。
教えて頂いたコードで試してみたところ、4/10ケースで出力結果が間違っていたようです。おそらく私が前提条件をお伝えし損ねているからだと思いますので、再考してみます。
この度はありがとうございました！

[takasima20]

(･∀･)b

Answer 4

この書き方だと、全ての要素が負の整数である場合は一つも見つかりませんね。
それぞれの関数がTrueかFalseを返すようにすれば、このバグは修正できます。

Comments

[退会済みユーザー]

ご回答ありがとうございます。
失礼しました。前提条件を忘れておりました。
・1 ≦ N ≦ 30
・1 ≦ 各要素の値 ≦ 1,000
したがって、ご指摘頂いたような要素が負であるためにより生じているエラーではないと考えております。
もし他に思いつくエラーの原因がございましたら教えて頂けますか？