powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / алгоритм последовательной генерации строк aaa-zzz
70 сообщений из 70, показаны все 3 страниц
алгоритм последовательной генерации строк aaa-zzz
    #36687704
fleandr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Что то я туплю. как правильно сделать сабж.(можно просто строчку из числ кодов)
вариант вида

for(i1=0;i1<26;++i1)
for(i2=0;i2<26;++i2)
for(i3=0;i3<26;++i3)
{
a=i1+i2+i3; // объединяем результат
f(a) //используем...
}
не нравится

придумал вариант вида
for(i=0;i<26*26*26;++i)
{
считаем скока надо остаток от деления на 26
}
но тоже не нравится. плюс что делать если надо генерить варианты 20 символьных строк.

Как правильно сделать? туплю жестоко...
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687711
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Тебя смущает 20 вложенных циклов или невозможность параметризировать количество циклов?
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687732
Фотография Нахлобуч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Перейди в систему счисления по основанию 26.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687749
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
три вложенных цикла нормально. Не нужны эти джедайские методики с делением и остатком.
Понимать код будет гораздо проще
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687757
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
fleandr,

напиши рекурсивно
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687761
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
хотя для 3-х циклов, это лишнее.
я тоже думаю что 1-й вариант нормальный.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687795
fleandr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudio,

20 вложенных циклов это бяка...
я почти понял как сделать
http://www.insidepro.com/doc/003r.shtml

в общем надо:
1)сгенерить исходную строку.
2)пока не сдохнем
3)инкрементировать первый символ.
4)если код символа стал >27 сделать перенос и распространить его сколько надо

наверно это оптимальный алгоритм
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687804
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
fleandrrstudio,

20 вложенных циклов это бяка...
я почти понял как сделать
http://www.insidepro.com/doc/003r.shtml

в общем надо:
1)сгенерить исходную строку.
2)пока не сдохнем
3)инкрементировать первый символ.
4)если код символа стал >27 сделать перенос и распространить его сколько надо

наверно это оптимальный алгоритм

не понял, а зачем там 20 вложенных циклов ?
длина строки может менятся ?
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687816
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
да, тогда можно рекурсивно
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687819
fleandr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
считай длину строки параметром
я просто не могу смотреть на 12 вложенных циклов в коде
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687843
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudioда, тогда можно рекурсивно

только при рекурсивном(не в ленивых языках) придется выделять память, под весь список.
а хаскелл, ИМХО, нормально бы справился с задачей.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687860
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
fleandr
в общем надо:
1)сгенерить исходную строку.
2)пока не сдохнем
3)инкрементировать первый символ.
4)если код символа стал >27 сделать перенос и распространить его сколько надо

наверно это оптимальный алгоритм
Всё верно. Если ты изучал ЦУ и МПС, то так работает сумматор. Только для оптимизации несколько двоичных разрядов объединяются в группы и суммирование групп происходит шифратором (или дешифратором не помню но это непринципиально). Это самый быстрый метод сложения двух двоичных чисел в природе. Быстрее не бывает. Его можно еще упростить, взяв за правило, что второе слагаемое всегда будет равно единице и схема сумматора упроститься. Сумматор можно сгенерить искусственно исходя из введённого параметра N=20 (к примеру). А каждая цифра сумматора будет 5-битной (как раз для кодирования) букв алвавита. Генерацию сумматора надо-бы делать динамической компилляцией. Но в этом сабже я не силён, особенно в если язык не С# и не Java.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687864
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
рекурсионный нормально. Вот в этом примере перебираются все слова с длиной на 5 символов и алфавитом в 6 символов.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
        private void Form1_Load(object sender, EventArgs e)
        {
            char[] alphabet = new char[]{'a', 'b', 'c', 'd', 'e', 'f'};
            List<string> list = new List<string>();

            this.F(alphabet, list, "",  0 ,  5 );
        }

        void F(char[] alphabet, List<string> list, string word, int level, int wordLength)
        {
            if (level < wordLength)
            {
                foreach(char c in alphabet)
                    F(alphabet, list, word + c, level +  1 , wordLength);
            }
            else
            {
                list.Add(word);
            }
        }

...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687866
fleandr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
рекурсивно написал:
но вот память кушает хотя и немного...
интересно а все таки как быстрее
public static string symbols = "abcdefghijklmnop";

