Вычисление N-го шага перестановки?

Question

У меня есть символ [26] из букв az и nested для операторов. Я создаю список последовательностей, таких как:

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

Ух ты, два вопроса за один день , которые можно решить с помощью декартовых произведений. Удивительно.

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

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

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

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