Как сделать эффективный алгоритм перебора всех возможных значений?

Question

[Негр Виталя]

Допустим у нас есть набор символов: a, b, c. А также есть диапазон от a до cc(

этот самый диапазон

a, b, c, aa, ba, ca, ab, bb, cb, ac, bc, cc

). То есть в диапазон должно входить 3^2=9 значений, которые нужно сгенерировать и перебрать. У меня было идея создать целочисленную переменную, к которой с каждым циклом прибавлять 1, и уже после этого делить на 3, 9 и т.д., но при работе с большьшой длиной это будет занимать большое количество памяти и + с каждым увеличением длины нужно будет совершать ещё большее число математических операций, тем самым создавая большую нагрузку на процессор.

Comments

[Akina]

a, b, c, aa, ba, ca, ab, bb, cb, ca, cb, cc

Что-то он какой-то странный. Где ac, bc? почему два cb?

У меня было идея

Это обычный перевод в троичную систему счисления. Только на своём наборе "цифр".

[Lynn «Кофеман»]

> Это обычный перевод в троичную систему счисления
Не совсем. В троичной системе «a» и «aa» неотличимы.

Скорее это стандартная задача генерации размещений с повторениями

[Негр Виталя]

a, b, c, aa, ba, ca, ab, bb, cb, ca, cb, cc
Что-то он какой-то странный. Где ac, bc? почему два cb?

ошибка вышла

[Wataru]

Негр Виталя, И еще, почему "То есть в диапазон должно входить 3^2=9 значений", когда их там 12 (три однобуквенных и 9 двухбуквенных). Тоже опечатка?

Диапазон может быть любой? Вроде от "ab" до "ccabc"? Или, например, он включает все строки длины от 1 до N?

[Shavadrius]

У вас есть алфавит (a,b,c) с основанием 3 и диапазон в этом алфавите.
Вся задача сводится к тому чтобы перевести первое число диапазона в десятичный uint (first), второе число в десятичный uint(second) и пройти циклом от first до second, переводя переменную-счетчик обратно в свою придуманную систему (с алфавитом (a,b,c) и основанием 3).

[Stalker_RED]

Негр Виталя,

ошибка вышла

погуляла немного, и снова вошла!

Вам никто не даст нормальній ответ пока вы не обозначите для чего это все и какие ограничения.
Потому что перебрать девять значений - это ерунда даже для микроконтроллера. Сложности будут на большом количестве элементов или длине последовательности, но вы не говорите какие у вас ограничения.
А сам алгоритм известен очень давно, он есть и в википедии и в учебниках, вот и ролик с объяснением пошаговым есть https://www.youtube.com/watch?v=CCecE9PAjgM

[Alexandroppolus]

Lynn «Кофеман»,

> Это обычный перевод в троичную систему счисления
Не совсем. В троичной системе «a» и «aa» неотличимы.

ну здесь отдельно можно применить троичную систему для чисел из одной цифры и отдельно для чисел из двух

[Негр Виталя]

Wataru, да, вот так вот

[Wataru]

Негр Виталя, поподробнее отвечайте, пожалуйста на утосняющие вопросы. Иначе я просто не смогу вам ничего ответить.

Answer 1

[GavriKos]

Если у вас все значения - то цикл в цикле. Что там еще оптимизировать. Хотя 9 значений можно и константами вбить. Не сильно понятно что вы хотите оптимизировать и зачем

Comments

[Негр Виталя]

Ну да, вы же тоже в ручную пишете 228 вложенных циклов?

[GavriKos]

Негр Виталя, откуда 228? 2 цикла

Answer 2

[Сергей П]

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

Такому алгоритму не нужно памяти сверх необходимого для хранения одной последовательности, плюс небольшая константа для переменных. В общем, инкрементация в среднем за O(log_M(N)), где M - размер алфавита, а N - число знаков.

У вас, кстати, еще ошибка:

То есть в диапазон должно входить 3^2=9 значений,

3^2+3^1

Comments

[Alexandroppolus]

инкрементация в среднем за O(log_M(N))

в среднем будет за О(1)

[Негр Виталя]

У вас, кстати, еще ошибка:

То есть в диапазон должно входить 3^2=9 значений,

3^2+3^1

Очень проблематично писать степени на клавиатуре.