Non-recursive permutations and strings generator

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)
{

someone suggested we should deal with the growing number of Zombies...

Easy Performance Win

The performance measurement is wholly inadequate, and when I run your code as provided it tells me that your code is slower than that provided by Rolfl.

Using BenchmarkDotNet to get sensible measurements (with the proviso that they are running on my machine, at the same time as it is doing a lot of other work), I can agree your method is faster than that provided by Rolfl, running in ~1.8 s rather than ~1.5 s for the 4-length string test.

There is, however, an easy way to do better: you shouldn't be initialising a new StringBuilder for each word: create one and clear it as you need. This tiny change halves the runtime for strings of length 4, giving ~700 ms.


// this loop seems to be the fastest ways to generate a string

You must have missed the most obvious option: fill an array! There are 2 obvious ways to do this: create a big array and use the appropriate overload of String..ctor (1), or create an array of the right length when we need it (2). Neither seems to give any real improvement over the StringBuilder for these short strings, certainly not enough to accept the reduction in readability and reusability (the StringBuilder method can be easily adapted to work with strings rather than chars, which will be important if non-ASCII-characters are needed) without better measurements.

Table of measurements:

|        Method | StringLength |        Mean |      Error |     StdDev |
|-------------- |------------- |------------:|-----------:|-----------:|
|         Rolfl |            3 |    36.57 ms |  0.7292 ms |  1.9590 ms |
|       T3chb0t |            3 |    32.51 ms |  0.6764 ms |  1.9732 ms |
| StringBuilder |            3 |    12.51 ms |  0.2493 ms |  0.7154 ms |
|        Array1 |            3 |    11.20 ms |  0.2233 ms |  0.5882 ms |
|        Array2 |            3 |    10.65 ms |  0.2538 ms |  0.7444 ms |
|         Rolfl |            4 | 1,849.73 ms | 36.1277 ms | 56.2465 ms |
|       T3chb0t |            4 | 1,472.04 ms | 28.1790 ms | 68.0553 ms |
| StringBuilder |            4 |   682.75 ms | 16.3137 ms | 48.1013 ms |
|        Array1 |            4 |   623.12 ms | 14.8381 ms | 43.2836 ms |
|        Array2 |            4 |   679.26 ms | 23.1619 ms | 67.5642 ms |

Test code: gist.

Char Sets Ranges

The StringGerator(CharSets) constructor could be made much tidier by using a List to accumulate the results (rather than shuffling IEnumerables), and using a helper method to create Ascii Ranges:

private static IEnumerable AsciiRange(char start, char end)
{
    if (end  (char)c);
}

public StringGenerator(CharSets charSets = CharSets.Lowercase)
{
    var chars = new List();

    if (charSets.HasFlag(CharSets.Lowercase))
    {
        chars.AddRange(AsciiRange('a', 'z'));
    }

    if (charSets.HasFlag(CharSets.Uppercase))
    {
        chars.AddRange(AsciiRange('A', 'Z'));
    }

    if (charSets.HasFlag(CharSets.Numbers))
    {
        chars.AddRange(AsciiRange('0', '9'));
    }

    _charSet = chars.ToArray();
}

This is much more maintainable, as there is reduced repetition, and you don't need an ASCII table at hand to make modifications.

Odometer is not reusable

I also don't like that Increase creates a another RolloverCounter at the very end of the enumeration: it is basically ignoring _gearCount. It has the consequence that when you 'reuse' the odometer, you end up with another gear on the end, and if you use it a few more times, you end up with another gear on the end...

For example, using just var _charSet = new char[] { 'a', 'b', 'c' };, the time you get the correct output:

a, b, c, aa, ab, etc.

using it again, you get:

aaaa, baaa, caaa, etc.

And again, the last a becomes a b... it's a total nightmare. It needs something like this on the end:

if (gear == _gearCount)
{
    // rollover
    Gears.RemoveRange(1, Gears.Count - 1);
    return true;
}
else
{
    return false;
}

A check to avoid the last gear being added in the first place would avoid an allocation which takes the list over its initial capacity:

if (gear < _gearCount)
    Gears.Add(new RolloverCounter(_min, _max, _min));

I don't know if reusability is a goal, but if it isn't then it should be documented. Honestly, the behaviour seems a bit weird from the outset, having gears introduced over-time.

Misc

-
I would be strongly inclined to specify the values for the CharSets enum since you are using them as default parameters (their values become part of the API, and so changing them becomes a breaking change).

-
The constructors for RolloverCounter could obvious do with some bounds checking and documentation (e.g. explaining that the 'default' value is the min, and the max is an exclusive upper-bound).

-
I don't like that Odometer.Gears is public, given it is mutable. I'd be strongly inclined to provide a readonly-view of it; however, un

StackExchange Code Review Q#104513, answer score: 4