Алгоритм для перечисления всех возможных способов прямоугольника можно разбить на n меньших прямоугольников

Смотрите название вопроса. Единственным другим ограничением является то, что меньшие прямоугольники должны быть сформированы путем погружения больших прямоугольников пополам. Я приложил результат для n = 3 и n = 4 ниже. Надеюсь, этого будет достаточно, чтобы объяснить смысл моих вопросов.

В настоящее время у меня есть неэффективный рекурсивный алгоритм, который делит каждый прямоугольник по горизонтали и вертикали и отслеживает все возможные комбинации в массиве. Мне не нравится этот алгоритм. Это полиномиальное время, кажется излишне сложным и дает мне дубликаты, как видно на рисунке n = 4 (подсказка: ищите четыре равных квадранта)

Мне было интересно, может ли быть лучшее решение для этого? Я экспериментировал с использованием 4-арного дерева (где каждый ребенок получает вертикальный или горизонтальный кусок), и я могу построить дерево, но получение всех возможных комбинаций из дерева, похоже, ускользает от меня. Я выложу код дерева котельной плиты ниже:

class Node:
    #value is an tuple (x0,y0,x1,y1)
    def __init__(self, value):
        self.horizontal = []
        self.vertical = []
        self.value = value
    def createTree(depth, currDepth, node):
        if currDepth == depth:
            return
        node.horizontal.append(Node(getLeftRect(node.value)))
        node.horizontal.append(Node(getRightRect(node.value)))
        node.vertical.append(Node(getTopRect(node.value)))
        node.vertical.append(Node(getBotRect(node.value)))
        createTree(depth, currDepth+1, node.horizontal[0])
        createTree(depth, currDepth+1, node.horizontal[1])
        createTree(depth, currDepth+1, node.vertical[0])
        createTree(depth, currDepth+1, node.vertical[1])

Любые предложения/помощь приветствуется!

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

Ответы

Ответ 1

Одна стратегия заключается в том, что, когда мы разрезаем по вертикали, не позволяйте обеим левым и правым частям горизонтального разреза. Это включает в себя анализ некоторых случаев.

В Python 3 мы сначала имеем типы данных для представления разделенных прямоугольников.

import collections

H = collections.namedtuple('H', ('top', 'bottom'))  # horizontal cut
V = collections.namedtuple('V', ('left', 'right'))  # vertical cut
W = collections.namedtuple('W', ())                 # whole rectangle

Вот генераторы.

def generate(n):
    assert isinstance(n, int) and n >= 0
    yield from generate_with_horizontal(n)
    yield from generate_without_horizontal(n)


def generate_with_horizontal(n):
    assert isinstance(n, int) and n >= 0
    for k in range(n):
        for top in generate(k):
            for bottom in generate(n - 1 - k):
                yield H(top, bottom)


def generate_without_horizontal(n):
    assert isinstance(n, int) and n >= 0
    if n == 0:
        yield W()
    for k in range(n):
        for left in generate_with_horizontal(k):
            for right in generate_without_horizontal(n - 1 - k):
                yield V(left, right)
        for left in generate_without_horizontal(k):
            for right in generate(n - 1 - k):
                yield V(left, right)

Ответ 2

Идея для рекурсивного или древовидного алгоритма, который позволяет избежать дубликатов:
Вы начинаете с прямоугольника, и несколько раз его нужно разделить. Разделите его в обоих направлениях и уменьшите число на единицу, а затем на каждое разделение (вертикальное и горизонтальное) разделите номер на две части.

Этот метод приводит к 39 делениям при делении на 4 части (и 1 дубликат).

Единственным дубликатом, которого я не смог избежать, является крест. Используя этот метод, всякий раз, когда у вас есть прямоугольник, который нужно разделить еще на 3 или более раз, вы будете дважды сталкиваться с крестом. Поэтому вам придется добавить дополнительную проверку.

Вы также заметите, что 4 группы из 8 растворов, возникающих в результате начального разбиения 2,0, являются поворотами друг друга на 90 °, 180 ° и 270 °. И 2 группы из 4 растворов, возникающих в результате начального разбиения 1,1, являются поворотными на 90 ° друг от друга. Таким образом, вы можете решить только одну группу, а затем повернуть, чтобы получить все решения.

