Как проверить, образуют ли элементы (координаты) множества непрерывную форму? - PullRequest
Новая
       31

Как проверить, образуют ли элементы (координаты) множества непрерывную форму?

0 голосов
/ 10 марта 2020

Я пытаюсь написать функцию, которая получает набор кортежей в качестве параметра и проверяет, образуют ли данные символы непрерывную форму в сетке NxN. Кортежи - это индексы символов в списках, которые образуют сетку. Форма является непрерывной, если персонаж находится непосредственно под, над или по бокам другого символа. 

continuous             not continous         not continous
  xxxxx                   xxxxx                 ooxxx   
  xxoox                   xxoox                 xxxxx
  xxxoo                   ooxxx                 xxoox 
  xxxoo                   oxxxx                 xxoox
  xxxxo                   xoxxx                 xxxxx

======================== 

    def connected(characters):
        result = True
        for i in characters:
            if (i[0]+1, i[1]) in characters or (i[0]-1, i[1]) in characters or (i[0], i[1]+1) in characters or (i[0], i[1]-1) in characters:
                result = True
                characters.discard(i)
            else:
                result = False
                return result
        return result

>>>connected({(1, 3), (2, 1), (2, 3), (0, 3), (1, 1)})

будет формировать эту форму, поэтому она не будет не будет непрерывным, но мой код думает, что это так. 

xxxo
xoxo
xoxo
xxxx

Это работает в большинстве случаев, но не работает, когда данные символы образуют две отдельные непрерывные фигуры, как 2-й неправильный пример, который я привел выше. Я попытался решить эту проблему, удалив каждый кортеж после того, как он был проверен, но я получаю ошибку 

Traceback (most recent call last):
  File "C:/Users/User/PycharmProjects/untitled6/venv/1.py", line 47, in <module>
    connected({(1, 2), (1, 3), (2, 2), (0, 3), (0, 4)})
  File "C:/Users/User/PycharmProjects/untitled6/venv/1.py", line 15, in connected
    for i in grid:
RuntimeError: Set changed size during iteration

. Что я могу сделать, чтобы решить эту проблему?

1 Ответ

1 голос
/ 12 марта 2020

Подробнее об ошибке см. { ссылка }. По сути, вам нужно перебрать копию набора, если вы хотите изменить этот набор в l oop.

Кроме этого, в вашем алгоритме есть изъян.

Если вы не сбрасываете текущий символ, вы проверяете, есть ли у каждого персонажа сосед. Все будет в порядке: 

xxxxx
xoxox
xoxox
xxxxx

Но если вы отбросите текущий символ, у вас могут быть сюрпризы: 

 xxx            xxx
 xox <- cur     x x <- discarded
 xox            xox <- has no neighbor!
 xxx            xxx

Алгоритм classi c основан на обходе дерева: start от любого нет и пройти все напрямую связанные узлы. Если все узлы были видны, график соединен.

Я использую DFS здесь, но вы можете использовать BFS , если хотите: 

def connected(characters):
    seen = set()
    stack = [next(iter(characters))] if characters else []
    while stack:
        c = stack.pop()
        seen.add(c)
        for other_c in [(c[0]+1, c[1]), (c[0]-1, c[1]), (c[0], c[1]+1), (c[0], c[1]-1)]:
            if other_c not in seen and other_c in characters:
                stack.append(other_c)

    return not (characters - seen)

print(connected({(1, 3), (2, 1), (2, 3), (0, 3), (1, 1)}))
# False
print(connected({(1, 3), (2, 1), (2, 3), (0, 3), (1, 1), (1, 2)}))
# True
...