research/defrag/permutation2.py

50 lines
1.2 KiB
Python

import random
def mk_shuffle(n):
L = list(range(n))
random.shuffle(L)
return L
def mk_fragmented_shuffle(n, shuffs):
L = list(range(n))
for i in range(shuffs):
x1 = random.randrange(n)
x2 = random.randrange(n)
value = int(min(n - x1, n - x2, abs(x2 - x1)) ** random.random())
L[x1:x1+value], L[x2:x2+value] = L[x2:x2+value], L[x1:x1+value]
return L
def fragments(vals):
tot = 1
for i in range(1, len(vals)):
if vals[i] != vals[i-1] + 1:
tot += 1
return tot
def apply_perm(vals, perm):
o = [0 for x in vals]
for i in range(len(perm)):
o[i] = vals[perm[i]]
return o
def attempt_fix(vals):
perm = list(range(len(vals)))
indices = {}
for i, x in enumerate(vals):
indices[x] = i
for i in range(len(vals)):
if perm[i] == i and vals[i] != i:
poz = indices[i]
if perm[poz] == poz:
perm[i], perm[poz] = perm[poz], perm[i]
assert apply_perm(perm, perm) == list(range(len(vals)))
return perm
def fix(vals):
goal = list(range(len(vals)))
path = []
while vals != goal:
vals = apply_perm(vals, attempt_fix(vals))
path.append(vals)
return path