user-touma
@user-touma

Are you sure you want to delete the question?

If your question is resolved, you may close it.

Leaving a resolved question undeleted may help others!

We hope you find it useful!

リスト内リストのうち共通要素をもつものを別リストにまとめる方法

リスト内リストのうち共通要素をもつものを別リストにまとめる方法

使用言語 Python 使用期間1か月ほど

知りたいこと
:リスト内リストのうち重複しているものを別リストにまとめる方法

始めた手でよくわかっていませんので、
私の立てた方針よりも効率が良い解法があればご教示をお願いしたいです
Pythonを始めてまだ1か月くらいでわからないことだらけです…

発生している問題・エラー

まず以下の問題が与えられて

「n*nの二次元配列にランダムに0か1が格納されているとき、
ある位置の要素についてその四近辺に同じ要素があれば同一領域とみなす
1の領域のうち最も大きい領域の面積を出力するプログラムをつくる」
例 五次元配列で
[[0 1 0 1 0]
 [0 0 0 0 1]
 [1 1 1 0 0]
 [1 1 1 1 0]
 [0 0 1 1 1]]
この場合最大領域面積は左下のあたりの10となる


その解決の方針として以下のように考えました
"""
①1の領域をみつける
②その領域が接しているマスの上下左右でで1を持つものの座標をまとめて一つのリストに格納
③全領域におこなう
④あるリストと、他のリストが共通項をもっていたらそれらを被りがないように統合
⑤かぶりがなくなるまで続ける
⑥リストのうち最も要素数がおおいものが答え
"""

③までは何とかかけたのですが(下記コード)、
④の共通項をもっていることの判別とそれらの統合がどうしてもできず
皆様のお力をお借りしたいです

例えば以下の五次元配列で
[[0 1 0 1 0]
 [0 0 0 0 1]
 [1 1 1 0 0]
 [1 1 1 1 0]
 [0 0 1 1 1]]

②の段階でこのようになったものを
[[(3, 0), (2, 1), (2, 0)], [(3, 1), (2, 2), (2, 0), (2, 1)], [(3, 2), (2, 1), (2, 2)], [(2, 0), (3, 1), (3, 0)], [(2, 1), (3, 2), (3, 0), (3, 1)], [(2, 2), (4, 2), (3, 3), (3, 1), (3, 2)], [(4, 3), (3, 2), (3, 3)], [(3, 2), (4, 3), (4, 2)], [(3, 3), (4, 4), (4, 2), (4, 3)], [(4, 3), (4, 4)]]

例えば初めの3つ
[(3, 0), (2, 1), (2, 0)]
[(3, 1), (2, 2), (2, 0), (2, 1)]
[(3, 2), (2, 1), (2, 2)]

は(2, 1)の共通項を持っている=隣接している と考えられるので
それぞれ重複のないように取り出して
[(3, 0),(3, 1), (2, 2), (2, 0), (2, 1),(3, 2)]
一つにリストにまとめたいとおもっています

改めて質問したいことは
一つのリストにまとめる方法

もしご都合がよろしければ
そもそもこのプログラム方針自体非効率極まりないと思っているので
まずどういう方針でプログラムを作る方が効率的だったか
教えていただきたいです

こちらも初投稿で
わからないことだらけではありますが
何卒宜しくお願い致します。