public static string growstr(string s)
{
if (s.Length == 5)
{
Console.WriteLine(s);
return "";
}
else
{
string res = "";
for (int i = 0; i < 10; ++i)
{
res =s+ symbols[i];
res = growstr(res);
}
return res;
}

}
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687907
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudioрекурсионный нормально. Вот в этом примере перебираются все слова с длиной на 5 символов и алфавитом в 6 символов.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
        private void Form1_Load(object sender, EventArgs e)
        {
            char[] alphabet = new char[]{'a', 'b', 'c', 'd', 'e', 'f'};
            List<string> list = new List<string>();

            this.F(alphabet, list, "",  0 ,  5 );
        }

        void F(char[] alphabet, List<string> list, string word, int level, int wordLength)
        {
            if (level < wordLength)
            {
                foreach(char c in alphabet)
                    F(alphabet, list, word + c, level +  1 , wordLength);
            }
            else
            {
                list.Add(word);
            }
        }



ключевое место, ты накапливаешь все элементы.
а нужно, вызвать процедуру для каждого.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687944
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Это большая проблема ?
У меня универсальная функция, ее можно запаковать в библиотеку.
Передаешь алфавит, длину слова и она возвращает все возможные вариации слов по этому алфавиту.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687947
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ZyK_BotaNrstudioда, тогда можно рекурсивно

только при рекурсивном(не в ленивых языках) придется выделять память, под весь список.
а хаскелл, ИМХО, нормально бы справился с задачей.

Опять начинается, Хаскелл, Лисп ... там где за три минуты в 5 строчек кода пишется на шарпе
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687951
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
все мы поняли, что когда речь идет о коротком понятном коде, все Лисперы копируют под кальку шарповый код и удаляют декларации. Возможны птицы высоты полета Ксени выдали нам бы что получше, но пока такой расклад по палатам
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687954
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudioZyK_BotaNrstudioда, тогда можно рекурсивно

только при рекурсивном(не в ленивых языках) придется выделять память, под весь список.
а хаскелл, ИМХО, нормально бы справился с задачей.

Опять начинается, Хаскелл, Лисп ... там где за три минуты в 5 строчек кода пишется на шарпе

я согласен, что решение с циклом самое лучшее.
я лишь сказал что рекурсия себя может быть приемлемой только для ленивого языка, и то уже начал в этом сомневаться.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687960
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudioЭто большая проблема ?
У меня универсальная функция, ее можно запаковать в библиотеку.
Передаешь алфавит, длину слова и она возвращает все возможные вариации слов по этому алфавиту.

функция то универсальная, но поставленную задачу решает плохо.
а если нужно вызвать процедуру для всех элементов с двадцатью порядками? памяти то хватит.

а решение с циклом, будет работать долго, но память не съест.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687963
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudioвсе мы поняли, что когда речь идет о коротком понятном коде, все Лисперы копируют под кальку шарповый код и удаляют декларации. Возможны птицы высоты полета Ксени выдали нам бы что получше, но пока такой расклад по палатам

причем здесь лисп и декларации?
я лишь предположил, что в ленивом хаскелле, рекурсивный алгоритм сможет выполнится с использованием малого объема памяти.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687970
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ZyK_BotaN
а решение с циклом, будет работать долго, но память не съест.

долго это примерно сколько ...
Давай посчитаем точно, допустим один миллиард комбинаций в секунду на самом мощном компьютере в мире. Получается ... 231 481 дней ... но памяти сожрет немного ....

зачем эти громкие слова ?
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687985
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudioZyK_BotaN
а решение с циклом, будет работать долго, но память не съест.

долго это примерно сколько ...
Давай посчитаем точно, допустим один миллиард комбинаций в секунду на самом мощном компьютере в мире. Получается ... 231 481 дней ... но памяти сожрет немного ....

зачем эти громкие слова ?

ну с 20-ю я загнул.
но зачем же придираться к мелочам?
смысл я надеюсь понятен, что итеративный алгоритм использует мало памяти, а рекурсивный ее жрет, и при этом скорости не добавляет. Наоборот требует выделения\освобождение памяти.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687988
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ZyK_BotaNrstudioвсе мы поняли, что когда речь идет о коротком понятном коде, все Лисперы копируют под кальку шарповый код и удаляют декларации. Возможны птицы высоты полета Ксени выдали нам бы что получше, но пока такой расклад по палатам

причем здесь лисп и декларации?
я лишь предположил, что в ленивом хаскелле, рекурсивный алгоритм сможет выполнится с использованием малого объема памяти.

