Hi I have made this code. Τhe code generates all binary permutations of a string with a given number of zeros and ones, checks for adjacency based on a specific homogeneity condition (differing by exactly two consecutive bits), builds a graph of these permutations, and prints the graph with nodes sorted by their decimal values.
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}")
I have this output with this input 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]
but I want this
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]
can someone explain me what I am doing wrong. I can't understand how to find the other neighbours for each node.
You claim to expect 46 and 15 to be adjacent in the graph. But 46 represents 101110 and 15 represents 001111. Those are not adjacent by the adjacency rule that you've described (and coded). Therefore either your expectation is wrong, or your adjacency rule is wrong. (Spot checking, 23 represents 010111, which indeed should be the only thing adjacent to 001111 by your stated rule...)
You can get the output that you say you expect with the following changes.
First, change your homogeneity check to just swap 2 positions.
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
Second, get rid of your debugging print in find_permutations:
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)
Re-enable the homogeneity check in 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
Add reverse=True to the sorts in print_graph:
def print_graph(graph):
for node in sorted(graph, key=lambda x: int(x, 2), reverse=True):
node_decimal = int(node, 2)
neighbors_decimal = sorted((int(neigh, 2) for neigh in graph[node]), reverse=True)
print(f"{node_decimal} -> {neighbors_decimal}")