I have this permutation code working perfectly but it does not generate the code fast enough, I need help with optimizing the code to run faster, please it is important that the result remains the same, I have seen other algorithms but they don't into consideration the output length and same character reputation which are all valid output. if I can have this converted into a for loop with 28 characters of alphanumeric, that would be awesome. below is the current code I am looking to optimize.

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);
        }
    }
}
}

Thanks for your effort in advance.

CodePudding user response：

What you're outputting there is the cartesian product of two sets; the first set is the characters "0123456789ab" and the second set is the characters "123456789ab".

Eric Lippert wrote a well-known article demonstrating how to use Linq to solve this.

We can apply this to your problem like so:

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 }));
    }
}    

You can extend this to 28 characters by modifying the source data:

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

If you want to know how this works, read Eric Lipper's excellent article, which I linked above.

CodePudding user response：

Consider

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

Permutations is a recursive function that implements an iterator. So each time the .MoveNext() method is will advance one step of the loop, that will call MoveNext() in turn etc, resulting in N calls to MoveNext(), new StringBuilder, Append() etc. This is quite inefficient.

A can also not see that stringBuilder gives any advantage here. It is a benefit if you concatenate many strings, but as far as I can see you only add two strings together.

The first thing you should do is add code to measure the performance, or even better, use a profiler. That way you can tell if any changes actually improves the situation or not.

The second change I would try would be to try rewrite the recursion to an iterative implementation. This probably means that you need to keep track of an explicit stack of the numbers to process. Or if this is to difficult, stop using iterator blocks and let the recursive method take a list that it adds results to.