バイナリ配列で直角三角形を見つける

Question

MxNバイナリマトリックスがあります。必ずしも疎ではありません。私は、配列内のすべての直角三角形の頂点の座標を見つけることに興味があります。直角三角形とは、つまり、行列の1またはTrueの値が三角形の頂点であり、0またはFalse要素がnullであるとふりまとうことです。次に、直角三角形は、直角三角形を視覚的に形成する配置である。頂点とは、三角形の直角に対応する頂点を意味します。例えば。次の5x6アレイでは：

0 0 1 0 1 0 
0 1 0 0 0 0 
1 0 0 1 0 1 
0 0 1 0 0 0 
0 0 0 0 0 0 

直角三角形は1つのみです。頂点を持つ三角形： （0,2）は頂点、（3,2）は左下、（0,4）は右上、ここでは0からインデックスを作成します。 [Pythonの索引付け]を残しました。所与のMxNアレイについて

---

、Iは各サブアレイはアレイ内の直角三角形の頂点の座標対であるサブアレイのアレイLを返すPython関数F（A）を、望みます。配列の同じ要素が複数の三角形の頂点である場合、最終的にはユニークなサブ配列が必要になりますが、今のところ関数はそれらを複製できます。一例として、上記アレイAのために、F（A）は、配列Lを返す= [0,2]

---

私の最初の思想は、行と列の和を使用することであろう。行sum> = 2の行は調べる価値があり、次にsum> = 2という列を使用します。次に、交差点を見つけるための効率的な方法が必要になります。私は、この方法や、より速くて速い他の方法を使用している関数に興味があります。

{例。これに代わる方法として、グラフ理論の観点から考えることができます。行と列は2つのグラフのノードになります（行は1組、列はもう1組）。次に、ここに示す行列は、完全二分グラフの隣接行列の1象限になります。言い換えれば、行ノードと他の行ノードに接続していないため、内部セット部分はすべて0になるため、行セットと列セットの間のクロス項の一部にすぎません。列ノードにのみ適用されます。この観点から、直角三角形は二部グラフの長さ3のパスのように見えます。私は行列のアプローチが簡単だと思いますが、私はここでどのアルゴリズムにもオープンしています。}

Answer 1

はい、私はあなたがこれを熟考していると信じています。行と列の合計を生成し、交差する各配列の位置を確認します。

私は構文をテストしていませんが、それはこのようなものになります。

# Generate row and column sums 
row_sums = (sum(A[M]) for M in range(len(A))) 
col_sums = (sum([A[M, N] for M in range(len(A))] for N in range len(A[0])) 

# Now, check each element in the array for being a vertex 
vertices = 
    [(row, col) if A[row, col] and row_sums[row] > 1 
           and col_sums[col] > 1 
      for row in range(len(A)) for col in range(len(A[0]))] 

# You now have a list of all solutions, with no duplicates.