Теория нам говорит. Что любой рекурсивный алгоритм можно переписать итеративно.
Просто на 95% я уверен что это не нужно ТС. Оптимизировать нужно только тогда, когда это критично.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36687991
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ZyK_BotaNrstudioZyK_BotaN
а решение с циклом, будет работать долго, но память не съест.

долго это примерно сколько ...
Давай посчитаем точно, допустим один миллиард комбинаций в секунду на самом мощном компьютере в мире. Получается ... 231 481 дней ... но памяти сожрет немного ....

зачем эти громкие слова ?

ну с 20-ю я загнул.
но зачем же придираться к мелочам?
смысл я надеюсь понятен, что итеративный алгоритм использует мало памяти, а рекурсивный ее жрет, и при этом скорости не добавляет. Наоборот требует выделения\освобождение памяти.

Рекурсивный памяти совершенно не жрет. В рекурсионных алгоритмах есть недостаток, они не могут разворачиваться "бесконечно". Стек не резиновый. Но вложенность в 100 вызовов функций, вполне может быть. Здесь же рекурсионный алгоритм разворачивается на длину слова, что весьма приемлимо.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688000
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudioZyK_BotaNrstudioвсе мы поняли, что когда речь идет о коротком понятном коде, все Лисперы копируют под кальку шарповый код и удаляют декларации. Возможны птицы высоты полета Ксени выдали нам бы что получше, но пока такой расклад по палатам

причем здесь лисп и декларации?
я лишь предположил, что в ленивом хаскелле, рекурсивный алгоритм сможет выполнится с использованием малого объема памяти.

Теория нам говорит. Что любой рекурсивный алгоритм можно переписать итеративно.
Просто на 95% я уверен что это не нужно ТС. Оптимизировать нужно только тогда, когда это критично.

напиши реализацию ф-и Аккермана, с константным использованием памяти.
хотя вроде есть такое решение, но я его не видел, и оно мне не очевидно.

возможно я вас запутал, говоря рекурсия, вместо рекурсивный процесс.
тогда извиняюсь.
ТС сам упоминал про 20 порядков.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688007
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudio
Рекурсивный памяти совершенно не жрет. В рекурсионных алгоритмах есть недостаток, они не могут разворачиваться "бесконечно". Стек не резиновый. Но вложенность в 100 вызовов функций, вполне может быть. Здесь же рекурсионный алгоритм разворачивается на длину слова, что весьма приемлимо.

у тебя там древовидная рекурсия, что ужасно.
она не сможет развернутся в цикл.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688010
fleandr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
мой код
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
    class Program
    {
        public static string symbols = "abcdefghijklmnop";

        public static string growstr(string s)
        {
            if (s.Length ==  12 )
            {
                Console.WriteLine(s);
                return "";
            }
            else
            {
                string res = "";
                for (int i =  0 ; i <  10 ; ++i)
                {
                    res =s+ symbols[i];
                    res = growstr(res);
                }
                return res;
            }
           
        }
        static void Main(string[] args)
        {
                      growstr("");
        }
}
кушает 2мб памяти и 10% проца
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688027
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ZyK_BotaNrstudio
Рекурсивный памяти совершенно не жрет. В рекурсионных алгоритмах есть недостаток, они не могут разворачиваться "бесконечно". Стек не резиновый. Но вложенность в 100 вызовов функций, вполне может быть. Здесь же рекурсионный алгоритм разворачивается на длину слова, что весьма приемлимо.

у тебя там древовидная рекурсия, что ужасно.
она не сможет развернутся в цикл.

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

хотя ну его этот алгоритм, без него можно обойтись
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688038
fleandr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вариант rstudio память хавает мегабайтами. хранить список - зло
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688043
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
fleandrвариант rstudio память хавает мегабайтами. хранить список - зло

с точки зрения преждевременной оптимизации, которая как известно из букваря корень всех зол - да. С точки зрения универсальности, законченности, рефакторинга и дебага. Гуд.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688051
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
fleandr,

кстате в коде у тебя уже глючок. Там 10 а там 12. А должни быть числа одинаковые.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688055
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudio
я еще раз говорю, любой рекурсионный алгоритм ( на шарпе ) с блекджеком и шлюхами, можно развернуть в цикл - это математический догмат.

хотя ну его этот алгоритм, без него можно обойтись

