こんにちは。
連鎖配列(例: [[0,1],[1,2],[2,3]]
)がランダムにシャッフルされているとして、それの本来の並び順を求めてみました。
$ ./sequence_sort.py
[[2, 3], [1, 2], [0, 1]] ==>
[0, 1]
[1, 2]
[2, 3]
sequence_sort.py
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import random
SKIP = -1
def find_vacancy(seq):
return list(set(range(len(seq))) - set(seq))[0]
def seq_nexts(arr):
heads = [a[0] for a in arr]
nexts = [heads.index(a[-1]) if a[-1] in heads else SKIP for a in arr]
index_top = find_vacancy(nexts)
return index_top, nexts
def sequence_sort(arr):
i, nexts = seq_nexts(arr)
indices = []
while i is not SKIP:
indices.append(i)
i = nexts[i]
return indices
N = 3
data = [[i,i+1] for i in range(N)]
random.shuffle(data)
print(data, '==>')
for i in sequence_sort(data):
print(data[i])
exit(0)