Permutation algorithm Optimization

Question

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.

You've added an implementation, without actually mentioning what it does and what the end goal is — Abhinav Mathur
– Abhinav Mathur, Commented May 10, 2022 at 4:54
Why do none of your "permutations" have a zero as the second character? For example, they go from 0b to 11, skipping 10. Is that intended? — Matthew Watson
– Matthew Watson, Commented May 10, 2022 at 8:48
good point @MatthewWatson, that isn't the intention, I missed that. Thanks — Andy Mike
– Andy Mike, Commented May 10, 2022 at 9:31
The reason for all the IEnumerable<> stuff is, that you want to generate those permutations lazily, yes? In contrast to generating all permuatations into a list or array? — BitTickler
– BitTickler, Commented May 10, 2022 at 16:53

Matthew Watson · Accepted Answer · 2022-05-10 09:44:13Z

2

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.

edited May 10, 2022 at 9:44

answered May 10, 2022 at 9:17

Matthew Watson

111k12 gold badges179 silver badges301 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Andy Mike Over a year ago

Thank you, Matthew, this is my source data ABCDEFGJHJKMNPQRTUVWXY346789 and I need to output 8 sets, I can use your response as a starting point, this works as well thanks again. example: AAAAAD9W AAAAAD9X

JonasH · Accepted Answer · 2022-05-10 11:23:26Z

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.

Collectives™ on Stack Overflow

Permutation algorithm Optimization

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related