Untitled
from itertools import product import numpy as np from functools import partial from multiprocessing import Pool, cpu_count # Helper functions def rotate_bits(binary_str): """Generate all rotated versions of a binary string.""" n = len(binary_str) return [binary_str[i:] + binary_str[:i] for i in range(n)] def hamming_distance(bin1, bin2): """Calculate the Hamming distance between two binary strings.""" return sum(bit1 != bit2 for bit1, bit2 in zip(bin1, bin2)) def is_valid_sequence(sequence): """Check if a sequence satisfies the one-bit change property.""" return all(hamming_distance(sequence[i], sequence[i + 1]) == 1 for i in range(len(sequence) - 1)) def evaluate_pattern(ep): """Evaluate the pattern of the EP based on groups of 1.""" groups = [len(group) for group in ep.split('0') if group] groups.sort() return groups def compare_patterns(new_pattern, best_pattern): """Compare two patterns to determine the most optimal based on LLOSG1 and LNOTSG1.""" for i in range(min(len(new_pattern), len(best_pattern))): if new_pattern[i] > best_pattern[i]: return True elif new_pattern[i] < best_pattern[i]: return False return len(new_pattern) < len(best_pattern) def generate_EP(n_bit_binaries): """Generate the EP by transposing the binary matrix of the given sequence.""" matrix = np.array([list(binary) for binary in n_bit_binaries]) transposed_matrix = matrix.T ep = "".join(transposed_matrix.flatten()) return ep, matrix, transposed_matrix def recursive_search(path, used, depth, binary_numbers, all_rotations): """Recursive search for optimal sequence.""" best_pattern = None best_sequence = None best_ep = None best_original_matrix = None best_transposed_matrix = None # Base case: if the path forms a complete sequence if depth == len(binary_numbers): ep, original_matrix, transposed_matrix = generate_EP(path) pattern = evaluate_pattern(ep) return pattern, path[:], ep, original_matrix, transposed_matrix # Recursive step: add unused rotations to the path for i in range(len(binary_numbers)): if not used[i]: for rotation in all_rotations[i]: if not path or hamming_distance(path[-1], rotation) == 1: path.append(rotation) used[i] = True # Recursive call result = recursive_search(path, used, depth + 1, binary_numbers, all_rotations) if result: pattern, sequence, ep, original_matrix, transposed_matrix = result if best_pattern is None or compare_patterns(pattern, best_pattern): best_pattern = pattern best_sequence = sequence best_ep = ep best_original_matrix = original_matrix best_transposed_matrix = transposed_matrix # Backtrack used[i] = False path.pop() # Return best results for this branch if best_pattern is not None: return best_pattern, best_sequence, best_ep, best_original_matrix, best_transposed_matrix return None # Parallelized function wrapper def parallel_worker(task_data): binary_numbers, all_rotations, start_index = task_data path = [all_rotations[start_index][0]] used = [False] * len(binary_numbers) used[start_index] = True return recursive_search(path, used, 1, binary_numbers, all_rotations) def find_most_optimal_pattern(binary_numbers): """Find the Gray code combination producing the most optimal EP.""" all_rotations = [rotate_bits(binary) for binary in binary_numbers] # Parallelization setup tasks = [(binary_numbers, all_rotations, i) for i in range(len(binary_numbers))] best_pattern = None best_sequence = None best_ep = None best_original_matrix = None best_transposed_matrix = None with Pool(cpu_count()) as pool: results = pool.map(parallel_worker, tasks) # Determine the best result from all parallel tasks for result in results: if result is not None: pattern, sequence, ep, original_matrix, transposed_matrix = result if best_pattern is None or compare_patterns(pattern, best_pattern): best_pattern = pattern best_sequence = sequence best_ep = ep best_original_matrix = original_matrix best_transposed_matrix = transposed_matrix return best_sequence, best_ep, best_original_matrix, best_transposed_matrix # TNC generation def is_tnc(binary_number): """ Check if a binary number is a TNC (unique binary sequence under rotation). """ rotations = set() n = len(binary_number) for i in range(n): rotated = binary_number[i:] + binary_number[:i] rotations.add(rotated) return len(rotations) == n and binary_number == min(rotations) def generate_tnc(n): """Generate all TNC for n-bit binary numbers.""" tnc_list = [] for binary_number in product("01", repeat=n): binary_str = "".join(binary_number) if is_tnc(binary_str): tnc_list.append(binary_str) return tnc_list # Main execution flow if __name__ == "__main__": n = int(input("Enter the number of bits: ")) tnc_list = generate_tnc(n) print(f"TNCs for {n} bits: {tnc_list}") print(f"Number of TNCs: {len(tnc_list)}\n") best_sequence, best_ep, best_original_matrix, best_transposed_matrix = find_most_optimal_pattern(tnc_list) if best_sequence: print("Optimal Gray Code Sequence:", best_sequence) print("\nOriginal Matrix:") print(best_original_matrix) print("\nTransposed Matrix:") print(best_transposed_matrix) print("\nEP:", best_ep) else: print("No valid Gray Code sequence found.")
Leave a Comment