Calculating Nth permutation step?
I have a char[26] of the letters a-z and via nested for statements I'm producing a list of sequences like:
aaa, aaz... aba, abb, abz, ... zzy, zzz.
Currently, the software is written to generate the list of all possible values from aaa-zzz and then maintains an index, and goes through each of them performing an operation on them.
The list is obviously large, it's not ridiculously large, but it's gotten to the point where the memory footprint is too large (there are also other areas being looked at, but this is one that I've got).
I'm trying to produce a formula where I can keep the index, but do away with the list of sequences and calculate the current sequence based on the current index (as the time between operations between sequences is long).
Eg:
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
}
I've tried working out a small example using a subset (abc) and trying to index into that using modulo division, but I'm having trouble thinking today and I'm stumped.
I'm not asking for an answer, just any kind of help. Maybe a kick in the right direction?
4 ответа
Подсказка: Подумайте, как бы вы напечатали число в системе счисления 26 вместо 10 и с буквами вместо цифр. Каков общий алгоритм отображения числа в произвольной системе счисления?
Спойлер: (листайте вправо для просмотра)
int ndx1 = currentIndex / 26 / 26 % 26;
int ndx2 = currentIndex / 26 % 26;
int ndx3 = currentIndex % 26;
Вау, два вопроса за один день , которые можно решить с помощью декартовых произведений. Удивительный.
Вы можете использовать фрагмент 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...
}
Что-то вроде этого должно работать, предполагая, что 26 символов:
public string CurrentSequence(int currentIndex) {
return characters[currentIndex / (26 * 26)]
+ characters[(currentIndex / 26) % 26]
+ characters[currentIndex % 26];
}
Есть несколько способов решить вашу проблему, но один из вариантов — генерировать последовательность на лету, а не сохранять ее в списке:
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);
В этом коде вообще не используются индексы, но он позволяет создать цикл вокруг последовательности строк, используя простой код и не сохраняя строки.