Python排列图问题：无法获取全部邻接节点，请求错误排查

我编写了一段Python代码，功能为：生成指定数量0和1的字符串的所有二进制排列，基于特定同质性条件（仅两个连续位不同）检查邻接关系，构建排列的图结构，并按十进制值排序输出图。但实际输出与期望不符，无法正确找到每个节点的所有邻接节点。

当前代码 #

def homogeneity_check(n1, n2) -> bool:
    positions = [i for i in range(len(n1)) if n1[i] != n2[i]]
    if len(positions) == 2 and positions[1] == positions[0] + 1:
        return True
    return False
    
def find_permutations(s: str):
    def generate_permutations(s, current_index):
        if current_index == len(s) - 1:
            return [s]  # Αν φτάσουμε στο τέλος της αλυσίδας, επιστρέφουμε την τρέχουσα παραλλαγή
        
        perms = []
        for i in range(current_index, len(s)):
            # Ανταλλάζουμε τα στοιχεία στις θέσεις current_index και i
            s_list = list(s)
            s_list[current_index], s_list[i] = s_list[i], s_list[current_index]
            new_str = ''.join(s_list)
            
            # Βάζουμε την νέα παραλλαγή και συνεχίζουμε την αναδρομή
            perms.extend(generate_permutations(new_str, current_index + 1))
        
        return perms

    perms = set(generate_permutations(s, 0))  # Χρησιμοποιούμε set για να αποφύγουμε τα διπλότυπα
    print(sorted(perms))
    return sorted(perms)

def generate_graph(s,t):
    num = ("0" * s + "1" * t)
    perms = find_permutations(num)
    
    graph = {n: [] for n in perms} # Κενός γραφός, με λιστές που αντιπροσωπεύουν τους γείτονες

    for i in range(len(perms)):
        for j in range(i + 1, len(perms)):
            # if homogeneity_check(perms[i], perms[j]):
                graph[perms[i]].append(perms[j])
                graph[perms[j]].append(perms[i])
    return graph

def print_graph(graph):
    for node in sorted(graph, key=lambda x: int(x, 2)):
        node_decimal = int(node, 2)
        neighbors_decimal = sorted(int(neigh, 2) for neigh in graph[node])
        print(f"{node_decimal} -> {neighbors_decimal}")

当前输出 #

15 -> [23]
23 -> [15, 27, 39]
27 -> [23, 29, 43]
29 -> [27, 30, 45]
30 -> [29, 46]
39 -> [23, 43]
43 -> [27, 39, 45, 51]
45 -> [29, 43, 46, 53]
46 -> [30, 45, 54]
51 -> [43, 53]
53 -> [45, 51, 54, 57]
54 -> [46, 53, 58]
57 -> [53, 58]
58 -> [54, 57, 60]
60 -> [58]

期望输出 #

60 -> [58, 57, 54, 53, 46, 45, 30, 29]
 58 -> [60, 57, 51, 54, 43, 46, 27, 30]
 57 -> [60, 58, 53, 51, 45, 43, 29, 27]
54 -> [60, 58, 51, 53, 39, 46, 23, 30]
53 -> [60, 57, 54, 51, 45, 39, 29, 23]
46 -> [60, 58, 54, 43, 39, 45, 15, 30]
45 -> [60, 57, 53, 46, 43, 39, 29, 15]
30 -> [60, 58, 54, 46, 27, 23, 15, 29]
29 -> [60, 57, 53, 45, 30, 27, 23, 15]
51 -> [58, 57, 54, 53, 43, 39, 27, 23]
43 -> [58, 57, 46, 45, 51, 39, 27, 15]
27 -> [58, 57, 30, 29, 51, 43, 23, 15]
39 -> [54, 53, 46, 45, 51, 43, 23, 15]
23 -> [54, 53, 30, 29, 51, 27, 39, 15]
15 -> [46, 45, 30, 29, 43, 27, 39, 23]

问题分析与修复 #

1. 核心矛盾：需求描述与期望不匹配 #

你代码中实现的homogeneity_check是仅允许两个连续位置的0和1交换（比如001111→010111），但你的期望输出对应的是交换任意位置的0和1得到的排列互为邻接（即两个排列的汉明距离为2，且保持0和1的数量不变）。这是两种完全不同的邻接规则。

2. 代码中的注释错误 #

你提供的generate_graph函数里，homogeneity_check的判断被注释掉了，但从当前输出看，你实际运行的代码应该是保留了该判断的——否则所有节点会互相连接，和你给出的当前输出不符。

3. 修复方案 #

方案A：修改为期望的邻接规则（交换任意0和1）

如果你的真实需求是让所有可通过交换一个0和一个1得到的排列互为邻接，修改homogeneity_check函数如下：

def homogeneity_check(n1, n2) -> bool:
    # 检查两个排列的汉明距离是否为2（恰好两个位置不同）
    diff_positions = [i for i in range(len(n1)) if n1[i] != n2[i]]
    return len(diff_positions) == 2

方案B：确保原规则生效（仅连续位交换）

如果你的需求确实是仅允许连续位交换，取消generate_graph中的注释，确保条件判断生效：

def generate_graph(s,t):
    num = ("0" * s + "1" * t)
    perms = find_permutations(num)
    
    graph = {n: [] for n in perms}

    for i in range(len(perms)):
        for j in range(i + 1, len(perms)):
            if homogeneity_check(perms[i], perms[j]):  # 取消这行的注释
                graph[perms[i]].append(perms[j])
                graph[perms[j]].append(perms[i])
    return graph

额外优化：提升排列生成效率

当前递归生成排列的方式效率较低，可改用itertools.permutations简化实现：

from itertools import permutations

def find_permutations(s: str):
    # 生成唯一排列并按字符串排序
    perms = sorted(set(''.join(p) for p in permutations(s)))
    print(perms)
    return perms

验证 #

修改homogeneity_check为汉明距离判断后，运行print_graph(generate_graph(2,4))即可得到你期望的输出。

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