生成非交叉划分的Kreweras补（对偶）的Python实现问题

针对你的预期输出的实现 #

根据你给出的输入输出示例，对应的转换规则可以总结为：

• 将原划分按块的最小元素排序
• 对每个块：
  • 若块长度大于1，将块的第一个元素单独作为一个块，把块的最后一个元素加入公共块
  • 若块长度为1，直接将元素加入公共块
• 最后将所有单独块和公共块按最小元素排序输出

对应的Python代码：

def kreweras_complement(partition):
    # 按块的最小元素排序原划分
    sorted_blocks = sorted(partition, key=lambda b: min(b))
    common_block = []
    single_blocks = []
    
    for block in sorted_blocks:
        if len(block) == 1:
            common_block.append(block[0])
        else:
            single_blocks.append([block[0]])
            common_block.append(block[-1])
    
    # 合并结果并按块的最小元素排序
    result = single_blocks
    if common_block:
        result.append(common_block)
    return sorted(result, key=lambda b: min(b))

# 测试你的示例
input_part = [[1,2],[3],[4,5]]
print(kreweras_complement(input_part))  # 输出: [[1], [2, 3, 5], [4]]

严格意义的Kreweras补实现 #

如果你需要的是数学定义上的线性非交叉划分Kreweras补（基于圆周划分的旋转补），可以使用以下代码：

def strict_kreweras_complement(partition):
    n = max(num for block in partition for num in block)
    n_plus_1 = n + 1
    
    # 将线性划分转换为包含{1, n+1}的圆周划分
    circ_partition = []
    found_first = False
    for block in partition:
        if 1 in block:
            circ_block = block.copy()
            circ_block.append(n_plus_1)
            circ_partition.append(circ_block)
            found_first = True
        else:
            circ_partition.append(block.copy())
    if not found_first:
        circ_partition.append([1, n_plus_1])
    
    # 计算圆周划分的Kreweras补（每个元素+1模n+1）
    circ_complement = []
    for block in circ_partition:
        new_block = []
        for num in block:
            new_num = num + 1
            if new_num > n_plus_1:
                new_num = 1
            new_block.append(new_num)
        circ_complement.append(new_block)
    
    # 去掉n+1，转换回线性划分
    linear_complement = []
    for block in circ_complement:
        cleaned_block = [num for num in block if num != n_plus_1]
        if cleaned_block:
            linear_complement.append(cleaned_block)
    
    # 按块的最小元素排序
    return sorted(linear_complement, key=lambda b: min(b))

# 测试你的示例
print(strict_kreweras_complement(input_part))  # 输出: [[1, 2, 3], [4], [5]]

这个严格版本的输出和你的预期不同，因为数学定义上的Kreweras补和你示例中的转换规则存在差异，你可以根据实际需求选择对应的实现。

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