я же выше говорил, что под рекурсией имею ввиду рекурсивный процесс. т.е. процесс занимаемая память которого растет с ростом n. т.е. сложность больше О(1).
сразу прошу не придираться к такому неточному(и содержащему ошибки) определению.
главное суть понять.
и шарп тут не причем, это математическое понятия.
ты сможешь реализовать с помощью цикла, и собственного стека :). но это - рекурсивный алгоритм.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688059
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
у тебя снова неточность, уже в который раз. Я смогу это реализовать итеративно без собственного стека.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688061
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudiofleandr,

кстате в коде у тебя уже глючок. Там 10 а там 12. А должни быть числа одинаковые.

поэтому, захардкореные константы - зло
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688065
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudioу тебя снова неточность, уже в который раз. Я смогу это реализовать итеративно без собственного стека.

я говорил про расходование памяти О(1).
емнип, такое решение существует, но я его не видел.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688072
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudio,

я не мастер излагать свои мысли, советую обратится к вводному курсу по программированию чтобы вспомнить чем рекурсивный процесс отличается от итеративного.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688074
fleandr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
хардкод констант зло эт да...
глючка нет:
12 - это длна строки
10 - это длина алфавита
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688076
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ZyK_BotaNrstudioу тебя снова неточность, уже в который раз. Я смогу это реализовать итеративно без собственного стека.

я говорил про расходование памяти О(1).
емнип, такое решение существует, но я его не видел.

помойму ты не понимаешь как работает компьютер в данном случае.
Обьясняю на пальцах. В рекурсионном алгоритме для слова в 5 символов, будет держаться стек с вложенностью в 5 функций. С 10 символов - вложенность в десять функций. Если на вызов каждой функции с ее локальными переменными требуется допустим 50 байт, то число это можешь домножать соответственно на 5 или 10. Зависимость здесь линейная .
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688082
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
fleandrхардкод констант зло эт да...
глючка нет:
12 - это длна строки
10 - это длина алфавита

так алфавит у тебя не десять символов
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688084
fleandr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
мож кому не лень написать нерекурсивно... ))) вот и посмотрим как работать будет
меня пока рекурсия устраивает. спс всем ))
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688099
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudio,

на счет данной задачи, уже согласен. и рекурсивная пойдет, главное список не хранить.

а на счет магических возможностей си-шарпа решения рекурсивного алгоритма итеративно, вопрос остается в силе.

итеративно - это не линейная зависимость, а константная.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688136
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
fleandrмож кому не лень написать нерекурсивно... ))) вот и посмотрим как работать будет
меня пока рекурсия устраивает. спс всем ))

на счет итеративного вопрос снят.
рекурсивная ф-и, легче пишется, и легче читается.

я просто затупил с вложенностью. не сообразил, что она не больше длины слова.
а так, я больше люблю рекурсивные определения, чем итеративные, в том случае, если нет оверхеда по памяти.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688182
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ZyK_BotaNrstudio,

на счет данной задачи, уже согласен. и рекурсивная пойдет, главное список не хранить.

а на счет магических возможностей си-шарпа решения рекурсивного алгоритма итеративно, вопрос остается в силе.

итеративно - это не линейная зависимость, а константная.

Да это не магические возможности си-шапра Гыы. Ты просто не понимаешь сути программирования и сути императивного представления программ. Вот итеративное решение. Оно менее наглядное, конечно. И алфавит заменен числами. А так все теже яйца только в профиль.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
private void Form1_Load(object sender, EventArgs e)
        {
            int[] alphabet = new int[] {  1 ,  2 ,  3  };
            List<int[]> list = new List<int[]>();

            //this.F(alphabet, list, "aaaaaaaa",  0 ,  5 );

            this.F(alphabet, list, new int[] {  0 ,  0 ,  0  });
        }

        void F(int[] alphabet, List<int[]> list, int[] word)
        {
            int i =  0 ;
            bool bReset = false;
            
            while (true)
            {
                if (i < alphabet.Length)
                {
                    if(!bReset)
                        list.Add((int[])word.Clone()); ;

                    word[i]++;

                    if (word[i] == alphabet.Length)
                    {
                        word[i] =  0 ;
                        i++;
                        bReset = true;
                    }
                    else if(bReset)
                    {
                        i =  0 ;
                        bReset = false;
                    }
                }
                else
                {
                    break;
                }
            }
        }

...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688262
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudio,

то что эту задачу можно решить итеративно я уже упоминал выше(даже настаивал на таком решении).
я попросил итеративное решение ф-и Аккермана.

