配列の並び替えのパターンの列挙をする関数をgolangで書く．ABC123で必要になったので．

TL;DR

QuickPermを使うと良さそうです．

上記はコピペ用でこっからはいくつか方法を試して最後に速度比較します．

方法1: naive dfs

素直にdfsをする．前から数字を決めていって，決めたらその数字を選択肢から消して次へ行く．全部使ったら（選択肢が無くなったら）1つのパターンとして採択する．

上のコードで使ってるサブ関数たちです．この後の方法でも使ってるのですが面倒なので1度だけ掲載．

方法2: Heap Algorithm

Heapのアルゴリズム を使う．

方法3: QuickPerm

QuickPermを使う．

方法4（おまけ）: QuickPerm + Channel

Generate all permutations in goとかを見ているとChannelを使った実装をしているので早いのか？と思って試してみた．

速度比較

go testでベンチマーク取ります．

方法3のQuickPermが一番早そうです．方法4は非同期でやっても単に結果くるまでブロッキングしてるので，goroutineやchannelの生成の分で普通に遅そうですね．まだgoroutineを書くの慣れてないのでコードが怪しいかもしれません．

goos: darwin
goarch: amd64
pkg: github.com/raahii/go-sandbox/permutations
BenchmarkPermute1-4  2    684403978 ns/op   637542560 B/op   9895161 allocs/op
BenchmarkPermute2-4  5    285790686 ns/op   377401424 B/op   3628802 allocs/op
BenchmarkPermute3-4  5    216943042 ns/op   377401440 B/op   3628802 allocs/op
BenchmarkPermute4-4  1   1215330546 ns/op   290305888 B/op   3628817 allocs/op
PASS
ok      github.com/raahii/go-sandbox/permutations       7.580s