順列を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'))