如何将坐标形状拆分为所有无旋转重复的可能子形状？

问题说明 #

给定用坐标集合表示的形状（示例：shape = {(0,0), (0,1), (1,0), (1,1)}），需要找出所有满足以下条件的子形状组合：

• 子形状数量范围是range(2, len(shape)+1)
• 所有子形状可拼接成原形状
• 排除旋转重复的组合

目前已写出初步暴力遍历代码，但希望找到更优雅的非暴力实现思路。

初步代码 #

from itertools import combinations_with_replacement

# 像素坐标：原点(0,0)为左上角
shape = [(0,0),(0,1),(1,0),(1,1)]

def sums(a, b):
    return tuple(sum(x) for x in zip(a, b))

def combinations_pixels_per_subshape(shape: list, n_subshapes: int):
    # 返回满足条件的子形状像素数组合，总和等于原形状的像素总数
    shape_pixels = len(shape)
    for c in combinations_with_replacement(range(1, shape_pixels), n_subshapes):
        if sum(c) == shape_pixels:
            yield(c)

# 子形状数量最多等于原形状的像素数
for nsub in range(2, len(shape) + 1):
    print(nsub, "个子形状")
    for comb in combinations_pixels_per_subshape(shape, nsub):
        print(comb) 
        for subpix in comb:
            print(subpix)
            
    break

预期输出示例 #

[[(0,0)], [(0,1)], [(1,0)], [(1,1)]] # 每个像素单独作为子形状（共4个子形状）
[[(0,0)], [(0,1), (1,0), (1,1)]] # 单个像素加3像素块（共2个子形状）
[[(0,0),(1,0)],[(0,1),(1,1)]] # 两个2像素块（共2个子形状）
[[(0,0)], [(0,1)], [(1,0), (1,1)]] # 两个单个像素加一个2像素块（共3个子形状）

注：需排除同形状的不同位置或旋转形式的重复结果。

内容的提问来源于stack exchange，提问作者slapslash