Расчет этапа N-й перестановки?

Question

У меня есть символ [26] буквы аза и через вложенные для заявлений я выпускающий список последовательностей, таких как:

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

В настоящее время программное обеспечение написано, чтобы создать список всех возможных значений из aaa-zzz, а затем поддерживает индекс и проходит через каждый из них, выполняя операцию над ними.

Этот список, очевидно, большой, он не смехотворно большой, но он дошел до того, что объем памяти слишком велик (есть и другие области, на которые смотрят, но это тот, который у меня есть).

Я пытаюсь создать формулу, в которой я могу сохранить индекс, но удаляю список последовательностей и вычисляю текущую последовательность на основе текущего индекса (так как время между операциями между последовательностями длинное).

Например:

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 
} 

Я попытался разработки небольшой пример с использованием подмножества (ABC) и пытается индексировать в этом с помощью деления по модулю, но у меня возникают проблемы, думая, сегодня и я озадачен.

Я не прошу ответа, просто любая помощь. Может быть, удар в правильном направлении?

Answer 1

Подсказка: Подумайте, как напечатать число в базе 26 вместо базы 10 и буквы вместо цифр. Каков общий алгоритм отображения числа в произвольной базе?

Спойлер: (прокрутка вправо для просмотра)

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

Answer 2

Нечто подобное должно работать, если 26 символов:

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

Answer 3

Вау, two questions in one day, которые могут быть решены с помощью декартовых произведений , Удивительно.

Вы можете использовать Eric Lippert's LINQ snippet для генерации всех комбинаций значений индекса. Этот подход приводит к потоковому набору значений, поэтому они не требуют хранения в памяти. Этот подход прекрасно отделяет логику генерации кодов от сохранения состояния или выполнения вычисления с кодом.

код Эрика для всех комбинаций:

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

Теперь вы можете написать:

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

Код выше генерирует потоковую последовательность всех строк кода из aaa в zzz.Теперь вы можете использовать это в другом месте, где вы выполняете вашу обработку:

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

Answer 4

Есть несколько способов решить вашу проблему, но вариант заключается в создании последовательности на лету вместо того, чтобы хранить его в списке:

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

вы можете перечислить все строки:

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

Этот код не использует индексы на всех, но это позволяет создать петлю вокруг последовательности строк, используя простые кода и без сохранения строк.