[Python] BTS algorithm for finding genres and homogeneity sequences

I want to implement a bts algo to identify paths on the use of the balanced ternary numbering system, which is based on three and the digits have the values -1, 0, and 1. Given a string in the balanced ternary number system, we can define as an R-block a part of the string of the form - +1 , ≥ 0 which is preceded by a 0 and not followed by a -. An L-block is a part of the string of the form +- , ≥ 0, which is followed by a 0. In the string +00++-+++-000- we have from left to right an L-block, another L- block, and an R-block. The blocks cannot overlap each other. If we have a string that contains at least one block, then we can create its successor as follows. If the rightmost block is an R-block, then we replace the rightmost 0-+1 with -+ 0. Otherwise, we replace the rightmost +- 0 with 0++1. We also change the first sign, if any, that follows the block we just changed. We can see the process in the following sequence: 000-+ → 00-0- → 00-- → 0-+00 → 0-0+0 → 0-00+ → -000- → -00-0 → -0-0 → --000.

This is what I have done:

def generate_sigma(s,t):
sigmas = []
for j in range(2 ** (s-1)):
t_j= ""
for i in range(s-1):
bit = (j >> (s-2-i)) & 1
t_j += "-" if bit == 1 else "+"
s_j = "0" * t + "-" + t_j
sigmas.append(s_j)
return sigmas

def balanced_ternary_to_binary(s):
binary = []
for c in s:
if c == "0":
binary.append("0")
else:
binary.append("1")
return "".join(binary)

def binary_to_decimal(str):
return int(str, 2)

# Δημιουργία ακουλουθίας απο string
def generate_bts_sequence(sigma):
sequence = [sigma]
current = sigma
while True:
i = len(current) - 1
while i >= 1:
if current[i-1:i+1] == '0-':
block_type = 'R'
break
elif current[i-1:i+1] == '+0':
block_type = 'L'
break
i -= 1
else:
break

new = list(current)
if block_type == 'R':
new[i-1], new = '-', '+'
if i + 1 < len(new):
new[i+1] = '+' if new[i+1] == '-' else '-' if new[i+1] == '+' else new[i+1]
else:
new[i-1], new = '0', '+'
if i + 1 < len(new):
new[i+1] = '+' if new[i+1] == '-' else '-' if new[i+1] == '+' else new[i+1]

current = ''.join(new)
sequence.append(current)
return sequence


def bts(s, t):
graph = generate_graph(s, t)
graph_keys = set(graph.keys())
all_paths = []

for sigma in generate_sigma(s, t):
bts_seq = generate_bts_sequence(sigma)

binary_seq = [balanced_ternary_to_binary(x) for x in bts_seq]
decimal_seq = [binary_to_decimal(b) for b in binary_seq]

if all(node in graph_keys for node in decimal_seq):
index_seq = []
for b in binary_seq:
ones = [i for i, bit in enumerate(b) if bit == '1']
reversed_ones = ''.join(str(x) for x in ones[::-1]) if ones else '0'
index_seq.append(int(reversed_ones))

all_paths.append({
'bts': bts_seq,
'binary': binary_seq,
'index': index_seq,
'decimal': decimal_seq
})

return all_paths


and with this input python transposition_graphs.py 2 4 bts, where s number of 0 and t number of 1, except this output :

['0000-+', '000-0-', '000--0', '00-+00', '00-0+0', '00-00+',
↪
'0-000-', '0-00-0', '0-0-00', '0--000', '-+0000', '-0+000',
↪
'-00+00', '-000+0', '-0000+']
[111100, 111010, 111001, 110011, 110101, 110110, 101110, 101101,
101011, 100111, 001111, 010111, 011011, 011101, 011110]↪
[5432, 5431, 5430, 5410, 5420, 5421, 5321, 5320, 5310, 5210,
3210, 4210, 4310, 4320, 4321]↪
[60, 58, 57, 51, 53, 54, 46, 45, 43, 39, 15, 23, 27, 29, 30]
7
['0000--', '000-+0', '000-0+', '00-00-', '00-0-0', '00--00',
↪
'0-+000', '0-0+00', '0-00+0', '0-000+', '-0000-', '-000-0',
↪
'-00-00', '-0-000', '--0000']
[111100, 111001, 111010, 110110, 110101, 110011, 100111, 101011,
101101, 101110, 011110, 011101, 011011, 010111, 001111]↪
[60, 57, 58, 54, 53, 51, 39, 43, 45, 46, 30, 29, 27, 23, 15]

Continue reading...