а итеративное решение обсуждаемой ф-и, я попробую записать и проще.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688286
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
пробуйте, как попробуете посмотрим на счет Аккермана
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688350
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
хсате на шот анхермана,
тоже самое вайл тру зациклились, пока не выполним условие на отрез отказываемса уходить
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688401
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudioхсате на шот анхермана,
тоже самое вайл тру зациклились, пока не выполним условие на отрез отказываемса уходить

нормально переписать в итеративный процесс не получилось.

в твоем решении я не увидел ф-и зависимой n(переменного размера слова).
да и ты уверен в правильности своего решения? а то у меня закрались сомнения.

и буду благодарен, если выложишь(или дашь ссылку) итеративное решение ф-и Аккермана.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688404
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ZyK_BotaNrstudioхсате на шот анхермана,
тоже самое вайл тру зациклились, пока не выполним условие на отрез отказываемса уходить

нормально переписать в итеративный процесс не получилось.

в твоем решении я не увидел ф-и зависимой n(переменного размера слова).


фикс вот здесь
Код: plaintext
1.
2.
3.
 while (true)
            {
                if (i < word.Length)

ZyK_BotaN
да и ты уверен в правильности своего решения? а то у меня закрались сомнения.


Код выдает правильный результат ? Выдает. Что еще нужно ?
Могут быть еще смол фиксы, но принцип остался тотже.
И вот я не уверен увижу ли решение которое ты обещал.

ZyK_BotaN
и буду благодарен, если выложишь(или дашь ссылку) итеративное решение ф-и Аккермана.

мне не оч. интересно заниматься довольно рутинной работой. Я просто показал что рекурсию можно довольно просто переписывать итеративно.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688406
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ZyK_BotaN
да и ты уверен в правильности своего решения? а то у меня закрались сомнения.



алгоритм проверил, была незначительная помарка.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688414
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudio
мне не оч. интересно заниматься довольно рутинной работой. Я просто показал что рекурсию можно довольно просто переписывать итеративно.

я уже выше упоминал, что сабжевый алгоритм легко преобразовать в итеративный.
а вот итеративной ф-и Аккермана я нигде не нашел.
а так, как ты упомянул выше, что понял как она реализуется, то я и попросил.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688422
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ZyK_BotaNrstudio
мне не оч. интересно заниматься довольно рутинной работой. Я просто показал что рекурсию можно довольно просто переписывать итеративно.

а вот итеративной ф-и Аккермана я нигде не нашел.


может быть здесь ?
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688448
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudio,

извиняюсь что морочил тебе голову, просто вспомнил упражнение которое не смог сделать, и подумал что то была ф-я Аккермана.
а задача была такая:
автор
Упражнение 3.18.
Напишите процедуру, которая рассматривает список и определяет, содержится ли в нем цикл, то
есть, не войдет ли программа, которая попытается добраться до конца списка, продвигаясь по
полям cdr, в бесконечный цикл. Такие списки порождались в упражнении 3.13.

Упражнение 3.19.
Переделайте упражнение 3.18, используя фиксированное количество памяти. (Тут нужна доста-
точно хитрая идея.)


сидел целый час, но ничего не придумал.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688457
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudio,

и в каком из тех решений, занимаемая память не зависит от n?
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688469
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
итеративной реализации ф-и Аккермана, наверное не существует.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688483
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Итеративных там несколько вариантов, но с минимумом памяти это нужно исследовать алгоритм в специализированной тулзе. Например кое что о алгоритме может рассказать Research Studio, токма Анкермана нужно переписать на васике
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688516
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
От смотри, от список вызовов функций
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688517
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
От как менялся от функции к функции параметр Ret
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688518
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну и собсно васиковская реализация Анкермана в эмуляторе RS
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36688956
Фотография ну я
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
void __fastcall TForm1::Button1Click(TObject *Sender)
{
const int n_symbols = 3;
char buf[ n_symbols + 1];
int imax = pow( 26, n_symbols);
for( int i = 0; i < imax; i++)
{
char* p = buf;
for( int k = 0, s = i; k < n_symbols ; k++)
{
*p ++ = s % 26 + 'a';
s /= 26;
}
*p = 0;
strrev( buf);
Memo1->Lines->Add( buf);
}
return;
}


> плюс что делать если надо генерить варианты 20 символьных строк.

поставить n_symbols = 20, если надо то использовать __int64
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36689127
d.p
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
d.p
Гость
Код: plaintext
perl -e "print \"$_\n\" for ('a' x 10 ... 'z' x 10);"
:)
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36689270
fleandr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ну яvoid __fastcall TForm1::Button1Click(TObject *Sender)
{
const int n_symbols = 3;
char buf[ n_symbols + 1];
int imax = pow( 26, n_symbols);
for( int i = 0; i < imax; i++)
{
char* p = buf;
for( int k = 0, s = i; k < n_symbols ; k++)
{
*p ++ = s % 26 + 'a';
s /= 26;
}
*p = 0;
strrev( buf);
Memo1->Lines->Add( buf);
}
return;
}