### 該当するソースコード
```Python
# n次元配列をつくる


class Board:
    def __init__(self):
        self.RawBoard = np.random.randint(0, 2, (raw,raw),dtype=int)
        self.number = 0
        self.list = []
        self.baselist = []
        self.subbaselist = []
        self.compactlist = []
    # raw = 作りたい配列の次元数をinputで入力

  #1を探す
    def find(self):
        for x in range(0, raw):
            for y in range(0,raw):
                if self.RawBoard[x,y] == 1:
                    self.list.append(x)
                    self.list.append(y)
                    self.number +=1

        print(self.number)
  #1のx,y座標をひとつづつリスト(subbaselist)に格納し、まとまったらbaselistに再格納
    def check(self):

        for i in range(self.number):
            x = int(self.list[2*i]) #x座標
            y = int(self.list[2*i+1]) #y座標
            # 0=<x=<raw-1 0=<y=<raw-1
            # 上
            if  (x>0) and (self.RawBoard[x-1,y] == 1):
                # もし上の座標にある値が1 かつ y座標が0より大きいなら
                self.subbaselist.append((x-1,y))
            # 下
            if (x<raw-1) and (self.RawBoard[x+1,y] == 1):
                self.subbaselist.append((x+1,y))
            # 右
            if (y<raw-1) and (self.RawBoard[x,y+1] == 1):
                # もし上の座標にある値が1 かつ y座標self.list[i+1]-1が0より大きいなら
                self.subbaselist.append((x,y+1))
            # 左
            if (y>0) and (self.RawBoard[x,y-1]) == 1:
                # もし上の座標にある値が1 かつ y座標self.list[i+1]-1が0より大きいなら
                self.subbaselist.append((x,y-1))
            # subbaselistの戸数が0個以上なら元座標を足して、ベースリストを作成
            if len(self.subbaselist) > 0:
                self.subbaselist.append((x, y))
                self.baselist.append(self.subbaselist)
                self.subbaselist = []

ここから作成途中でわからなくなった部分
    # def compact(self):
    #     self.compactlist =
    #
    #
    # def make(self):
    #     a = 1
    #     b = 1
    #     for x in self.baselist[a] :
    #         if x not in self.baselist[range(self.number)]:
    #         self.baselist[a].append(self.baselist[b])

#実行用メインコード
print("何次元配列にしますか?")
raw = int(input())
test = Board()
print(test.RawBoard)
test.find()
print(test.list)
test.check()
print(test.baselist)

### 自分で試したこと
ここに問題・エラーに対して試したことを記載してください。
    # def make(self):
    #     a = 1
    #     b = 1
    #     for x in self.baselist[a] :
    #         if x not in self.baselist[range(self.number)]:
    #         self.baselist[a].append(self.baselist[b])
ここでリスト内包表記?も試したのですが、よくわからず変な変数が入り混じっています…
1

2Answer

重複を消す手法1

例で示していただいた長いリスト内リスト,2次元配列をdim2として,

手法1-1
dim2 = [[(3, 0), (2, 1), (2, 0)], [(3, 1), (2, 2), (2, 0), (2, 1)], [(3, 2), (2, 1), (2, 2)], [(2, 0), (3, 1), (3, 0)], [(2, 1), (3, 2), (3, 0), (3, 1)], [(2, 2), (4, 2), (3, 3), (3, 1), (3, 2)], [(4, 3), (3, 2), (3, 3)], [(3, 2), (4, 3), (4, 2)], [(3, 3), (4, 4), (4, 2), (4, 3)], [(4, 3), (4, 4)]]

ret = list()
for dim1 in dim2:
	for value in dim1:
		if not value in ret:
			ret.append(value)
print(ret) # 重複なし

とすることで重複なし配列を得られます.重複確認をin演算子を用い,retの中にすでにvalueがあれば追加せず,valueが存在しなければretappendする.という感じです.

質問のタグにリスト内包表記ともあったので,そちらも示しておきます.

手法1-2
ret = list()
[ret.append(value) for dim1 in dim2 for value in dim1 if not value in ret]
print(ret) # 重複なし

残念ながら各ループでretに関して確認をしないといけないため,リスト内包表記で作ったリスト自体には何の意味もありません.が,上のように1行で書くことはできます.

2次元配列の状態で扱うのは紛らわしいので,一旦,1次元配列にしてから,重複するものは追加しないようにするように書くこともできます.

手法1-3
flatten = list() # 重複あり
for dim1 in dim2:
	flatten.extend(dim1)

ret = list() # 重複なし
for value in flatten:
	if not value in ret:
		ret.append(value)

以上の手法で重複を潰す際の計算量は,2次元配列の全要素の数を$N$として,$O(N^2)$です.
全ての要素に対して計算を行うので$O(N)$,やる計算はin演算で$O(N)$の計算量を持つのでこの積をとって$O(N^2)$です.

重複を消す手法2

Pythonの機能にある集合setを使う手法を提案します.

最初に示された長い2次元配列dim2に対して

手法2-1
dim2 = # 略

flatten = list() # 重複あり
for dim1 in dim2:
    flatten.extend(dim1)

ret = list(set(flatten)) # 重複なし

もできますし,標準で用意されているライブラリitertoolsを用いて,

手法2-2
from itertools import chain

dim2 = # 略

ret = list(set(chain.from_iterable(dim2))) # 重複なし

としても良いでしょう.また,例として3つ取り出している場合で言えば,上の動作は,+で配列を結合させるように書くこともできるので,

s1 = [(3, 0), (2, 1), (2, 0)]
s2 = [(3, 1), (2, 2), (2, 0), (2, 1)]
s3 = [(3, 2), (2, 1), (2, 2)]

s = list(set(s1 + s2 + s3)) # 重複なし

とすることもできます.

いずれにしても,set()にした時点で重複はないのですが,全体的にリストで扱われているので,最終的にはリストに戻すように書きました.

方針としてはいずれも,2次元配列の状態に対してflattenし,set()に変換して重複を潰させた上で,list()でリストに戻すような実装になります.

しかし,

⑥リストのうち最も要素数がおおいものが答え

という点を無視すれば,set()に対してlen()を使ってサイズを求めることもできますので,いちいちリストに戻すという実装は無くしても良さそうです.

手法1で言えばsize = len(set(ret)),手法2で言えばsize = len(set(chain.from_iterable(s)))でサイズがもとまります.

重複を潰す際の計算量は,flattenされた配列の長さを$N$として,$O(N{\rm log}N)$です.
処理は全てset()に任せましたが,内部では,集合setに対する追加演算add()が$O({\rm log}N)$で,全ての要素に対して行う$O(N)$ので,この積をとって$O(N{\rm log}N)$です.

そもそもこのプログラム方針自体非効率極まりないと思っているので
まずどういう方針でプログラムを作る方が効率的だったか

パッと見た感じ,計算量は下記のプログラムと変わらず$O(N^2)$で一緒なので,計算機科学,特に計算量理論の分野で言う「効率」は最善を尽くしています.

ただ,使っている配列のサイズや処理の量で言えば,定数倍で「非効率」な感じかと思います.
計算量理論において定数倍は無視されますが,実効的に無視して良いかどうかは場合によります.このプログラムが「非効率である」と言いたい場合には,この定数倍をできるだけ小さく出来そうである.という点から述べられることになりますね.

実装例

塗りつぶしのアルゴリズムで,FloodFillというものがあります.塗りつぶしていく中で塗りつぶしが終わるまでその塗りつぶした箇所をカウントアップすることができます.

また,今回の設計思想である「隣り合う場所を結合する」という思想を借りれば,UnionFindというデータ構造も提案できます.こちらも,同一領域にあるものの要素の個数を数え上げることができます.

過去には要素の数え上げはしていないものの,UnionFindを使って日本地図を塗りつぶした記事も書きました.

FloodFillを使った実装

RawBoardにおける1の場所を0で塗りつぶしていくという設計思想で実装します.
下で実装したFloodFillの実態は深さ優先探索なので,そちらを調べてみるのもありです.

import numpy as np

raw = 5
RawBoard = np.random.randint(0, 2, (raw, raw), dtype = int)

def FloodFill(x, y):
	count = 0
	stack = list()
	stack.append((x, y))
	RawBoard[x, y] = 0
	nexts = [[0, 1], [1, 0], [-1, 0], [0, -1]] # 上下左右への移動方向
	while len(stack):
		x, y = stack.pop()
		count += 1
		for _x, _y in nexts:
			nx, ny = x + _x, y + _y
			if (0 <= nx) and (nx < raw) and (0 <= ny) and (ny < raw) and RawBoard[nx, ny]:
				stack.append((nx, ny))
				RawBoard[nx, ny] = 0;
	return count

print(RawBoard)

ans = 0
for x in range(raw):
	for y in range(raw):
		if RawBoard[x, y]:
			ans = max(ans, FloodFill(x, y))

print(ans)

上のコードのwhile文のwhile len(stack):やif文のif RawBoard[x, y]:では比較演算が明記されていませんが,いずれも値が0であればFalse,それ以外の値がTrueとされる性質を用いて省略しています.
while len(stack):はリストstackのサイズが0より大きければ実行されますし,if RawBoard[x, y]:ではRawBoard[x, y]1であれば実行されるといった感じです.

この実装では,配列stackが新しく用意された程度で済んでおり,多数の配列を用意したuser-toumaさんのコードより定数倍で省容量,高速です.

深さ優先探索と計算量が同じなので,形式的にはグラフ$G=(V, E)$の頂点$V$の数$|V|$と辺$E$の数$|E|$を用いて$O(|V| + |E|)$になります.
今回の二次元配列RawBoardのサイズにおいては頂点数も辺の数もrawの2乗に比例するので,rawの大きさNを用いて計算量は$O(N^2)$と表すことができます.

2Like

Comments

  1. 文面とソースコードがどちらもコードブロックの中に収まってしまっています.
    今一度,体裁の確認をお願いします.

クラスにせずに、コメント順に処理してみました。
参考になることがあれば幸いです。

# n次元配列をつくる
board = [
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1],
    [1, 1, 1, 0, 0],
    [1, 1, 1, 1, 0],
    [0, 0, 1, 1, 1],
]

# 1. 1の領域を見つける
ones = [(x, y)
        for y, row in enumerate(board)
        for x, value in enumerate(row)
        if value == 1]

# 2. その領域が接しているマスの上下左右でで1を持つものの座標をまとめて一つのリストに格納
# 3. 全領域に行う
groups = [[(gx, gy)
           for gx, gy in [(x, y), (x, y-1), (x, y+1), (x-1, y), (x+1, y)]
           if 0 <= gy < len(board)
           if 0 <= gx < len(board[gy])
           if board[gy][gx] == 1]
          for x, y in ones]

# 4. あるリストと、他のリストが共通項をもっていたらそれらを被りがないように統合
# 5. かぶりがなくなるまで続ける
def merge(groups):
    areas = []
    for group in groups:
        for area in areas:
            if any(xy in area for xy in group):
                area |= set(group)  # 被りがないように統合
                areas = merge(areas)  # area同士のかぶりをなくす
                break
        else:  # breakしなかったとき
            areas.append(set(group))  # 被りがないグループとして追加
    return areas

areas = merge(groups)

# 6. リストのうち最も要素数がおおいものが答え
answer = max(map(len, areas))
print(answer)
1Like

Comments

  1. area同士がかぶることを考慮していなかったので、area同士のかぶりがなくなるまで続ける処理を追加しました

Your answer might help someone💌