Inspired by Sam's question (Brute-force string generator) and rolfl's really short version of the algorithm I started to experiment with a different approach and created one that seems to run a little bit faster (about 40-50ms for a string of length 4). As it doesn't really optimize the orginal algorithm but is a complete different one I thought I let you review it.
Actually it's really simple although it requires signifficantly more code then the original example and expecially the opmizided one.
To generate the permutations I wrote an Odometer class with a RolloverCounter that works like an odometer in a car. Each odometer gear-value is an index in the charSet array so based on these indexes I create a string.
It doesn't run in parallel yet but I made some preparations to implement it later. The RolloverCounter and the Odometer can start at some random number and continue from there so the whole range of possible permutations can be devided into sub-odometers and run on different threads.
I also shortened the char array to be generated from ascii codes and allowed the user to specify which character set he would like to use.
CharSets
[Flags]
public enum CharSets
{
Lowercase,
Uppercase,
Numbers,
Special
}
RolloverCounter
public class RolloverCounter
{
private readonly int _min;
private readonly int _max;
private int _value;
public RolloverCounter(int min, int max, int value)
{
_min = min;
_max = max;
_value = value;
}
public RolloverCounter(int min, int max) : this(min, max, min)
{
}
public int Value { get { return _value; } }
// increases the counter and returns true if rolledover
public bool Increase()
{
if (++_value < _max)
{
return false;
}
_value = _min;
return true;
}
// makes things easier
public static explicit operator int (RolloverCounter rolloverCounter)
{
return rolloverCounter._value;
}
}
Odometer
public class Odometer
{
private readonly int _gearCount;
private readonly int _min;
private readonly int _max;
public Odometer(int gearCount, int min, int max, params int[] gearValues)
{
_gearCount = gearCount;
_min = min;
_max = max;
Gears =
gearValues.Length > 0
// start at the specified state - for multithreading
? gearValues.Select(x => new RolloverCounter(min, max, x)).ToList()
// start at min
: new List<RolloverCounter>(gearCount) { new RolloverCounter(min, max) };
Max = max;
}
public int Max { get; private set; }
public List<RolloverCounter> Gears { get; private set; }
// increases the odometer and returns true if rolledover
public bool Increase()
{
var gear = 0;
while (gear < Gears.Count && Gears[gear].Increase())
{
gear++;
// add new gear
if (Gears.Count - 1 < gear)
{
Gears.Add(new RolloverCounter(_min, _max, _min));
break;
}
};
// rollover
return gear == _gearCount;
}
}
StringGenerator
public class StringGenerator
{
private readonly char[] _charSet;
public StringGenerator(CharSets charSets = CharSets.Lowercase)
{
var chars = Enumerable.Empty<char>();
if (charSets.HasFlag(CharSets.Lowercase))
{
chars = chars.Concat(Enumerable.Range(97, 122 - 97 + 1).Select(c => (char)c));
}
if (charSets.HasFlag(CharSets.Uppercase))
{
chars = chars.Concat(Enumerable.Range(65, 90 - 65 + 1).Select(c => (char)c));
}
if (charSets.HasFlag(CharSets.Numbers))
{
chars = chars.Concat(Enumerable.Range(48, 57 - 48 + 1).Select(c => (char)c));
}
_charSet = chars.ToArray();
// shorter char set for debugging
//charSet = Enumerable.Range(97, 99 - 97 + 1).Select(c => (char)c).ToArray();
}
public IEnumerable<string> GenerateStrings(int count)
{
// todo: here I'll need to calc the number of permutations and split the
// the odometer into ranges
var odometer = new Odometer(count, 0, _charSet.Length);
do
{
// this loop seems to be the fastest ways to generate a string
// I tested a few other options like:
// new string(odometer.Gears.Select(x => _charSet[(int)x]).ToArray())
// but they were all much slower
var result = new StringBuilder(odometer.Gears.Count);
foreach (var gear in odometer.Gears)
{
result.Append(_charSet[(int)gear]);
}
yield return result.ToString();
} while (!odometer.Increase());
}
}
Test code
var stringCount = 0;
StopwatchHelper.Measure(() =>
{
var stringGenerator = new StringGenerator(CharSets.Lowercase | CharSets.Numbers);
var maxStringLength = 4;
var strings = stringGenerator.GenerateStrings(maxStringLength).ToList();
stringCount = strings.Count;
},
sw => Console.WriteLine($" My: {sw.ElapsedMilliseconds} ms"));
// measures @rolfl's optimized version
StopwatchHelper.Measure(() =>
{
var strings2 = new List<string>();
var bruteForce3 = new BruteForce3();
for (var i = 0; i < stringCount; i++)
{
var generatedString = bruteForce3.GenerateString();
strings2.Add(generatedString);
}
},
sw => Console.WriteLine($"Optimized: {sw.ElapsedMilliseconds} ms"));
Console.ReadKey();
Helper
public static Stopwatch Measure(Action measureAction, Action<Stopwatch> resultAction = null)
{
var stopwatch = new Stopwatch();
stopwatch.Start();
measureAction();
stopwatch.Stop();
resultAction?.Invoke(stopwatch);
return stopwatch;
}