Кажется, что дубликаты будут сложнее избежать с помощью этого метода, чем я думал. Если вы добавите еще 2 раздела, кажущиеся очень разными L3 R1 и T2 B2 основные параметры приводят к нескольким дубликатам. 4 шага дальше:

Как упоминает Дэвид Эйзенстат в своем ответе, вы можете избежать перекрестных двойников, разрешив обе половины прямоугольника делиться в один порядок (например, сначала вертикальный, затем горизонтальный), но не другой. Это означает, что при обработке прямоугольника вы должны знать, где находится его "другая половина", и как и как эта половина была разделена; что усложняет код, необходимый для использования этого метода.

Ответ 3

Здесь рекурсия в Python, которая сохраняет дерево в качестве словаря, где дети индексируются как 2i и 2i + 1. Я попытался реализовать предложение Дэвида Эйзенстата об избежании горизонтального раскола по обе стороны вертикального раскола (количество результатов, похоже, соответствует тем, которые он представил в комментариях).

from sets import Set

def f(n):
  results = []

  def _f(n,result,indexes):
    if n == 1:
      results.append(result)
      return

    for i in list(indexes):
      indexes.remove(i)

      parent = i // 2
      sibling = i - 1 if i & 1 else i + 1 
      left = 2 * i
      right = 2 * i + 1

      # add horizontal split

      if not (False if i < 2 else result[sibling] == 'H' and result[parent] == 'V'):
        result_h = result.copy()
        indexes_h = indexes.copy()

        result_h[i] = 'H'

        result_h[left] = result_h[right] = 'W'
        indexes_h.add(left)
        indexes_h.add(right)

        _f(n - 1, result_h, indexes_h)

      # add vertical split

      result_v = result.copy()
      indexes_v = indexes.copy()

      result_v[i] = 'V'

      result_v[left] = result_v[right] = 'W'
      indexes_v.add(left)
      indexes_v.add(right)

      _f(n - 1, result_v, indexes_v)

  _f(n,{1:1},Set([1]))
  return results

Результаты для f(4):

