🐱

FileMakerでフィッシャー/イェーツのシャッフル

6 min read
FileMaker
tech

はじめに

またニッチで誰得？なネタになりますが、今回はFileMakerでシャッフルを行ってみます。バラバラに混ざった状態にするやつです。

みなさんは、規則正しく並んでいるものを見ると乱したくなることありませんか？普通にありますよねぇ、私なんかのレベルになると禁断症状が出るくらいです えぇ。ずいぶん昔に、キレイにグラデーション順に並んでいたMy Wife（絵が趣味）の色鉛筆を、バラバラに並び変えたら1週間ほど口をきいて貰えなかったキヲクが今もガッツリ脳に刻まれています。

つまりシャッフルにはリスクが伴うということで...

本題

多言語には普通にあったりするシャッフル関数ですが、FileMakerにはなぜかないんですよね。ソートを行うSortValuesが、4年前のFileMaker16からようやく実装されましたので、ひょっとしたら将来的にはシャッフル関数も実装されるかもしれません。

ただまぁ、そもそも必要な場面も経験上なかったんで、要るか？っていうと...まぁ...そこはね？
とは言え実際にどうやるかを考えると、何か見えてくるかもしれない。

フィッシャー/イェーツのシャッフルとは

有名なアルゴリズムに『フィッシャー/イェーツのシャッフル』というのがあります。改良版もありますがまずは、オリジナル版の手法からご紹介し、それぞれ実装してみます。簡単なスクリプトステップのみで実装しますので、どなたでも再現頂けますよ。

オリジナル版

図で表すとこうです。ある並んだリストがあったとします

この中からランダムで1つピックし（選び）ます（例えば、だちょう）

残った中からまたランダムで1つピックします（例えば、りんご）

っていうのを繰り返す手法なんですが...

えっそれだけ？

っていうね。まぁシャッフルするんだったらそりゃそういう手順になるよね、っていう正に王道中の王道。カードが入った袋の中から1個ずつ取り出して並べていく、そんなイメージですね。

スクリプトは、何てことのないこんな感じです。
※demoというテーブルにoriginalList shuffledListという2つのフィールドを設定しています

Randomにピック行を決めてGetValueで値をピックして元の一覧から除外して、残った一覧からまたランダムに値をピックして...を繰り返すのみ。ちなみにピック値を除外する17行目は、

$valueList
FilterValues ( 

	LeftValues ( $valueList ; $pickLine - 1 ) &
	RightValues ( $valueList ; $max.cnt - $pickLine ) 

	; demo::originalList

 )

とかしましたが、FilterValuesはやらなくてもアルゴリズムから言えば（ランダム選択が肝なので）問題ないですし、また簡単にUniqueValuesやSubstituteとかを使ってピックした値をガンガン消していってもいいですよ。やりやすいやり方で。

再帰カスタム関数化したら1つで終わりそうな勢いのシャッフルスクリプトですが、むしろ今のトレンドはWhile関数でのループなのかしら？でも私は年寄りなので、どうしても昔ながらの再帰カスタムを作りがちです。

え？あなたも？じゃぁ一緒に酒でも。

ダステンフェルド版

フィッシャー/イェーツのシャッフルを改良したもの、のようです。
ダンテさんじゃないですよダステンさんです。

要素数が n の配列 a をシャッフルする(添字は0からn-1)
i を n - 1 から 1 まで減少させながら、以下を実行する
j に 0 以上 i 以下のランダムな整数を代入する
a[j] と a[i]を交換する

よくは分からないんですがまぁ...要はなんやかんや交換していくっていう感じで？

余談ですがいつも思うのは、賢人達の記述の仕方は難解すぎて凡人にはツラい。Amazon MWSとかMWSとか、後はMWSとか。それからMWSとかも。もう理解させる気ゼロでしょ、っていうリファレンス。キミ達自分らで読み返したか？って言いたい。ハードモード過ぎる。

取り合えず...ダステンフェルドさんの思考は恐らくこんな感じかと。

例えば、上から1~7番として最後の7番（しまうま）と、それ以前（1~7番）からランダムでピックした値、例えば2番（ごりら）を交換します。「ごりら」はこれで確定です。

それを元に次は、6番（うし）と、それ以前（1~6番）からランダムでピックした値、例えば4番（ぱんだ）を交換します。「ぱんだ」もこれで確定です。

それを元に次は、5番（だちょう）と、それ以前（1~5番）からランダムでピックした値、例えば3番（らっぱ）を交換します。「らっぱ」もこれで確定です。

といった風に、どんどん遡りながら交換していく手法です。後ろから確定させていく感じですね。

ぶっちゃけ何か逆にややこしい
交換という箇所の処理がそこはかとなく面倒くさそう

だが、やるしかない

