Algorithm: Odometer / Brute force

Question

I want to write a odometer-like method in a C#-style-language, but not just using 0-9 for characters, but any set of characters. It will act like a brute-force application, more or less.

If I pass in a char-array of characters from 0 to J, and set length to 5, I want results like 00000, 00001, 00002... HJJJJ, IJJJJJ, JJJJJ.

Here is the base, please help me expand:

protected void Main()
{
    char[] chars = new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
     'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J' };

    BruteForce(chars, 5);
}

private void BruteForce(char[] chars, int length)
{
    // for-loop (?) console-writing all possible combinations from 00000 to JJJJJ
    // (when passed in length is 5)
    // TODO: Implement code...
}

Answer 1

Google for permutations.

If however you are just dealing with that 'hex' range, just do the following:

for (int i = 0; i < (1 << 24); i++)
  string s = i.ToString("X6");

Answer 2

This isn't quite a duplicate of "recursion instead of multi-loops" but it's pretty close. I'll write up a solution if this doesn't help you.

EDIT: Here's a non-recursive solution. The recursive one is slightly harder to return an IEnumerable<string> from, but returning an iterator gives a nice interface IMO :)

private static IEnumerable<string> GetAllMatches(char[] chars, int length)
{
    int[] indexes = new int[length];
    char[] current = new char[length];
    for (int i=0; i < length; i++)
    {
        current[i] = chars[0];
    }
    while (Increment(indexes, current, chars))
    {
        yield return new string(current);
    }
}

private static bool Increment(int[] indexes, char[] current, char[] chars)
{
    int position = indexes.Length-1;

    while (position >= 0)
    {
        indexes[position]++;
        if (indexes[position] < chars.Length)
        {
             current[position] = chars[indexes[position]];
             return true;
        }
        indexes[position] = 0;
        current[position] = chars[0];
        position--;
    }
    return false;
}

Answer 3

Hi Seb,

Below is a class I've used before for this exact purpose... as the name suggests, it essential counts in different Bases based on the number of characters in the character set provided. Hope it's useful...

public class BaseNCounter
{
    public char[] CharSet { get; set; }
    public int Power { get; set; }

    public BaseNCounter() { }

    public IEnumerable<string> Count() {
        long max = (long)Math.Pow((double)this.CharSet.Length, (double)this.Power);
        long[] counts = new long[this.Power];
        for(long i = 0; i < max; i++)
            yield return IncrementArray(ref counts, i);
    }

    public string IncrementArray(ref long[] counts, long count) {
        long temp = count;
        for (int i = this.Power - 1; i >= 0 ; i--) {
            long pow = (long)Math.Pow(this.CharSet.Length, i);
            counts[i] = temp / pow;
            temp = temp % pow;
        }

        StringBuilder sb = new StringBuilder();
        foreach (int c in counts) sb.Insert(0, this.CharSet[c]);
        return sb.ToString();
    }
}

Heres a couple of usage scenarios in a console app.

class Program
{
    static void Main(string[] args)
    {
        BaseNCounter c = new BaseNCounter() { 
            CharSet = new char [] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' }, 
            Power = 2};

        foreach(string cc in c.Count())
            Console.Write("{0} ,", cc);
        Console.WriteLine("");

        BaseNCounter c2 = new BaseNCounter()
        {
            CharSet = new char[] { 'x', 'q', 'r', '9'},
            Power = 3
        };
        foreach (string cc in c2.Count())
            Console.Write("{0} ,", cc);
        Console.Read();
    }
}

Answer 4

This is one of the solutions I've found. I like the compactness and separation of it:

public static void PerformBruteForce()
{
    char[] characters = new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
        'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J' };

    int length = 5; // Length of the string created by bruteforce
    int charactersLength = characters.Length;
    int[] odometer = new int[length];
    long size = (long)Math.Pow(charactersLength, length);

    for (int i = 0; i < size; i++)
    {
        WriteBruteForce(odometer, characters);
        int position = 0;
        do
        {
            odometer[position] += 1;
            odometer[position] %= charactersLength;
        } while (odometer[position++] == 0 && position < length);
    }
}

private static void WriteBruteForce(int[] odometer, char[] characters) {
    // Print backwards
    for (int i = odometer.Length - 1; i >= 0; i--) {
        Console.Write(characters[odometer[i]]);
    }
    Console.WriteLine();
}