4
\$\begingroup\$

I have created an algorithm that can generate all possible combinations of a string given its length, and character set (it uses a custom numeral system to do this). How could I improve its performance and readability?

using System;
using System.Text;

public class Program
{
    public static void Main(string[] args)
    {       
        Bruteforce brute = new Bruteforce(9, new Range(0, Helpers.Chars.Length - 1));
        brute.PrintResults();

        Console.ReadKey(true);
    }
}

public class Bruteforce
{
    private int _Length;
    private Range _Range;

    public int Length
    {
        get
        {
            return _Length;
        }
    }

    public Range Range
    {
        get
        {
            return _Range;
        }
    }

    public Bruteforce(int length, Range range)
    {
        _Length = length;
        _Range = range;
    }

    public Bruteforce(int length, int min, int max)
    {
        _Length = length;
        _Range = new Range(min, max);
    }


    public void PrintResults()
    {
        int num = this.Range.Max;
        int[] arr = new int[this.Length];
        for (int c = 0; c < arr.Length; c++) arr[c] = this.Range.Min;
        while (true)
        {
            arr[0]++;
            if (arr[0] > this.Range.Max)
            {
                for (int i = 1; i < arr.Length; i++)
                {
                    if (arr[i - 1] > this.Range.Max)
                    {
                        arr[i - 1] = this.Range.Min;
                        arr[i]++;
                    }
                }
            }

            int num2 = arr[0];
            for (int i = 1; i < arr.Length; i++) num2 += arr[i];

            Console.WriteLine(Helpers.ArrayToString(arr));

            if (num2 == this.Range.Max * arr.Length) break;
        }
    }

    private void PrintArray(int[] arr)
    {
        for (int i = 0; i < arr.Length; i++)
        {
            if (i == arr.Length - 1)
            {
                Console.WriteLine(arr[i]);
            }
            else
            {
                Console.Write(arr[i] + ", ");
            }
        }
    }
}

public class Helpers
{
    public static char[] Chars = new char[] { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
    public static string ArrayToString(int[] arr)
    {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < arr.Length; i++)
        {
            if (arr[i] >= 0)
            {
                builder.Append(Helpers.Chars[arr[i]]);
            }
            else
            {
                throw new Exception();
            }
        }
        return builder.ToString();
    }
}

public class Range
{
    private int _Max, _Min;

    public int Max
    {
        get
        {
            return _Max;
        }
    }

    public int Min
    {
        get
        {
            return _Min;
        }
    }

    public Range(int min, int max)
    {
        _Max = max;
        _Min = min;
    }
}
\$\endgroup\$
  • \$\begingroup\$ I would call the permutation. en.wikipedia.org/wiki/Combination The has go to be a better way to know you are done than sum the entire array. \$\endgroup\$ – paparazzo Dec 30 '16 at 21:06
  • \$\begingroup\$ You can mark an answer when ever you want but 1 hour is not much time for feedback. \$\endgroup\$ – paparazzo Dec 30 '16 at 21:46
  • \$\begingroup\$ Sorry, I am new to stackexchange, I am still learning how to do things. \$\endgroup\$ – DD314 Dec 30 '16 at 21:56
4
\$\begingroup\$

string.Join(string, IEnumerable<T>)

Your method ArrayToString can be replaced with a single line :

public static string ArrayToString(int[] arr)
{
    return string.Join("", arr.Select(x => Chars[x]));
}

Your method PrintArray is never used but I assume it's just there for testing purpose.

Code style

Auto properties

You can use auto-properties to avoid explicitly creating a backing field for your variables :

private int _Length;

public int Length
{
    get
    {
        return _Length;
    }
}

Can be simplified to a single property :

public int Length { get; }

You can do the same for all of your properties.

Redundant this qualifier

You don't have to write this. everywhere e.g this.Range.Max as there are no variables with the same names there, the compiler will guess that you are referring to the container class.

\$\endgroup\$
  • \$\begingroup\$ I like your first suggestion, I never thought about string.Join. That would also get rid of that System.Text using statement. (I like programs that only have a single using statement). \$\endgroup\$ – DD314 Dec 30 '16 at 20:59
  • \$\begingroup\$ Also, I use the this qualifier because it's just my style. \$\endgroup\$ – DD314 Dec 30 '16 at 20:59
  • 1
    \$\begingroup\$ I agree with that this can be considered a personal preference it doesn't have any impact on performance but it also adds few characters of code to read. \$\endgroup\$ – Denis Dec 30 '16 at 21:00
  • 1
    \$\begingroup\$ Also, I tried using the string.Join method, and it only returned the numbers themselves, not the letters. I was using this method to take the raw data in the array, and convert it to the characters I need. It works by Looping through all the elements in the array and append the character that is at the index specified by the current value of the spot I am at in my array. \$\endgroup\$ – DD314 Dec 30 '16 at 21:13
  • 1
    \$\begingroup\$ I've edited the answer as I didn't notice those were indexes not the actual characters to convert into string. Try it out now. \$\endgroup\$ – Denis Dec 30 '16 at 21:14