{1: 'H', 2: 'H', 3: 'H', 4: 'W', 5: 'W', 6: 'W', 7: 'W'}
{1: 'H', 2: 'H', 3: 'V', 4: 'W', 5: 'W', 6: 'W', 7: 'W'}
{1: 'H', 2: 'H', 3: 'W', 4: 'H', 5: 'W', 8: 'W', 9: 'W'}
{1: 'H', 2: 'H', 3: 'W', 4: 'V', 5: 'W', 8: 'W', 9: 'W'}
{1: 'H', 2: 'H', 3: 'W', 4: 'W', 5: 'H', 10: 'W', 11: 'W'}
{1: 'H', 2: 'H', 3: 'W', 4: 'W', 5: 'V', 10: 'W', 11: 'W'}
{1: 'H', 2: 'V', 3: 'H', 4: 'W', 5: 'W', 6: 'W', 7: 'W'}
{1: 'H', 2: 'V', 3: 'V', 4: 'W', 5: 'W', 6: 'W', 7: 'W'}
{1: 'H', 2: 'V', 3: 'W', 4: 'H', 5: 'W', 8: 'W', 9: 'W'}
{1: 'H', 2: 'V', 3: 'W', 4: 'V', 5: 'W', 8: 'W', 9: 'W'}
{1: 'H', 2: 'V', 3: 'W', 4: 'W', 5: 'H', 10: 'W', 11: 'W'}
{1: 'H', 2: 'V', 3: 'W', 4: 'W', 5: 'V', 10: 'W', 11: 'W'}
{1: 'H', 2: 'W', 3: 'H', 6: 'H', 7: 'W', 12: 'W', 13: 'W'}
{1: 'H', 2: 'W', 3: 'H', 6: 'V', 7: 'W', 12: 'W', 13: 'W'}
{1: 'H', 2: 'W', 3: 'H', 6: 'W', 7: 'H', 14: 'W', 15: 'W'}
{1: 'H', 2: 'W', 3: 'H', 6: 'W', 7: 'V', 14: 'W', 15: 'W'}
{1: 'H', 2: 'W', 3: 'V', 6: 'H', 7: 'W', 12: 'W', 13: 'W'}
{1: 'H', 2: 'W', 3: 'V', 6: 'V', 7: 'W', 12: 'W', 13: 'W'}
{1: 'H', 2: 'W', 3: 'V', 6: 'W', 7: 'H', 14: 'W', 15: 'W'}
{1: 'H', 2: 'W', 3: 'V', 6: 'W', 7: 'V', 14: 'W', 15: 'W'}
{1: 'V', 2: 'H', 3: 'V', 4: 'W', 5: 'W', 6: 'W', 7: 'W'}
{1: 'V', 2: 'H', 3: 'W', 4: 'H', 5: 'W', 8: 'W', 9: 'W'}
{1: 'V', 2: 'H', 3: 'W', 4: 'V', 5: 'W', 8: 'W', 9: 'W'}
{1: 'V', 2: 'H', 3: 'W', 4: 'W', 5: 'H', 10: 'W', 11: 'W'}
{1: 'V', 2: 'H', 3: 'W', 4: 'W', 5: 'V', 10: 'W', 11: 'W'}
{1: 'V', 2: 'V', 3: 'H', 4: 'W', 5: 'W', 6: 'W', 7: 'W'}
{1: 'V', 2: 'V', 3: 'V', 4: 'W', 5: 'W', 6: 'W', 7: 'W'}
{1: 'V', 2: 'V', 3: 'W', 4: 'H', 5: 'W', 8: 'W', 9: 'W'}
{1: 'V', 2: 'V', 3: 'W', 4: 'V', 5: 'W', 8: 'W', 9: 'W'}
{1: 'V', 2: 'V', 3: 'W', 4: 'W', 5: 'H', 10: 'W', 11: 'W'}
{1: 'V', 2: 'V', 3: 'W', 4: 'W', 5: 'V', 10: 'W', 11: 'W'}
{1: 'V', 2: 'W', 3: 'H', 6: 'H', 7: 'W', 12: 'W', 13: 'W'}
{1: 'V', 2: 'W', 3: 'H', 6: 'V', 7: 'W', 12: 'W', 13: 'W'}
{1: 'V', 2: 'W', 3: 'H', 6: 'W', 7: 'H', 14: 'W', 15: 'W'}
{1: 'V', 2: 'W', 3: 'H', 6: 'W', 7: 'V', 14: 'W', 15: 'W'}
{1: 'V', 2: 'W', 3: 'V', 6: 'H', 7: 'W', 12: 'W', 13: 'W'}
{1: 'V', 2: 'W', 3: 'V', 6: 'V', 7: 'W', 12: 'W', 13: 'W'}
{1: 'V', 2: 'W', 3: 'V', 6: 'W', 7: 'H', 14: 'W', 15: 'W'}
{1: 'V', 2: 'W', 3: 'V', 6: 'W', 7: 'V', 14: 'W', 15: 'W'}

Ответ 4

Итак, похоже, что существует несколько способов генерации всех неизоморфных возможностей, поэтому мое предложение было бы:

Сгенерировать их для некоторого количества мониторов.
Удалить дубликаты и сохранить результаты.
Когда вам это нужно, прочитайте из файла.

Дело в том, что если вам не нужен результат для больших входов (скажем, 6-10), вы не хотите генерировать их на лету. Даже если вы хотите показать результаты для такого размера раздела, это, безусловно, будет намного больше, чем вы могли бы с пользой показать пользователю!

Тем не менее, если вы хотите генерировать неизоморфные представители этих структур, есть интересное исследование "разрезанных двойников" - см., например, this магистерская диссертация Винсента Кустерса. Обратите внимание, что ваши структуры более общие, поскольку они включают разделы, которые встречаются при объединении с четырьмя.

Ответ 5

Это не прямой ответ на ваш вопрос, но вы должны рассмотреть его:

Будьте очень осторожны при использовании рекурсивного алгоритма для подсчета количества разделов при n> 4. Причина в том, что у нас может быть несколько разделов, в которых слияние NO двух прямоугольников заканчивается в другом прямоугольнике. Например, для пяти разделов рассмотрим следующее:

Картина здесь

Я думаю, что алгоритмы, предложенные выше, пропускают все разделы, подобные этому.