Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / алгоритм последовательной генерации строк aaa-zzz / 25 сообщений из 70, страница 1 из 3
  1  все
15.06.2010, 14:16:59
    #36687704
fleandr
fleandr
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм последовательной генерации строк aaa-zzz
Что то я туплю. как правильно сделать сабж.(можно просто строчку из числ кодов)
вариант вида

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
| Ответить | Цитировать | Написать  
15.06.2010, 14:20:08
    #36687711
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм последовательной генерации строк aaa-zzz
Тебя смущает 20 вложенных циклов или невозможность параметризировать количество циклов?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.06.2010, 14:25:45
    #36687732
Нахлобуч
Нахлобуч
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм последовательной генерации строк aaa-zzz
Перейди в систему счисления по основанию 26.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.06.2010, 14:29:26
    #36687749
rstudio
rstudio
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм последовательной генерации строк aaa-zzz
три вложенных цикла нормально. Не нужны эти джедайские методики с делением и остатком.
Понимать код будет гораздо проще
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.06.2010, 14:31:16
    #36687757
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм последовательной генерации строк aaa-zzz
fleandr,

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

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

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

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

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

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

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

не понял, а зачем там 20 вложенных циклов ?
длина строки может менятся ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.06.2010, 14:41:46
    #36687816
rstudio
rstudio
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм последовательной генерации строк aaa-zzz
да, тогда можно рекурсивно
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.06.2010, 14:42:02
    #36687819
fleandr
fleandr
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм последовательной генерации строк aaa-zzz
считай длину строки параметром
я просто не могу смотреть на 12 вложенных циклов в коде
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.06.2010, 14:50:38
    #36687843
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм последовательной генерации строк aaa-zzz
rstudioда, тогда можно рекурсивно

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

наверно это оптимальный алгоритм
Всё верно. Если ты изучал ЦУ и МПС, то так работает сумматор. Только для оптимизации несколько двоичных разрядов объединяются в группы и суммирование групп происходит шифратором (или дешифратором не помню но это непринципиально). Это самый быстрый метод сложения двух двоичных чисел в природе. Быстрее не бывает. Его можно еще упростить, взяв за правило, что второе слагаемое всегда будет равно единице и схема сумматора упроститься. Сумматор можно сгенерить искусственно исходя из введённого параметра N=20 (к примеру). А каждая цифра сумматора будет 5-битной (как раз для кодирования) букв алвавита. Генерацию сумматора надо-бы делать динамической компилляцией. Но в этом сабже я не силён, особенно в если язык не С# и не Java.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.06.2010, 14:56:06
    #36687864
rstudio
rstudio
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм последовательной генерации строк aaa-zzz
рекурсионный нормально. Вот в этом примере перебираются все слова с длиной на 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
| Ответить | Цитировать | Написать  
15.06.2010, 14:57:14
    #36687866
fleandr
fleandr
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм последовательной генерации строк aaa-zzz
рекурсивно написал:
но вот память кушает хотя и немного...
интересно а все таки как быстрее
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
| Ответить | Цитировать | Написать  
15.06.2010, 15:09:31
    #36687907
ZyK_BotaN
ZyK_BotaN
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм последовательной генерации строк aaa-zzz
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
| Ответить | Цитировать | Написать  
15.06.2010, 15:23:30
    #36687944
rstudio
rstudio
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм последовательной генерации строк aaa-zzz
Это большая проблема ?
У меня универсальная функция, ее можно запаковать в библиотеку.
Передаешь алфавит, длину слова и она возвращает все возможные вариации слов по этому алфавиту.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.06.2010, 15:24:34
    #36687947
rstudio
rstudio
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алгоритм последовательной генерации строк aaa-zzz
ZyK_BotaNrstudioда, тогда можно рекурсивно

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекурсивный памяти совершенно не жрет. В рекурсионных алгоритмах есть недостаток, они не могут разворачиваться "бесконечно". Стек не резиновый. Но вложенность в 100 вызовов функций, вполне может быть. Здесь же рекурсионный алгоритм разворачивается на длину слова, что весьма приемлимо.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / алгоритм последовательной генерации строк aaa-zzz / 25 сообщений из 70, страница 1 из 3
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 528ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1343619]:
 0ms
get settings:
 8ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 192ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 69ms
get tp. blocked users:
 1ms
others: 226ms
total:  528ms
x
x
Закрыть


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