Início / user-18764738

Cybercode's questions

Martin Hope
Cybercode
Asked: 2025-04-09 03:33:44 +0800 CST
  • 5

Olá, criei este código. O código gera todas as permutações binárias de uma string com um determinado número de zeros e uns, verifica a adjacência com base em uma condição de homogeneidade específica (diferente de exatamente dois bits consecutivos), cria um gráfico dessas permutações e imprime o gráfico com nós classificados por seus valores decimais.

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}")

Eu tenho esta saída com esta entrada print_graph(generate_graph(2,4)):

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]

mas eu quero isso

 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]

Alguém pode me explicar o que estou fazendo errado? Não consigo entender como encontrar os outros vizinhos de cada nó.

python