Алгоритм: одометр / грубая сила

Question

Я хочу написать метод, похожий на одометр, на языке стиля C #, но не просто с использованием 0-9 для символов, а для любого набора символов. Он будет действовать как приложение грубой силы, более или менее.

Если я передам массив символов из 0 в J и установлю длину 5, я хочу получить результаты, такие как 00000, 00001, 00002 .. HJJJJ, IJJJJJ, JJJJJ .

Вот база, пожалуйста, помогите мне расширить:

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

Это не вполне дубликат "рекурсии вместо мультициклов" , но это довольно близко. Я напишу решение, если это вам не поможет.

РЕДАКТИРОВАТЬ: Вот нерекурсивное решение. Рекурсивный немного сложнее вернуть IEnumerable<string>, но возврат итератора дает хороший интерфейс 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];
    }
    do
        {
            yield return new string(current);
        }
        while (Increment(indexes, current, chars));
}

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 2

Это одно из найденных мной решений. Мне нравится его компактность и разделение:

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

// length: The length of the string created by bruteforce
public static void PerformBruteForce(int length) {
    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();
}

Answer 3

Я только что опубликовал переписывание, которое я сделал для старой (но великолепной) рутины грубой силы, которую я делал еще в 90-х, она доступна из моего Gist и будет делать именно то, что вы просите:

https://gist.github.com/johanssonrobotics/11249060

Удачи!

Answer 4

Ниже приведен класс, который я использовал ранее для этой конкретной цели ... как следует из названия, он существенно учитывается в разных основах в зависимости от количества символов в предоставленном наборе символов. Надеюсь, это полезно ...

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();
    }
}

Вот несколько сценариев использования в консольном приложении.

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 5

Google для перестановок.

Если, однако, вы имеете дело с этим «шестнадцатеричным» диапазоном, просто сделайте следующее:

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