import math from statistics import median, stdev def count_one_bits(n): return bin(n).count("1") def compute_distance(a, b): distance = count_one_bits(a ^ b) # return 1 / (8 ** distance) if distance == 0: return 0 # return 1 / (64 ** (distance - 1)) return distance def xor_n(n): return count_one_bits(n) % 2 def compute_distances(N): return [[compute_distance(i, j) for j in range(N)] for i in range(N)] def compute_nn_probabilities(i, knowns, distances): total = 0.0 total_zero = 0.0 total_one = 0.0 for known in knowns: j = known[0] if i == j: continue distance = distances[i][j] total += distance if known[1] == 0: total_zero += distance else: total_one += distance p_zero = total_zero / total p_one = total_one / total return (p_zero, p_one) def interpolate_probabilities(i, knowns, distances, probabilities, dim): total = 0.0 total_dim = [0.0] * dim for known in knowns: j = known[0] if i == j: continue distance = distances[i][j] total += distance probability = probabilities[j] for index in range(dim): total_dim[index] += distance * probability[index] for index in range(dim): total_dim[index] /= total return total_dim def compute_est_coherence(i, knowns, coherences, distances): total = 0.0 coherence = 0.0 for known in knowns: j = known[0] distance = distances[i][j] total += distance coherence += distance * coherences[j] return coherence / total def compute_est_coherences(N, knowns, distances): nn_probabilities = [None for i in range(N)] nn_correct_probabilities = [None for i in range(N)] coherences = [] for known in knowns: i = known[0] nn_probabilities[i] = compute_nn_probabilities(i, knowns, distances) # for i in range(len(nn_probabilities)): # if not nn_probabilities[i] is None: # continue # nn_probabilities[i] = interpolate_probabilities(i, knowns, distances, nn_probabilities, 2) for known in knowns: i = known[0] nn_correct_probabilities[i] = [nn_probabilities[i][known[1]]] # for i in range(len(nn_correct_probabilities)): # if not nn_correct_probabilities[i] is None: # continue # nn_correct_probabilities[i] = interpolate_probabilities(i, knowns, distances, nn_correct_probabilities, 1) coherences_0 = [] coherences_1 = [] for known_i in knowns: i = known_i[0] coherence = 0.0 total = 0.0 for known_j in knowns: j = known_j[0] if i == j: continue distance = distances[i][j] total += distance nn_p_i_0 = nn_probabilities[i][0] nn_p_i_1 = nn_probabilities[i][1] nn_c_p_i = nn_correct_probabilities[i][0] nn_p_j_0 = nn_probabilities[j][0] nn_p_j_1 = nn_probabilities[j][1] nn_c_p_j = nn_correct_probabilities[j][0] p_i_0 = nn_p_i_0 * nn_c_p_i + nn_p_i_1 * (1 - nn_c_p_i) p_i_1 = nn_p_i_1 * nn_c_p_i + nn_p_i_0 * (1 - nn_c_p_i) p_j_0 = nn_p_j_0 * nn_c_p_j + nn_p_j_1 * (1 - nn_c_p_j) p_j_1 = nn_p_j_1 * nn_c_p_j + nn_p_j_0 * (1 - nn_c_p_j) coherence += distance * (p_i_0 * p_j_0 + p_i_1 * p_j_1) coherences.append(coherence / total) if known_i[1] == 0: coherences_0.append(coherence / total) else: coherences_1.append(coherence / total) return coherences def score(coherences, knowns, distances): # while len(coherences) > 1: # coherences = [(coherences[i] + coherences[i + 1]) / 2 for i in range(0, len(coherences), 2)] # return coherences[0] # return median(coherences) # return sum(coherences) / len(coherences) if len(coherences) == 0: return 1.0 numerator_0 = 0.0 denominator_0 = 0.0 numerator_1 = 0.0 denominator_1 = 0.0 count_0 = 0.0 count_1 = 0.0 for i in range(len(knowns)): weight = 0 for j in range(len(knowns)): weight += distances[knowns[i][0]][knowns[j][0]] print(weight, end=' ') if knowns[i][1] == 0: denominator_0 += weight numerator_0 += weight * coherences[i] count_0 += 1 else: denominator_1 += weight numerator_1 += weight * coherences[i] count_1 += 1 # print() if count_0 == 0 or count_1 == 0: return 1.0 # return ((sum(coherences[0]) / len(coherences[0])) + (sum(coherences[1]) / len(coherences[1]))) / 2.0 # return (sum(coherences[0]) + sum(coherences[1])) / (len(coherences[0]) + len(coherences[1])) # div_0 = (numerator_0 / denominator_0 if denominator_0 > 0 else 1.0) * 0.5 # div_1 = (numerator_1 / denominator_1 if denominator_1 > 0 else 1.0) * 0.5 # return div_0 + div_1 # aligned = 1.0 - abs(0.5 - max(count_0 / (count_0 + count_1), count_1 / (count_0 + count_1))) # return ((numerator_0 + numerator_1) / (denominator_0 + denominator_1)) * (aligned ** 0.1) # return (((numerator_0 + numerator_1) / (denominator_0 + denominator_1)) + 0.12 * aligned) * (1.0 / 1.12) return (numerator_0 + numerator_1) / (denominator_0 + denominator_1) def xor_by_index(knowns, index): mask = 1 << index knowns = knowns[:] for i in range(len(knowns)): known = knowns[i] if known[0] & mask: knowns[i] = (known[0], known[1] ^ 1) return knowns def main(): n = 8 N = 2 ** n distances = compute_distances(N) knowns = [(i, xor_n(i)) for i in [ # 0, 3, 4, 5, 7 # 3, 5, 6, 10, 12, 14 # 1, 3, 7, 10, 14, 15 # 0, 3, 5, 6, 10, 11, 12 0, 3, 5, 6, 10, 11, 12, 24, 30 # 0, 3, 5, 6, 10, 11, 12, 24, 30, 52, 63, 255, 243, 127 # 128, 131, 248, 0, 7, 13, 17, 19 ]] for known_i in knowns: i = known_i[0] for known_j in knowns: j = known_j[0] print(distances[i][j], end=' ') print() print(knowns) print() # knowns = [ # (1, 1), # (3, 0), # (7, 1), # (10, 0), # (14, 1), # (15, 0) # ] # knowns = [ # (0, 0), # (3, 0), # (4, 1), # (5, 0), # (7, 1) # ] # knowns = [ # (0, 0), # (1, 1), # (2, 1), # (3, 0), # (4, 1), # (5, 0), # (6, 0), # (7, 1) # ] coherences = compute_est_coherences(N, knowns, distances) best_coherence = score(coherences, knowns, distances) print(best_coherence) flipped = [] while best_coherence < 1.0: print() # print(knowns) # print() best_index = -1 # best_coherence = 0 for i in range(0, n): if i in flipped: continue mutated_knowns = xor_by_index(knowns, i) coherences = compute_est_coherences(N, mutated_knowns, distances) coherence = score(coherences, mutated_knowns, distances) # print(coherence) print(coherence, end=' ') print(mutated_knowns) if coherence > best_coherence: best_coherence = coherence best_index = i if best_index < 0: break knowns = xor_by_index(knowns, best_index) # flipped.append(best_index) print(knowns) if __name__ == "__main__": main()