开发者

C# - Finding all permutations of the letters in a string with some letters repeated

I am having problems calculating permutations for strings containing multiple instances of a letter (e.g. "HRWSOROE" where 'O' and 'R' are in the string twice. The algorithm I am using

public static class Extensions
{
    public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> source)
    {
        if (source == null) throw new ArgumentNullException("source");
        return PermutationsImpl(source, Enumerable.Empty<T>());
    }

    private static IEnumerable<IEnumerable<T>> PermutationsImpl<T>(IEnumerable<T> source, IEnumerable<T> prefix)
    {
        if (!source.Any()) yield return prefix;
        foreach (var permutation in source.SelectMany(x => PermutationsImpl(source.Except(Yield(x)), prefix.Union(Yield(x)))))
            yield return permutation;
    }

    private static IEnumerable<T> Yield<T>(this T element)
    {
        yield return element;
    }
}

Seems to work, but ignores duplicate letters - so instead of calculating permutations on "HRWSOROE" the permutations are being calculated on "HRWSOE". If someone would be kind enough to review what I h开发者_如何学运维ave and let me know what they think, I'd appreciate it.

Thanks!


The problem here seems to be the source.Except(Yield(x)) part in the LINQ line in PermutationsImpl().

It's comparing and removing all the values in the source which match the values in 'x'.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