Problem
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;
}
}
Solution
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.
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.