¿Calcular el paso de permutación enésimo?

Question

que tienen un char [26] de las letras az y anidados a través de las declaraciones que estoy produciendo una lista de secuencias como:

aaa, aaz... aba, abb, abz, ... zzy, zzz. 

Actualmente, el software está escrito para generar la lista de todos los valores posibles de aaa-zzz y luego mantiene un índice, y pasa por cada uno de ellos realizando una operación sobre ellos.

La lista es obviamente grande, no es ridículamente grande, pero se ha llegado al punto en que la huella de memoria es demasiado grande (también hay otras áreas que se miran, pero esta es una que tengo).

Estoy tratando de producir una fórmula donde pueda mantener el índice, pero elimine la lista de secuencias y calcule la secuencia actual en función del índice actual (ya que el tiempo entre operaciones es largo).

Ej:

char[] characters = {a, b, c... z}; 
int currentIndex = 29; // abd 

public string CurrentSequence(int currentIndex) 
{ 
    int ndx1 = getIndex1(currentIndex); // = 0 
    int ndx2 = getIndex2(currentIndex); // = 1 
    int ndx3 = getIndex3(currentIndex); // = 3 

    return string.Format(
     "{0}{1}{2}", 
     characters[ndx1], 
     characters[ndx2], 
     characters[ndx3]); // abd 
} 

He intentado elaborar un pequeño ejemplo usando un subconjunto (abc) y tratando de índice en que el uso de la división de módulo, pero estoy teniendo problemas para pensar hoy y estoy perplejo.

No estoy pidiendo una respuesta, cualquier tipo de ayuda. Tal vez una patada en la dirección correcta?

Answer 1

Sugerencia: Piense en cómo imprimiría un número en base 26 en lugar de base 10, y con letras en vez de dígitos. ¿Cuál es el algoritmo general para mostrar un número en una base arbitraria?

Alerón: (desplazarse hacia la derecha para ver)

                     int ndx1 = currentIndex/26/26 % 26; 
                         int ndx2 = currentIndex/26 % 26; 
                         int ndx3 = currentIndex % 26; 

Answer 2

Algo como esto se debe trabajar, asumiendo 26 caracteres:

public string CurrentSequence(int currentIndex) { 
    return characters[currentIndex/(26 * 26)] 
     + characters[(currentIndex/26) % 26] 
     + characters[currentIndex % 26]; 
} 

Answer 3

Wow, two questions in one day que pueden ser resueltos a través de productos cartesianos . Asombroso.

Puede usar Eric Lippert's LINQ snippet para generar todas las combinaciones de valores de índice. Este enfoque da como resultado un conjunto de valores de transmisión, por lo que no requieren almacenamiento en la memoria. Este enfoque separa muy bien la lógica de generar códigos para mantener el estado o realizar cálculos con el código.

código de Eric como todas las combinaciones:

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) 
{ 
    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; 
    return sequences.Aggregate( 
    emptyProduct, 
    (accumulator, sequence) => 
     from accseq in accumulator 
     from item in sequence 
     select accseq.Concat(new[] {item}));     
} 

Ahora puede escribir:

public static IEnumerable<string> AllCodes() 
{ 
    char[] characters = {a, b, c... z}; 
    IEnumerable<char[]> codeSets = new[] { characters, characters, characters }; 

    foreach(var codeValues in codeSets.CartesianProduct()) 
    { 
    yield return 
     string.Format("{0}{1}{2}", codeValues[0], codeValues[1], codeValues[2]); 
    } 
} 

El código anterior genera una secuencia de streaming de todas las cadenas de código aaa-zzz.Ahora puede utilizar esto en otro lugar donde se realiza el procesamiento:

foreach(var code in AllCodes()) 
{ 
    // use the code value somehow... 
} 

Answer 4

Hay varias maneras de resolver su problema, pero una opción es generar la secuencia sobre la marcha en lugar de almacenarla en una lista:

IEnumerable<String> Sequence() { 
    for (var c1 = 'a'; c1 <= 'z'; ++c1) 
    for (var c2 = 'a'; c2 <= 'z'; ++c2) 
     for (var c3 = 'a'; c3 <= 'z'; ++c3) 
     yield return String.Format("{0}{1}{2}", c1, c2, c3); 
} 

a continuación, puede enumerar todas las cadenas:

foreach (var s in Sequence()) 
    Console.WriteLine(s); 

Este código no utiliza índices en absoluto, sino que le permite crear un bucle alrededor de la secuencia de cadenas utilizando simples código y sin almacenar las cadenas.