Bakteri kümelerini bulun

Question

Bir Python programında bağlı (4 bağlantı) tüm bakteri kümelerini bulmalıyım.

     ### 
        ##### 
        ####### 
        ####### 
        ###### 
        ###### ## 
        #### ##### 
         ## ######  #### 
        # ######  #### 
        ### ########## ##### 
       ####### #### ## ###### 
       ######### ## #  ##### 
     #   #### ###   ### 
    #####  #### #  ##  ## 
    #####     ###### # 
    ######     ######## 
    ####      ######## 
           ####### 
           ####### 

NOT:

Bu dosya Sınıfımdaki 2B dizi şeklinde kaydedilir sayılır olamaz ızgaranın kenarına bitişik olan Kümeleri girişi şöyle bir dosyadır . Bu işlevi tüm kümeleri bulmak için yazdım ancak birçok kümeye (5 yerine 22) neden oluyor. Neyi yanlış yaptığımı biliyor musun?

Kodum:

def findAll(self): 
    self.colonies = [set()] 
    for i in range(len(self.grid)): 
     for j in range(len(self.grid[i])): 
      if self.grid[i][j] == "#": 
       added = False 
       count = 0 
       for k in self.colonies: 
        if self.checkNeighbours((i, j), k): 
         k.add((i, j)) 
         added = True 
        count += 1 
       if not added: 
        self.colonies.append({(i, j)}) 

def checkNeighbours(self, pos, current): 
    return ((pos[0] + 1, pos[1]) in current 
      or (pos[0] - 1, pos[1]) in current 
      or (pos[0], pos[1] + 1) in current 
      or (pos[0], pos[1] - 1) in current) 

Answer 1

yaşadığınız sorun andan itibaren iki kümeleri meydana olmasıdır, bunları katılamadı. Sonunda, iki kümenin ara düğümlerin eklenmesiyle birleştirilmesi amaçlanmış olsa bile. Bu, union-find data structure numaralı bir uygulama ile çözülebilir. Bir unoptimized piton sürümü:

s = """\ 
        ###     \ 
        #####     \ 
        #######    \ 
        #######     \ 
        ######     \ 
        ###### ##    \ 
        #### #####   \ 
         ## ######  ####\ 
        # ######  #### \ 
        ### ########## ##### \ 
       ####### #### ## ###### \ 
       ######### ## #  ##### \ 
     #   #### ###   ### \ 
    #####  #### #  ##  ## \ 
    #####     ###### # \ 
    ######     ########  \ 
    ####      ########  \ 
           #######  \ 
           #######  \ 
""" 
representatives = {i: i for i, c in enumerate(s) if c == '#'} 
nrows, ncols = 19, 44 

def neighbours(idx): 
    i, j = divmod(idx, ncols) 
    if i > 0: yield idx - ncols 
    if i < nrows - 1: yield idx + ncols 
    if j > 0: yield idx - 1 
    if j < ncols - 1: yield idx + 1 

def representative(a): 
    while representatives[a] != a: a = representatives[a] 
    return a 

def join(a, b): 
    repr_a, repr_b = representative(a), representative(b) 
    if repr_a != repr_b: representatives[repr_a] = repr_b 

for idx in representatives: 
    for n in neighbours(idx): 
     if s[n] == '#': join(idx, n) 

cluster_count = len(set(map(representative, representatives))) 

Sonuç:

6 

Ayrıca da bir grafiği oluşturulur ve bağlı bileşenleri bulmak için depth first search kullanmış olabilir. Yukarıdaki yöntemin avantajı, artımlı olmasıdır ve yeni noktaları ekleyerek kümeleri kolayca güncelleyebilirsiniz.

Answer 2

Algılama özellikleri scipy ndimage measurements modülüyle kolayca yapılır. Bu şekilde giderseniz, hızın ek avantajı vardır. En üstteki ve alttaki bir:

import numpy as np 
from scipy.ndimage.measurements import label, find_objects 

q = np.genfromtxt('bacteria.txt', dtype='S1', comments=':', delimiter=1) 
arr = (q == b'#') # convert to boolean mask because ' ' evaluates to True 

labelled, num_features = label(arr) 

def count_edge_objects(labelled): 
    hulls = find_objects(labelled) 
    nbr_edgeobjects = 0 
    for rowslice, colslice in hulls: 
     if (rowslice.start == 0 or rowslice.stop == labelled.shape[0] or 
      colslice.start == 0 or colslice.stop == labelled.shape[1]): 
      nbr_edgeobjects += 1 
    return nbr_edgeobjects 

print('{} objects'.format(num_features - count_edge_objects(labelled))) 
# output: 
# 4 objects 

veri kümesi size kenarına yakın 2 nesneler vardır gösterdik. Şu anda veri kümesini her satırda eşit sayıda karaktere sahip olduğumu varsayarsak (eğer değilse np.genfromtxt'un missing_values seçeneğini kontrol edin)