順列をC#とF#で
Qiitaにも載せたんだけど、こっちにも書いておこう。
F#の方が圧倒的に短くなるのはまあ当然と言えば当然。
ちなみにC#の方のデータ構造はシーケンスだけど、F#の方は連結リストなので、そこだけ注意。
(F#の方もシーケンスにすることは可能だけど、そこは好みの問題)
public static class EnumerableEx { public static IEnumerable<IEnumerable<T>> Dist<T>(this IEnumerable<T> source, T element) { if (source.Any()) { var head = source.First(); var tail = source.Skip(1); yield return Enumerable.Repeat(element, 1).Concat(source); foreach (var source2 in tail.Dist(element)) yield return Enumerable.Repeat(head, 1).Concat(source2); } else { yield return Enumerable.Repeat(element, 1); } } public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> source) { if (source.Any()) { var head = source.First(); var tail = source.Skip(1); foreach (var source2 in tail.Permute()) foreach (var source3 in source2.Dist(head)) yield return source3; } else { yield return Enumerable.Empty<T>(); } } public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> source, int c) { if (c == 0) { yield return Enumerable.Empty<T>(); } else if (source.Any()) { var head = source.First(); var tail = source.Skip(1); foreach (var source2 in tail.Permute(c)) yield return source2; foreach (var source2 in tail.Permute(c - 1)) foreach (var source3 in source2.Dist(head)) yield return source3; } } }
let rec dist e = function | [] -> [[e]] | x::xs -> (e::x::xs)::[for ys in dist e xs -> x::ys] let rec permute = function | [] -> [[]] | x::xs -> List.collect (dist x) (permute xs) let rec permuteN n xs = match (n,xs) with | (0,_) -> [[]] | (_,[]) -> [] | (_,x::xs') -> (permuteN n xs') @ (List.collect (dist x) (permuteN (n-1) xs'))