4
\$\begingroup\$

Generating indexes

There is this principle that says that a class should have only a single responsibility. We call it the Single responsibility principle.

This means, that all the Bruteforce class should do, is to generate the indexes and not render the strings or write them to the console.

Apart from removing the print methods from it, there are few other things you can improve becuase the current while/if/for/if/ implementation is really complex. There's also a bug here arr[0]++; where you increase the first index so the resulting array skips one item - the first one so let's fix the PrintResults method.


for (int c = 0; c < arr.Length; c++) arr[c] = this.Range.Min;

If you like LINQ you can rewrite this loop as

var slots = Enumerable.Repeat(Range.Min, Length).ToArray();

but keep in mind that in some critical situations a peformance hit might be noticeable. However usualy you just want to use some convenience functions to get the work done.


The next part that needs to be simplified is this

while (true)
{
    arr[0]++;
    if (arr[0] > this.Range.Max)
    {
        for (int i = 1; i < arr.Length; i++)
        {
            if (arr[i - 1] > this.Range.Max)
            {
                arr[i - 1] = this.Range.Min;
                arr[i]++;
            }
        }
    }

    int num2 = arr[0];
    for (int i = 1; i < arr.Length; i++) num2 += arr[i];

    Console.WriteLine(Helpers.ArrayToString(arr));

    if (num2 == this.Range.Max * arr.Length) break;
}

There are particularly two things going on: increase the index and keep increasing it until all indexes are equal Range.Max. These two parts can be implemented separately.

var increase = new Func<bool>(() =>
{
    var currentSlot = 0;
    do
    {
        if (slots[currentSlot]++ < Range.Max)
        {
            return true;
        }
        // current slot exceeded
        else
        {
            // reset current slot
            slots[currentSlot++] = Range.Min;
        }
        // is last slot still less then Range.Max? if not then stop.
    } while (slots[Length - 1] <= Range.Max && currentSlot < Length);
    return false;
});

I let a local function take care of the indexes. It returns true if an index could be successfuly increased and false if not, this means we're finished.

The second part is quite small and just keeps this function running as long as necessary:

do
{
    action(slots);
} while (increase());

But what is action? This is the new delegate that is passed by the caller. He'll recive each index array via this parameter so the new signature is:

public void ForEach(Action<int[]> action)

Everything put together looks like this:

public void ForEach(Action<int[]> action)
{
    var slots = Enumerable.Repeat(Range.Min, Length).ToArray();

    var increase = new Func<bool>(() =>
    {
        // always start with the first slot
        var currentSlot = 0;
        do
        {
            // increase the current slot
            if (slots[currentSlot]++ < Range.Max)
            {
                return true;
            }
            // current slot exceeded
            else
            {
                // reset current slot and continue with the next one
                slots[currentSlot++] = Range.Min;
            }
        // is last slot still less then Range.Max? if not then stop.
        } while (slots[Length - 1] <= Range.Max && currentSlot < Length);
        return false;
    });

    do
    {
        action(slots);
    } while (increase());
}

Now that this method no longer prints the results I also no longer depends on the Helpers class..

Console.WriteLine(Helpers.ArrayToString(arr));

To use it, you call the ForEach with an anonymous delegate or you can pass a function that has the same signature as the delegate, this is void Foo(int[])

var brute = new Bruteforce(3, new Range(0, 2));
brute.ForEach(indexes =>
{
    Console.WriteLine(Helpers.ArrayToString(indexes));
});

More tips

public Bruteforce(int length, Range range)
{
    _Length = length;
    _Range = range;
}

public Bruteforce(int length, int min, int max)
{
    _Length = length;
    _Range = new Range(min, max);
}

Both these constructors do the same thing and initalize the same variables. You can chain them with :this(..) so that you don't repeat yourself:

public Bruteforce(int length, Range range)
{
    Length = length;
    Range = range;
}

public Bruteforce(int length, int min, int max)
: this(length, new Range(min, max))
{
}

public static string ArrayToString(int[] arr)
{
  StringBuilder builder = new StringBuilder();
  for (int i = 0; i < arr.Length; i++)
  {
      if (arr[i] >= 0)
      {
          builder.Append(Helpers.Chars[arr[i]]);
      }
      else
      {
          throw new Exception();
      }
  }
  return builder.ToString();
}

Here is actually no room for exceptions. If you run into one, then something is wrong with the conditions.

throw new Exception();

But if you throw exceptions, be so nice and try to communicate what happened, if possible why and if possible how to fix it.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the suggestions. I typically try to stay away from LINQ because I just can't understand it (It totally violates conventional programming methods for me). I have never heard about the Single responsibility principle, I will remember that for future reference. Something to note is that I am trying to go for performance. Any speed improvements are welcome. Thanks for your feed back! \$\endgroup\$ – DD314 Jan 4 '17 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.