サイトスワップをトポロジー変換したものを全探索するプログラム
一度に2つのことが起こらない世界でのジャグリングにおけるサイトスワップを、トポロジー変換してできあがる新たなサイトスワップ、それを
全探索して一覧表示するプログラムをとりあえずpythonで書いてみました。
import itertools
import re
while(True):
print('空白区切りで数値を入力してください')
print('「q」を入力すると終了します')
s = list(input().split())
t_ss = []
branch_num = [2]*len(s)
ori_graph = [[i] for i in range(len(s))]
if s[0] == 'q':
break
frax = 0
for i in range(len(s)):
if not(re.fullmatch(r'(\d+\.\d+)||\d+',s[i])):
print('入力は数値のみ受け付けます')
frax = 1
break
a = s[i].find('.')
if a >= 0:
branch_num[i] -= 1
t_ss.append([int(s[i][:a])])
t_ss[i].append(int(s[i][a+1]))
else:
t_ss.append([int(s[i][:])])
for j in range(len(t_ss[i])):
c = t_ss[i][j]
c = (i+c)%len(s)
ori_graph[i].append(c)
branch_num[c] -= 1
if frax == 0:
fra = 0
for i in branch_num:
if i != 0:
print('impossible',branch_num)
fra = 1
break
if fra == 0:
print(ori_graph)
for seq in itertools.permutations(range(0,len(ori_graph))):
kari = []
swap_val = ["" for i in range(len(ori_graph))]
f_num = {}
for i in range(len(ori_graph)):
kari.append(ori_graph[seq[i]])
f_num[kari[i][0]] = i
for i in range(len(kari)):
for j in range(len(kari[i])):
if j >= 1:
if i >= f_num[kari[i][j]]:
x = len(ori_graph)+f_num[kari[i][j]]-i
else:
x = f_num[kari[i][j]]-i
if j == 1:
swap_val[i] = str(x)
if j == 2:
swap_val[i] = swap_val[i] + '.' + str(x)
print(*swap_val)
python実行環境のある方は試してみてください。
実行したらコマンドラインから、たとえば
1 3.1 1 3.1
のように入力すれば、これをグラフ化したものを1行表示しその下に
グラフの節を並べ替えてできる全組み合わせのサイトスワップを1行ずつ
表示します。
項目数の階乗分表示されるので、実行するのは長さ8ぐらいまでにしといたほうがいいです。
qを入力すると終了します。
実行環境のない方はwebでも実行できます。
何個か試してみたところ、
pyWeb
が使いやすかったです。真ん中のエリアにコードを張り付けて、右上の再生ボタンを押すと右側のコマンドラインで入力ができます。