> плюс что делать если надо генерить варианты 20 символьных строк.

поставить n_symbols = 20, если надо то использовать __int64

не прокатит даже с инт64
2^64 =18446744073709551616
26^20 =19928148895209409152340197376
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36689275
Mozok
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ZyK_BotaN,

классический боянчик для linked list'ов. Рекурсивно будет где-то так:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
>(defun getCycle (slowL fastL)
    (declare (list slowL fastL))
    (if (not (endp fastL))
        (if (eq (car slowL) (car fastL))
            t
            ;else
            (getCycle (cdr slowL) (cddr fastL))
        )
    )
)
GETCYCLE
>(let ((x (list 'a 'b 'c)))
(rplacd (last x) x)
(print (getCycle x (cdr x)))
)
t
>
Можно переписать и итеративно, тогда будет фиксированный объем памяти использоваться.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36689276
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudio,

ткни меня носом.
не нашел я там алгоритма с константным потреблением памяти.
чем отличается итеративный алгоритм от рекурсивного советую почитать.

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

жаль там не пишут потребляемую память.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36689332
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ZyK_BotaNитеративной реализации ф-и Аккермана, наверное не существует.
Мне тоже не верится. Но не в итерации. А в реализацию Аккермана на конечных автоматах, для заранее неизвестного (m,n). Использование стеков, списков, variable arrays - будет фейком по определению.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36689350
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Такшо мне Нобелевку дадут если я Анкермана запишу итеративно с фиксированным или линейным потреблением памяти ?
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36689363
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я скажу спасиб. И попрошу исходник в свою коллекцию.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36689386
rstudio
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Курите скрины с Ресерч Студио. Определенные закономерности она уже показала, например как меняется М.

222 11 00 1111 0000 1111111 000000 ...
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36689979
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rstudio,

c фиксированным.
...
Рейтинг: 0 / 0
алгоритм последовательной генерации строк aaa-zzz
    #36691359
Фотография SQL_Lamer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
fleandr,

Нашел, писал когда - то на си шарпе, и вот такое у себя нашел :)

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
public class PermutationString
    {
        public PermutationString()
        {
            m_string = "a";
        }

        private string m_string;

        public static PermutationString operator ++(PermutationString word)
        {
            word.m_string = word.next(word.m_string);
            return word;
        }

        public static implicit operator String(PermutationString word)
        {
            return word.m_string;
        }

        public string next()
        {
            return next(m_string);
        }


        private string next(string word)
        {
            return next(char_list(word),  0 );
        }


        private string next(List<char> chars, int depth)
        {
            int
                idx_last = chars.Count -  1 ,
                min =  97 ,
                max =  122 ;


            if (chars[idx_last - depth] < max)
            {
                chars[idx_last - depth]++;

                if (depth >  0 )
                {
                    for (int i = idx_last - depth +  1 ; i < chars.Count; i++)
                        chars[i] = 'a';
                }
            }
            else if (depth < idx_last)
            {
                return next(chars, ++depth);
            }
            else
            {
                reset(chars);
                chars.Insert( 0 , (char)min);
            }

            return chars_to_string(chars);
        }


        private string chars_to_string(List<char> chars)
        {
            string res = "";

            foreach (char smbl in chars)
                res += smbl;

            return res;
        }


        private void reset(List<char> chars)
        {
            for (int i =  0 ; i < chars.Count; i++)
                chars[i] = 'a';
        }



        private List<char> char_list(string word)
        {
            List<char> lst = new List<char>();

            for (int i =  0 ; i < word.Length; i++)
                lst.Add(word[i]);

            return lst;
        }
    }

Зачем эту шняку написал, даже вспомнил.
Надо было с эксел работать, я начал столбцы перебирать по буквам, и тут захотелось мне универсальности
...
Рейтинг: 0 / 0
70 сообщений из 70, показаны все 3 страниц
Форумы / Программирование [игнор отключен] [закрыт для гостей] / алгоритм последовательной генерации строк aaa-zzz
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]