C#：Permutation(順列の全列挙)を作成する
動機
受験していたAtCoder Beginner Contest 232(ABC232) でPermutationを利用する問題が出た。
順列のクラスを1から作っていて時間内に解けなかった。悔しい。
以下解説を見ると、Permutationなる関数がPythonやc++ならある模様。…ずりぃ！C#にはない！
なので今回作成しておくことにした。
特に、大体計算量が気になる処理に使われるので、なるべく早い処理にしたい。
クラス条件
- ジェネリックメソッドである
- 結果をすべて返却する
自分で作成
特に気にせず再帰処理で作れるだろうという考えで作成。
イメージ的にはごく普通に選択肢の木を作っていく感じ。
public static IEnumerable<IEnumerable<T>> Permutation3<T>(params T[] items)
{
//残り1回ならこれで終了
if (items.Count() == 1)
{
yield return new List<T>() { items.First() };
yield break;
}
for (int i = 0; i < items.Count(); i++)
{
var nextitems = items.ToList();
var itemx = nextitems[i];
nextitems.Remove(itemx);
//選んだものを除いたコレクションから再度選ぶ(再帰関数)
foreach (var c in Permutation3<T>(nextitems.ToArray()))
{
var newitem = new List<T>() { itemx };
newitem.AddRange(c);
yield return newitem.ToArray();
}
}
}
先人のやり方を参考にする
ぐぐったらいくつか出た。
(1)
Compareで比較できるという条件がありますが、比較を利用して配列の順序を交換していく処理。
(2)
偶然にも私の発想とほぼ同じ。
こちらよりも再帰処理を最大限簡潔に書いてる感じ。
処理速度評価
とりあえず上記の先人の処理を手前の実行環境で処理時間を評価する。
var r1 = Permutation1(Enumerable.Range(1, n).ToArray());
Console.WriteLine(r1.Count());
n=5(5!=120)とn=10(10!=3,628,800)で評価。
結果は5回試行した平均。
| ＼ | 私の処理 | (1) | (2) |
|---|---|---|---|
| n=5 | 0.00045s | 0.00018s | 0.00137s |
| n=10 | 6.586s | 1.662s | 35.274s |
どちらのケースも(1)が最も早いという結果に。
・・・自分の計算量見積もりがガバガバなことを再確認orz
重い所の特定
あれ？でも私の処理が(2)より早い理由は何だ？
・・・比較していろいろ試した結果、
- IEnumerable＜TSource＞ Except(i個目のT) よりもコピー→Remove(i個目のT)のほうが早い
- Concat()よりもAddRange()のほうが早い
という結果に。
これを踏まえて、(1)をベースにnが大きい時の効率を考えて高速化を目指し、以下を作成した。
最終Ver
//n個の数値オブジェクトの順列を返す(n!個)
public static IEnumerable<IEnumerable<T>> PermutationX<T>(params T[] items) where T : IComparable
{
int cnt = items.Count();
if (cnt < 10)
{
foreach (var p in Permutation1(items)) //(1)のPermutation
yield return p;
}
else
{
//nが10以上の場合、前半と後半に分割して処理を減らす
var combs = Combination(cnt, cnt / 2);
foreach (var comb in combs)
{
var Litems = new List<T>();
var Ritems = items.ToList();
foreach (var cc in comb)
{
Ritems.Remove(items[cc]);
Litems.Add(items[cc]);
}
var vL = PermutationX(Litems.ToArray());
var vR = PermutationX(Ritems.ToArray());
foreach (var l in vL)
{
foreach (var r in vR)
{
var plr = new List<T>();
plr.AddRange(l.ToList());
plr.AddRange(r.ToList());
yield return plr;
}
}
}
}
}
nCrのコンビネーションを数値として列挙するCombination(n,r)も同時に作成した。
//nCr列挙
private static IEnumerable<List<int>> Combination(int n, int r, int st = 0)
{
for (int i = st; i < n; i++)
{
//残り1回ならこれで終了
if (r == 1)
{
yield return new List<int> { i };
continue;
}
//iを獲る選択肢を列挙
foreach (var c in Combination(n, r - 1, i + 1))
{
var comb = new List<int>();
comb.Add(i);
comb.AddRange(c);
yield return comb;
}
//(iを獲らない選択肢は次のループで行われる)
}
}
処理速度評価(再)
処理速度はこんな感じ。
n=11(11!=39,916,880)を追加した。
| ＼ | 分割+(1) | (1) |
|---|---|---|
| n=5 | 0.00074106s | 0.00071038s |
| n=10 | 1.5163s | 1.8346s |
| n=11 | 17.623s | 33.612s |
nが10以上のときの高速化が達成できた。
以下のように数値以外のコレクションにしても分割+(1)のほうが早かったので、コレクションのサイズが大きくなければ有意な差はないと思われる。
var r1_x = Permutation1(new char[] { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' });
var r1_y = Permutation1(new string[] { "aaa","bbb","ccc","ddd","eee","fff","ggg","hhh","iii","jjj" });
注意点
Combinationとそれに伴う分割の計算量・メモリ占有もあるため、
if (cnt < 10)
の部分(分割境界)は9～10ぐらいが良い模様。（n=8～9のときは(1)のみのほうが早い）
未考察点
今回このためにCombination関数を作ったが、これの効率自体は未検証。
もっと早く出来るかもしれない。