ダステンさんも配列がうんぬん、って言ってましたので配列で処理します。

  • 3~11行目：リストを配列にします。配列のインデックス（番地）は基本は0からなのでカウント$cntはゼロスタート。

8行目の$valueArraysの設定は以下です。

$valueArrays
JSONSetElement ( $valueArrays ;

	[ "[" & $cnt & "]" ; GetValue ( $valueList ; $cnt + 1 ) ; 1 ]

 )

インデックスをカウントアップさせながら、自身にどんどん配列値を追加していくカタチですね。こうやって作成される$valueArraysには、結果このような配列が得られます。

["りんご","ごりら","らっぱ","ぱんだ","だちょう","うし","しまうま"]

13行目からアルゴリズム本番の交換処理です。

  • 14行目：交換対象の配列インデックス（番地）$max.cntは、最後尾のインデックス6から減少させていくので0になったら抜ける（0の時は、配列[0]同士の交換なので無意味）
  • 16,17行目：交換対象の配列$endArrayと、ランダムピックする配列$pickArrayを設定（[]のカタチで）
  • 19行目：スワップ！スワップ！
$valueArrays
JSONSetElement ( $valueArrays ;

	[ $endArray ; JSONGetElement ( $valueArrays ; $pickArray ) ; 1 ];
	[ $pickArray ; JSONGetElement ( $valueArrays ; $endArray ) ; 1 ]

 )
  • 21行目：そして交換対象の配列$endArrayのインデックスを一つ減らす
  • 24行目：配列値をJSONListValuesで書き出す

案外何てことない処理でしたね。むしろ3~11行目までの配列にするのが何かアレだなー、って感じでしたが、

$valueArrays
"[\"" & 

Substitute ( $valueList ;

	[ "\"" ; "\\\"" ];
	[ ¶ ; "\",\"" ]

 )

& "\"]"

こんなので一気に配列$valueArraysを作成してもいいかもですね（値にダブルクォーテーションが含まれる可能性を考慮して2段階置換）。

考察的なナニカ

オリジナル版と改良版、速度的にはどんなもんなの？っていうと、リスト件数が少ない内は差はなかった。が、件数が増えれば増える程に改良版の方がダンチで速い、もう圧倒的。

オリジナル版の抜粋手法を変えてみたりとかしたけど全然ダメ。やっぱり再リスト化や抜粋とかの箇所がボトルネックね。2,000件くらいになると、もはや目も当てられない。

オリジナルがどんなに頑張ってもどんなに改良しても、ダステンの2秒

終わったな...と思われたが、
気を取り直してオリジナル版も一旦配列にして、そこからJSONGetElementでピックして新たな配列をJSONSetElementで作りつつ、元の配列からはJSONDeleteElementで消す方法にしたら...

なんと！ダステンとの差が超絶的に縮まるという結果に！

まとめ

たかがシャッフルされどシャッフル、奥が深い。
ちなみにランダムピックとは言え、偶然に最初と同じ並びでピックされないとも限らない。つまりシャッフル前後で全く同じ並びになる確率は、今回のように値が7つの場合、

\dfrac{1}{_7\mathrm{P}_7} = \dfrac{1}{7!} = \dfrac{1}{7×6×5×4×3×2×1} = \dfrac{1}{5040}

実は、ドバイの宝くじで100万ドル当たる確率がこれくらいらしいですよ！！
ドバイにのりこめー^^

でも5,000回くらい買えば必ず当たるということではないのでご注意を。
確率とはそういうことではないです。

今回のスクリプトで「りんご、ごりら、らっぱ、ぱんだ」の4つのシャッフルを24,000回実行した際の、それぞれのパターンの出現頻度がコチラです。

値が4つなので順列は4!=24パターンありますが、まぁ...ちゃんとバラけてるから機能しているかな、だいたい1/24に収束にしている。これもいわゆるモンテカルロ法。

確率に興味を持たれた方はコチラもぜひ

https://zenn.dev/ontherocks_plz/articles/f14ce7730e783c
https://zenn.dev/ontherocks_plz/articles/81cf358884bae0

おわりに

いかがだったでしょうか。
配列を制する者はデータを制す、そんな感じの結果でしたが、取り敢えずシャッフルのアルゴリズムは簡単なので、今後そんな関数が実装されることはなさそうですね。必要とされる場面もあんまり無さそうですし、登録した曲のシャッフル再生とか？乱痴気宴会時に何らかのゲームで使うとか？そのくらいですかねぇ。

カスタム関数化してベンチウォーマーさせておけばいいでしょう。

それでは
Let's enjoy FileMaker！

※並んだ色鉛筆の色をごちゃ混ぜしたらそりゃWifeもオコだよね、って。

Discussion

ログインするとコメントできます