与えられた並べ替えを実現するあみだくじの生成
Posted feedbacks - Python
自力では解けなかったので、カバレッジ100%目的で pythonに移植させて頂きました。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | def f(args):
order = {}
sequence = [order.setdefault(j, i) for i, j in enumerate(args)]
print ' '.join([str(i) for i in sequence])
change = True
while change:
am = list(' ' * (len(sequence) - 1))
change = False
i = 0
while i < len(sequence) - 1:
if order[sequence[i]] > order[sequence[i+1]]:
sequence[i], sequence[i+1] = sequence[i+1], sequence[i]
change = True
am[i] = '-'
i += 1
i += 1
if change:
print '|%s|' % '|'.join(am)
print ' '.join([str(i) for i in sequence])
f([3,5,2,4,0,1])
|
おっと、上のコードだと与えられたデータが初めからソートされている場合に 縦棒の列が消えてしまうので、再投稿ついでに全面書き直し。
1 2 3 4 5 6 7 8 9 10 11 12 | def f(a):
l = [' '.join([str(i) for i in a])]
while True:
f = [1] * len(a)
l.append(''.join([a.insert(i, a.pop(i+1)) or f.insert(i+1, 0) or
'|-' if f[i] and a[i] > a[i+1] else
'| ' for i in range(len(a)-1)]) + '|')
if a == range(len(a)): break
l.append(' '.join([str(i) for i in a]))
print '\n'.join(reversed(l))
f([3,5,2,4,0,1])
|
shiro
#4704()
Rating13/13=1.00
お題#4476を見て思いつきました。
0からn (n>=1) までの数字を任意の順で並べたリストが与えられた時、0からnまでが順に並んだ状態から出発して、与えられたリストの順で結果が得られるようなあみだくじを作成して出力するプログラムを書いてください。
与えられたリストが (3 5 2 4 0 1) の場合、出力の1例を示します：
一応、制約条件を示しておきます。
一つのリストに対して複数の解があり得ます。ナイーブな解に飽き足らなければ出力行数をなるべく少なくする解を求める方法を考えてみてください。
[ reply ]