サイトスワップ掲示板

任意の数列を含むサイトスワップの生成

No.94: 2017-01-06(金) 02:07:05
投稿者: にしの
59 とか任意の数列を含むサイトスワップを作ってみようと思い、考えてみたら意外と難しかったのでご紹介です。

0)ボールの数を一つ固定する 例 3個のサイトスワップで
1)適当な数字を考える  例 67
2)これを含むサイトスワップを見つける 答え 6711123

というわけで、意外と難しいです。

自明なこととして降順数列とそれを含むもの (例 54、3X1)を含むジャグリングの数列は存在しないので不可です。
この他にも不可のものがあるかもしれません。

不可でない数列ならなんでも、それを含む数列が作れます。

手続き的に証明すると、例えば、
67 の場合
 6 7 - - - - 7 - 6 - - - - - - 6 7 - - ....
と長さ 13 (6+7)の数列の繰り返しとして書くことができ、この間のスペースを全部0にすれば 2個のサイトスワップになります。
ここにd(13)の倍数を適宜埋め込めば3以上何個でも対応できます。

もちろん、ここで得られる数列は最短が保障されていません。

課題は、とりあえず、
A)不可の数列(部品とならないもの)には降順数列の他に何があるか?
B)「最短」のものを見つける方法
の二つがあります。

興味のある方はチャレンジ願います。

関連ツリー

【1】 任意の数列を含むサイトスワップの生成 No.94 にしの 2017-01-06(金) 02:07:05
Re: 任意の数列を含むサイトスワップの生成 No.95 にしの 2017-01-06(金) 21:46:57

掲示板に戻る