生成由 10 个正交连接点形成的所有可能形状的最有效方法是什么？
What is the most efficient way to generate all possible shapes formed by 10 orthogonally connected points?
我需要在 2D space 中生成 10 个点的所有有效组合。
在这种情况下，有效的形状意味着：
- 所有点都相互连接，不允许对角线连接。
- 如果我们围绕点绘制外边界，则形状内部不应有空点。
以下是一些有效和无效组合的示例：
我尝试了几种算法，但它们都效率低下并且需要太多时间来计算。生成和存储所有有效组合的最有效方法是什么？
出于衍生式设计目的，我需要它。组合代表建筑平面图中房间的形状。
首选语言是 Python.
我不确定你想做什么，但我认为你可以通过以下方式生成所有由 10 个点组成的形状：
从任意一个像素开始，标记它并尝试在四个主要方向上移动；
在下一个像素处，标记它并尝试在四个主要方向上移动，前提是像素未标记；
继续递归，直到达到允许的像素数。如果你到达了初始像素的邻居，你就有了一个有效的形状；
当递归回溯时，取消标记您要离开的像素。
如果你不想复制90°旋转对称的副本，只在一个方向移动第一个就足够了。
作为一个可能有用的优化，您可以通过避免移动使得 return 不可能（曼哈顿距离太大）来避免远离初始像素的路径。
下面的代码打印了通过正交连接 n 个点可以构成的所有可能结构。对于您的用例来说，它非常有效，对于 n=10，它在我的笔记本电脑上运行了大约 4 秒，并进行了有效性检查（房间内没有间隙）。基于 n=8、9、10、11 的 运行 时间，似乎时间复杂度为 O(4^n)，这在给定四个基本方向的情况下是有道理的。
想法是先放置一个点，然后反复考虑我们可以放置点的位置，以便仍然满足任何约束。在每一步，我们都会考虑结构中之前没有考虑过的任何点的外边界，并考虑用我们剩下的任意数量的点填充这些空间的所有可能组合。
房间内没有缝隙的约束通过深度优先搜索验证，该搜索来自刚选择的点旁边的空单元格。如果在 DFS 期间的任何时候它到达墙壁或已经走得足够远，那么它是有效的。
这是代码（yield from 和 f-string 需要 Python 3.6+）：
# -*- coding: utf-8 -*-
"""
02 Aug 2019
Generate all possible floorplans.
"""
# Import statements
from __future__ import print_function, division
import sys
from argparse import ArgumentParser
from pprint import pprint
from itertools import combinations
def neighbors(row, col):
"""Generate all neighbors of a point"""
result = []
for dir_row, dir_col in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
new_row, new_col = row+dir_row, col+dir_col
result.append((new_row, new_col))
return result
def generate_structures(n):
"""Main generator to generate structures that can be formed from n orthogonally connected
points."""
# Setup the grid
# The first point is assumed to be the left-most point, and among the left-most,
# it is the top-most. This prevents duplicate structures, since all structures have a
# unique left-most top-most point.
grid = [['.']*n for _ in range(2*n-2)]
for r in range(len(grid)):
grid[r].append('X')
grid[r].insert(0, 'X')
grid.append(['X']*(n+2))
grid.insert(0, ['X']*(n+2))
row, col = n-1, 1
for r in range(row):
grid[r][1] = 'X'
grid[row][col] = 'O'
yield from _generate_structures(grid, n-1, [(row, col)], (row, col), n-1)
def _generate_structures(grid, n, last_points, source, max_dist):
"""Recursive function to generate all possible structures with n points remaining,
where last_points are the points last added.
The source and max_dist are used in validation check, to make it slightly faster.
"""
if n == 0:
# No more points to be placed, return the current structure
yield grid
raise StopIteration
def get_expansion(points, charset='.'):
"""Get all points around selected points, with the given character set."""
expansion = set()
for row, col in points:
if grid[row][col] != 'O':
# Only expand from points
continue
for new_row, new_col in neighbors(row, col):
if grid[new_row][new_col] not in charset:
continue
expansion.add((new_row, new_col))
expansion = list(sorted(expansion))
return expansion
expansion = get_expansion(last_points)
# For all possible number of points that can be assigned to the boundary
# of the last added points (1 to n)
for i in range(1, n+1):
# Consider all the possible combinations (number of empty space choose
# number of points)
for combination_indices in combinations(range(len(expansion)), i):
includeds = [False]*len(expansion)
included_points = []
for included_index in combination_indices:
includeds[included_index] = True
for included, (row, col) in zip(includeds, expansion):
if included:
grid[row][col] = 'O'
included_points.append((row, col))
else:
grid[row][col] = 'X'
to_be_checked = get_expansion(included_points, '.X')
if valid(grid, to_be_checked, source, max_dist-n+1):
# If valid (there are no isolated empty cells, for example),
# then continue expanding the boundary.
yield from _generate_structures(grid, n-len(included_points), included_points,
source, max_dist)
for row, col in expansion:
grid[row][col] = '.'
def valid(grid, points, source, max_dist):
"""Check the points given, whether they are isolated.
The source and max_dist helps in early termination of the check, by checking whether
we have been far enough that it is impossible for walls to form.
"""
def distance(point):
return abs(point[0]-source[0]) + abs(point[1]-source[1])
if len(points) == 0:
return True
for check_point in points:
stacked = set()
stack = []
if check_point in stacked:
continue
stacked.add(check_point)
stack.append(check_point)
current_is_valid = False
while len(stack) > 0:
row, col = stack.pop()
if (row == 0 or col == 0 or row == len(grid)-1 or col == len(grid[0])-1 or
distance((row, col)) >= max_dist):
# From this check_point it is valid, check other points
current_is_valid = True
break
cur_neighbors = []
for new_row, new_col in neighbors(row, col):
if grid[new_row][new_col] == 'O' or (new_row, new_col) in stacked:
# Skip selected points and points that are already in the stack
continue
stacked.add((new_row, new_col))
cur_neighbors.append((new_row, new_col))
# Prioritize the furthest point from the origin
cur_neighbors = sorted(cur_neighbors, key=distance)
stack.extend(cur_neighbors)
if not current_is_valid:
return False
return True
def simplify(structure):
"""Removes empty rows and columns, compacting the display
"""
structure = structure[:]
for i in range(len(structure)):
structure[i] = list(''.join(structure[i]).replace('X', '.'))
for row_idx in reversed(range(len(structure))):
row = structure[row_idx]
if len(row) == row.count('.'):
# All empty, remove
structure[row_idx:row_idx+1] = []
for col_idx in reversed(range(len(structure[0]))):
empty = True
for row_idx in range(len(structure)):
if structure[row_idx][col_idx] != '.':
empty = False
break
if empty:
for row in structure:
row[col_idx:col_idx+1] = []
return structure
def main():
parser = ArgumentParser(description='Generate all possible floorplans')
parser.add_argument('-n', type=int, help='The number of points')
args = parser.parse_args()
max_n = args.n
with open(f'floorplans-{max_n}.txt', 'w') as outfile:
for struct_id, structure in enumerate(generate_structures(max_n)):
structure = simplify(structure)
outfile.write(f'Structure ID: {struct_id}\n')
outfile.write('\n'.join(''.join(row) for row in structure))
outfile.write('\n\n')
if __name__ == '__main__':
main()
对于 n=10，有 39,425 个不同的平面图。
对于 n=5，它打印以下 63 个结构：
Structure ID: 0
.O
.O
.O
OO
Structure ID: 1
.OO
.O.
OO.
Structure ID: 2
..O
.OO
OO.
Structure ID: 3
.OOO
OO..
Structure ID: 4
.O.
.OO
OO.
Structure ID: 5
..O
..O
OOO
Structure ID: 6
..OO
OOO.
Structure ID: 7
...O
OOOO
Structure ID: 8
OOOOO
Structure ID: 9
OOOO
...O
Structure ID: 10
OOO.
..OO
Structure ID: 11
OOO
..O
..O
Structure ID: 12
..O.
OOOO
Structure ID: 13
..O
OOO
..O
Structure ID: 14
OOOO
..O.
Structure ID: 15
OO..
.OOO
Structure ID: 16
OO.
.OO
..O
Structure ID: 17
OO
.O
OO
Structure ID: 18
OO.
.O.
.OO
Structure ID: 19
OO
.O
.O
.O
Structure ID: 20
OO.
.OO
.O.
Structure ID: 21
.O.
.O.
OOO
Structure ID: 22
.OO
OOO
Structure ID: 23
.O..
OOOO
Structure ID: 24
.O.
OOO
..O
Structure ID: 25
.O
.O
OO
.O
Structure ID: 26
.OO
OO.
.O.
Structure ID: 27
.O.
OO.
.OO
Structure ID: 28
.O
OO
.O
.O
Structure ID: 29
..O
OOO
.O.
Structure ID: 30
OOOO
.O..
Structure ID: 31
OOO
.OO
Structure ID: 32
OOO
.O.
.O.
Structure ID: 33
.O.
OOO
.O.
Structure ID: 34
O.O
OOO
Structure ID: 35
O...
OOOO
Structure ID: 36
O..
OOO
..O
Structure ID: 37
O..
OO.
.OO
Structure ID: 38
O.
OO
.O
.O
Structure ID: 39
O..
OOO
.O.
Structure ID: 40
O..
O..
OOO
Structure ID: 41
O.
O.
OO
.O
Structure ID: 42
O.
O.
O.
OO
Structure ID: 43
O
O
O
O
O
Structure ID: 44
O.
O.
OO
O.
Structure ID: 45
O..
OOO
O..
Structure ID: 46
O.
OO
OO
Structure ID: 47
O.
OO
O.
O.
Structure ID: 48
.O
.O
OO
O.
Structure ID: 49
.OO
OO.
O..
Structure ID: 50
..O
OOO
O..
Structure ID: 51
OOOO
O...
Structure ID: 52
OOO
O.O
Structure ID: 53
OO.
OOO
Structure ID: 54
OO
OO
.O
Structure ID: 55
OO
O.
OO
Structure ID: 56
OO
O.
O.
O.
Structure ID: 57
.O.
OOO
O..
Structure ID: 58
.O
OO
OO
Structure ID: 59
.O
OO
O.
O.
Structure ID: 60
OOO
OO.
Structure ID: 61
OOO
O..
O..
Structure ID: 62
OO
OO
O.
我需要在 2D space 中生成 10 个点的所有有效组合。
在这种情况下，有效的形状意味着：
- 所有点都相互连接，不允许对角线连接。
- 如果我们围绕点绘制外边界，则形状内部不应有空点。
以下是一些有效和无效组合的示例：
我尝试了几种算法，但它们都效率低下并且需要太多时间来计算。生成和存储所有有效组合的最有效方法是什么？
出于衍生式设计目的，我需要它。组合代表建筑平面图中房间的形状。 首选语言是 Python.
我不确定你想做什么，但我认为你可以通过以下方式生成所有由 10 个点组成的形状：
从任意一个像素开始，标记它并尝试在四个主要方向上移动；
在下一个像素处，标记它并尝试在四个主要方向上移动，前提是像素未标记；
继续递归，直到达到允许的像素数。如果你到达了初始像素的邻居，你就有了一个有效的形状；
当递归回溯时，取消标记您要离开的像素。
如果你不想复制90°旋转对称的副本，只在一个方向移动第一个就足够了。
作为一个可能有用的优化，您可以通过避免移动使得 return 不可能（曼哈顿距离太大）来避免远离初始像素的路径。
下面的代码打印了通过正交连接 n 个点可以构成的所有可能结构。对于您的用例来说，它非常有效，对于 n=10，它在我的笔记本电脑上运行了大约 4 秒，并进行了有效性检查（房间内没有间隙）。基于 n=8、9、10、11 的 运行 时间，似乎时间复杂度为 O(4^n)，这在给定四个基本方向的情况下是有道理的。
想法是先放置一个点，然后反复考虑我们可以放置点的位置，以便仍然满足任何约束。在每一步，我们都会考虑结构中之前没有考虑过的任何点的外边界，并考虑用我们剩下的任意数量的点填充这些空间的所有可能组合。
房间内没有缝隙的约束通过深度优先搜索验证，该搜索来自刚选择的点旁边的空单元格。如果在 DFS 期间的任何时候它到达墙壁或已经走得足够远，那么它是有效的。
这是代码（yield from 和 f-string 需要 Python 3.6+）：
# -*- coding: utf-8 -*-
"""
02 Aug 2019
Generate all possible floorplans.
"""
# Import statements
from __future__ import print_function, division
import sys
from argparse import ArgumentParser
from pprint import pprint
from itertools import combinations
def neighbors(row, col):
"""Generate all neighbors of a point"""
result = []
for dir_row, dir_col in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
new_row, new_col = row+dir_row, col+dir_col
result.append((new_row, new_col))
return result
def generate_structures(n):
"""Main generator to generate structures that can be formed from n orthogonally connected
points."""
# Setup the grid
# The first point is assumed to be the left-most point, and among the left-most,
# it is the top-most. This prevents duplicate structures, since all structures have a
# unique left-most top-most point.
grid = [['.']*n for _ in range(2*n-2)]
for r in range(len(grid)):
grid[r].append('X')
grid[r].insert(0, 'X')
grid.append(['X']*(n+2))
grid.insert(0, ['X']*(n+2))
row, col = n-1, 1
for r in range(row):
grid[r][1] = 'X'
grid[row][col] = 'O'
yield from _generate_structures(grid, n-1, [(row, col)], (row, col), n-1)
def _generate_structures(grid, n, last_points, source, max_dist):
"""Recursive function to generate all possible structures with n points remaining,
where last_points are the points last added.
The source and max_dist are used in validation check, to make it slightly faster.
"""
if n == 0:
# No more points to be placed, return the current structure
yield grid
raise StopIteration
def get_expansion(points, charset='.'):
"""Get all points around selected points, with the given character set."""
expansion = set()
for row, col in points:
if grid[row][col] != 'O':
# Only expand from points
continue
for new_row, new_col in neighbors(row, col):
if grid[new_row][new_col] not in charset:
continue
expansion.add((new_row, new_col))
expansion = list(sorted(expansion))
return expansion
expansion = get_expansion(last_points)
# For all possible number of points that can be assigned to the boundary
# of the last added points (1 to n)
for i in range(1, n+1):
# Consider all the possible combinations (number of empty space choose
# number of points)
for combination_indices in combinations(range(len(expansion)), i):
includeds = [False]*len(expansion)
included_points = []
for included_index in combination_indices:
includeds[included_index] = True
for included, (row, col) in zip(includeds, expansion):
if included:
grid[row][col] = 'O'
included_points.append((row, col))
else:
grid[row][col] = 'X'
to_be_checked = get_expansion(included_points, '.X')
if valid(grid, to_be_checked, source, max_dist-n+1):
# If valid (there are no isolated empty cells, for example),
# then continue expanding the boundary.
yield from _generate_structures(grid, n-len(included_points), included_points,
source, max_dist)
for row, col in expansion:
grid[row][col] = '.'
def valid(grid, points, source, max_dist):
"""Check the points given, whether they are isolated.
The source and max_dist helps in early termination of the check, by checking whether
we have been far enough that it is impossible for walls to form.
"""
def distance(point):
return abs(point[0]-source[0]) + abs(point[1]-source[1])
if len(points) == 0:
return True
for check_point in points:
stacked = set()
stack = []
if check_point in stacked:
continue
stacked.add(check_point)
stack.append(check_point)
current_is_valid = False
while len(stack) > 0:
row, col = stack.pop()
if (row == 0 or col == 0 or row == len(grid)-1 or col == len(grid[0])-1 or
distance((row, col)) >= max_dist):
# From this check_point it is valid, check other points
current_is_valid = True
break
cur_neighbors = []
for new_row, new_col in neighbors(row, col):
if grid[new_row][new_col] == 'O' or (new_row, new_col) in stacked:
# Skip selected points and points that are already in the stack
continue
stacked.add((new_row, new_col))
cur_neighbors.append((new_row, new_col))
# Prioritize the furthest point from the origin
cur_neighbors = sorted(cur_neighbors, key=distance)
stack.extend(cur_neighbors)
if not current_is_valid:
return False
return True
def simplify(structure):
"""Removes empty rows and columns, compacting the display
"""
structure = structure[:]
for i in range(len(structure)):
structure[i] = list(''.join(structure[i]).replace('X', '.'))
for row_idx in reversed(range(len(structure))):
row = structure[row_idx]
if len(row) == row.count('.'):
# All empty, remove
structure[row_idx:row_idx+1] = []
for col_idx in reversed(range(len(structure[0]))):
empty = True
for row_idx in range(len(structure)):
if structure[row_idx][col_idx] != '.':
empty = False
break
if empty:
for row in structure:
row[col_idx:col_idx+1] = []
return structure
def main():
parser = ArgumentParser(description='Generate all possible floorplans')
parser.add_argument('-n', type=int, help='The number of points')
args = parser.parse_args()
max_n = args.n
with open(f'floorplans-{max_n}.txt', 'w') as outfile:
for struct_id, structure in enumerate(generate_structures(max_n)):
structure = simplify(structure)
outfile.write(f'Structure ID: {struct_id}\n')
outfile.write('\n'.join(''.join(row) for row in structure))
outfile.write('\n\n')
if __name__ == '__main__':
main()
对于 n=10，有 39,425 个不同的平面图。
对于 n=5，它打印以下 63 个结构：
Structure ID: 0 .O .O .O OO Structure ID: 1 .OO .O. OO. Structure ID: 2 ..O .OO OO. Structure ID: 3 .OOO OO.. Structure ID: 4 .O. .OO OO. Structure ID: 5 ..O ..O OOO Structure ID: 6 ..OO OOO. Structure ID: 7 ...O OOOO Structure ID: 8 OOOOO Structure ID: 9 OOOO ...O Structure ID: 10 OOO. ..OO Structure ID: 11 OOO ..O ..O Structure ID: 12 ..O. OOOO Structure ID: 13 ..O OOO ..O Structure ID: 14 OOOO ..O. Structure ID: 15 OO.. .OOO Structure ID: 16 OO. .OO ..O Structure ID: 17 OO .O OO Structure ID: 18 OO. .O. .OO Structure ID: 19 OO .O .O .O Structure ID: 20 OO. .OO .O. Structure ID: 21 .O. .O. OOO Structure ID: 22 .OO OOO Structure ID: 23 .O.. OOOO Structure ID: 24 .O. OOO ..O Structure ID: 25 .O .O OO .O Structure ID: 26 .OO OO. .O. Structure ID: 27 .O. OO. .OO Structure ID: 28 .O OO .O .O Structure ID: 29 ..O OOO .O. Structure ID: 30 OOOO .O.. Structure ID: 31 OOO .OO Structure ID: 32 OOO .O. .O. Structure ID: 33 .O. OOO .O. Structure ID: 34 O.O OOO Structure ID: 35 O... OOOO Structure ID: 36 O.. OOO ..O Structure ID: 37 O.. OO. .OO Structure ID: 38 O. OO .O .O Structure ID: 39 O.. OOO .O. Structure ID: 40 O.. O.. OOO Structure ID: 41 O. O. OO .O Structure ID: 42 O. O. O. OO Structure ID: 43 O O O O O Structure ID: 44 O. O. OO O. Structure ID: 45 O.. OOO O.. Structure ID: 46 O. OO OO Structure ID: 47 O. OO O. O. Structure ID: 48 .O .O OO O. Structure ID: 49 .OO OO. O.. Structure ID: 50 ..O OOO O.. Structure ID: 51 OOOO O... Structure ID: 52 OOO O.O Structure ID: 53 OO. OOO Structure ID: 54 OO OO .O Structure ID: 55 OO O. OO Structure ID: 56 OO O. O. O. Structure ID: 57 .O. OOO O.. Structure ID: 58 .O OO OO Structure ID: 59 .O OO O. O. Structure ID: 60 OOO OO. Structure ID: 61 OOO O.. O.. Structure ID: 62 OO OO O.