用於枚舉所有可能的方法的算法矩形可以分割成n個較小的矩形

Question

查看問題的標題。唯一的另一個限制是，較小的矩形必須通過將較大的矩形對準一半而形成。我附加了n = 3和n = 4以下的結果。希望這足以解釋我的問題的含義。

目前，我有一個效率低下的遞歸算法，它將每個矩形水平和垂直分開，並跟蹤數組中所有可能的組合。我不喜歡這種算法。這是多項式時間，似乎不必要的複雜，並給我重複，如在n = 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]) 

歡迎任何建議/幫助！

注意：這不是課程。我正在嘗試爲我正在製作的自定義虛擬監視器工具製作用戶界面。

Answer 1

理念爲遞歸或樹構建算法，避免了重複：
你用矩形開始，並多次有進行劃分。將它分爲兩​​個方向，並將數字減1，然後對每個分區（垂直和水平），將數字分成兩部分。

該方法導致39個區劃分成4份（與1個重複）時。

我無法避免的唯一副本是十字。使用這種方法，無論什麼時候你需要再劃分一個矩形3次或更多次，你會碰到兩次交叉。所以你必須添加一些額外的檢查。

您還會注意到，由最初的2,0分區產生的8組解決方案中的4組8個解決方案彼此的旋轉角度分別爲90°，180°和270°。並且由最初的1,1劃分產生的2組4個解彼此爲90°旋轉。因此，您只能解決一個組，然後旋轉以獲得所有解決方案。

---

似乎重複將很難避免用這種方法比我第一次想到的。如果添加了2個師，貌似很不同L3 R1和T2 B2主要選擇導致一些重複4個步驟進一步：

正如David Eisenstat提到了他的回答，您可以通過只允許雙方避免交叉雙打一個矩形的一半要按一個順序分割（例如第一個垂直，然後是水平）而不是另一個。這意味着在處理一個矩形時，你必須知道它的「另一半」在哪裏，以及是否以及如何劃分了這一半;所以使用這種方法所需的代碼變得複雜。

Answer 2

一種策略是，當我們垂直切割時，不要讓左半邊和右半邊都進行水平切割。這涉及一些案例分析。

在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) 

Answer 3

好了，所以它看起來像有一些方法來生成所有非同構的可能性，所以我的建議是：

1. 生成所有這些對於一些數量的顯示器。
2. 刪除重複項並存儲結果。
3. 當你需要它們時，從文件中讀取。

事情是，除非你需要大量輸入的結果（比如6-10），你不想在運行中產生它們。即使您確實想要顯示此分區大小的結果，它肯定會比您可以向用戶顯示的大得多！也就是說，如果你確實想要生成這些結構的非同構代表，有一些關於'可切片雙重'的有趣研究 - 例如參見Vincent Kusters的this masters thesis。請注意，雖然您的結構更一般，因爲它們包含以四連接相遇的分區。

Answer 4

以下是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'}