# GoldPerm1-q6
# Exs for Section 47, Q.6, p.167, p.276-277

import math

N = 100

u = [0]*(N+1)
x = [i for i in range(N+1)]
y = [0]*(N+1)

z = (math.sqrt(5)-1)/2
for i in range(1,N+1):
  y[i] = i*z - math.trunc(i*z)

for i in range(2, N+1):
  v = y[i]
  w = x[i]
  j = i
  # print(j-1, y[1])
  while y[j-1] == v:   # ??
    y[j] = y[j-1]
    x[j] = x[j-1]
    j -= 1
  y[j] = v
  x[j] = w
print()

print("The golden perm:")
for i in range(1,N+1):
  print(f"{x[i]:4}", end='')
print()

print("Forward diffs in golden perm:")
for i in range(1,N):
  print((x[i+1]-x[i]), end='')
print()

print("Dist from x[i] to x[i]+1 in golden perm:")
i = 1
while i <= N:
  j = 0; # checks c
  if x[i] == N:
    print(" N")
  else:
    while True:
      j += 1
      if x[j]-x[i] == 1:
        break
    print((j-i), end ='')
  i += 1
print()

for i in range(1,N+1):
  u[x[i]] = i

print("Inverse perm:")
for i in range(1,N):
  print(f"{u[i]:4}", end ='')
print()

print("Forward diffs in inverse perm:")
for i in range(1,N-1):
  print((u[i+1]-u[i]), end='')
print()

print("Dist from u[i] to u[i]+1 in inverse perm:")
i = 1
while i <= N:
  j = 0; # checks c
  if u[i] == N:
    print(" N")
  else:
    while True:
      j += 1
      if u[j] - u[i] == 1:
        break
    print((j-i), end='')
  i += 1