net - test online c#

Algoritmo: Odómetro/fuerza bruta

Question

Quiero escribir un método tipo cuentakilómetros en un lenguaje de estilo C #, pero no solo usar 0-9 para caracteres, sino cualquier conjunto de caracteres. Actuará como una aplicación de fuerza bruta, más o menos.

Si paso una matriz de caracteres de 0 a J y establezco la longitud a 5, quiero resultados como 00000, 00001, 00002 ... HJJJJ, IJJJJJ, JJJJJ .

Aquí está la base, por favor ayúdenme a expandir:

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

A continuación hay una clase que he usado anteriormente para este propósito exacto ... como su nombre lo indica, es esencial contar en diferentes Bases en función del número de caracteres en el juego de caracteres provisto. Espero que sea útil ...

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

Aquí hay un par de escenarios de uso en una aplicación de consola.

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 2

Google para permutaciones.

Sin embargo, si solo estás tratando con ese rango ''hexagonal'', solo haz lo siguiente:

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

Answer 3

Esta es una de las soluciones que he encontrado. Me gusta la compacidad y la separación de la misma:

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 4

Acabo de publicar una reescritura que hice en una antigua (pero genial) rutina de fuerza bruta que hice en los años 90, está disponible en mi Gist y hará exactamente lo que estás pidiendo:

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

¡Buena suerte!

Answer 5

Esto no es exactamente un duplicado de "recursión en lugar de múltiples bucles", pero está bastante cerca. Escribiré una solución si esto no te sirve.

EDITAR: Aquí hay una solución no recursiva. El recursivo es un poco más difícil de devolver una IEnumerable<string> de IEnumerable<string> , pero devolver un iterador proporciona una interfaz agradable 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;
}