c# - 排列算法优化

Question

我有这个排列代码工作完美，但它生成代码的速度不够快，我需要帮助优化代码以运行得更快，请重要的是结果保持不变，我见过其他算法，但它们没有不考虑输出长度和相同的角色声誉，这些都是有效的输出。如果我可以将其转换为包含 28 个字母数字字符的 for 循环，那就太棒了。下面是我正在寻求优化的当前代码。

namespace CSharpPermutations
{

public interface IPermutable<T>
{
    ISet<T> GetRange();
}

public class Digits : IPermutable<int>
{
    public ISet<int> GetRange()
    {
        ISet<int> set = new HashSet<int>();
        for (int i = 0; i < 10; ++i)
            set.Add(i);
        return set;
    }
}

public class AlphaNumeric : IPermutable<char>
{
    public ISet<char> GetRange()
    {
        ISet<char> set = new HashSet<char>();
        set.Add('0');
        set.Add('1');
        set.Add('2');
        set.Add('3');
        set.Add('4');
        set.Add('5');
        set.Add('6');
        set.Add('7');
        set.Add('8');
        set.Add('9');
        set.Add('a');
        set.Add('b');

        return set;
    }
}


public class PermutationGenerator<T,P> : IEnumerable<string>
    where P : IPermutable<T>, new()
{

    public PermutationGenerator(int number)
    {
        this.number = number;
        this.range = new P().GetRange();
    }

    public IEnumerator<string> GetEnumerator()
    {
        foreach (var item in Permutations(0,0))
        {
            yield return item.ToString();
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        foreach (var item in Permutations(0,0))
        {
            yield return item;
        }
    }

    private IEnumerable<StringBuilder> Permutations(int n, int k)
    {
        if (n == number)
            yield return new StringBuilder();

        foreach (var element in range.Skip(k))
        {
            foreach (var result in Permutations(n + 1, k + 1))
            {
                yield return new StringBuilder().Append(element).Append(result);
            }
        }
    }

    private int number;
    private ISet<T> range;

}

class MainClass
{
    public static void Main(string[] args)
    {
        foreach (var element in new PermutationGenerator<char, AlphaNumeric>(2))
        {
            Console.WriteLine(element);
        }
    }
}
}

感谢您提前做出的努力。

Answer 1

你输出的是两个集合的笛卡尔积；第一组是字符“0123456789ab”，第二组是字符“123456789ab”。

Eric Lippert 写了一篇著名的文章来演示 how to use Linq to solve this 。

我们可以将其应用于您的问题，如下所示:

using System;
using System.Collections.Generic;
using System.Linq;

namespace Demo;

static class Program
{
    static void Main(string[] args)
    {
        char[][] source = new char[2][];

        source[0] = "0123456789ab".ToCharArray();
        source[1] = "0123456789ab".ToCharArray();

        foreach (var perm in Combine(source))
        {
            Console.WriteLine(string.Concat(perm));
        }
    }

    public static IEnumerable<IEnumerable<T>> Combine<T>(IEnumerable<IEnumerable<T>> sequences)
    {
        IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };

        return sequences.Aggregate(
            emptyProduct,
            (accumulator, sequence) =>
                from accseq in accumulator
                from item in sequence
                select accseq.Concat(new[] { item }));
    }
}    

您可以通过修改源数据将其扩展到 28 个字符:

source[0] = "0123456789abcdefghijklmnopqr".ToCharArray();
source[1] = "0123456789abcdefghijklmnopqr".ToCharArray();

如果您想了解其工作原理，请阅读我在上面链接的 Eric Lipper 的精彩文章。