"""Return the number of distinct binary necklaces of length n using
the FKM / Ruskey algorithm, without storing them, based on Lyndon words."""
def generate_necklaces_fkm(n: int):
buffer = [0] * (n + 1)
necklaces = []
def generate_recursive(position: int, period: int) -> None:
if position > n:
if n % period == 0:
necklace = "".join(str(bit) for bit in buffer[1 : period + 1]) * (n // period)
necklaces.append(necklace)
return
buffer[position] = buffer[position - period]
generate_recursive(position + 1, period)
for bit_value in range(buffer[position - period] + 1, 2):
buffer[position] = bit_value
generate_recursive(position + 1, position)
generate_recursive(1, 1)
return necklaces
for necklace in generate_necklaces_fkm(13):
print(necklace)
