Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Генерирование строк

Автор: Magister Y0da 7.2.2007, 16:38

мне нужен рекурсивный АЛГОРИТМ который генерирует все возможные строки составленные из данной, длинной от a до b

Пример:
у нас есть строка "123"
нам надо сгенерировать все строки от 1 до двух символов

Вывод:
1, 2, 3, 11, 12, 13, 21, 22, 23, 31, 32, 33

Автор: nerezus 7.2.2007, 18:12

Код


def getitem(x1=1,x2=3, alfavit = "abcdefghklmnopqrstuvwxyz"):
    for n in range(x1,x2+1):
        state = [0 for x in range(n)]
        memo = 0
        while memo==0:
            yield ''.join(map(alfavit.__getitem__,state))
            memo = 1
            for i in range(n):
                state[n-i-1] += memo
                if state[n-i-1]==len(alfavit):
                    state[n-i-1]=0
                    memo = 1
                else:
                    memo = 0
for x in getitem(1, 2, "123"):
    print x,

Код


1 2 3 11 12 13 21 22 23 31 32 33

Автор: Great 7.2.2007, 19:15

Код


#include <string>
#include <string.h>
#include <iostream>
#include <math.h>
using namespace std;
string getnext(int a, int b, string alpha)
{
    static long lcur = -1;
    int len = alpha.length() + 1;
_gen:
    if(lcur == -1)
        lcur = pow(len, a-1);
    if(lcur >= pow(len, b))
        return string("");
    char *buf = new char[b+3];
    itoa(lcur, buf, len);
    if(strchr(buf, '0'))
    {
        lcur ++;
        goto _gen;
    }
    for(int i=0;i<strlen(buf);i++)
        buf[i] = alpha.c_str()[buf[i] - '1'];
    buf[i] = 0;
    string ret = buf;
    delete buf;
    lcur ++;
    return ret;
}
int main()
{
    string s;
    do cout << (s = getnext(1, 3, "abc")) << " ";
    while(!s.empty());
    cout << endl;
    return 0;
}

Код


a b c aa ab ac ba bb bc ca cb cc aaa aab aac aba abb abc aca acb acc baa bab bac bba bbb bbc bca bcb bcc caa cab cac cba cbb cbc cca ccb ccc
Press any key to continue

Автор: Magister Y0da 8.2.2007, 21:34

Спасиба конечно
но я просил АЛГОРИТМ =)

Автор: SoWa 8.2.2007, 23:36

Не понимаю. Алгоритм- рекурсия. Этим все сказано. А чем, допустим, код на Си- не реализация алгоритма?

Автор: pushok 8.2.2007, 23:49

может вот это подойдет:

процедура П1 (s,a,s1) // s,s1 - строки, a - максимальная длина нужных нам слов
цикл от первой до последней буквы строки s:
если у нас нет слова s1+очередная буква строки s, тогда добавляем/пишем это слово.
если длина такой строки(s1+очередная буква строки s)<а, тогда П1(s,a,s1+очередная буква строки s).
конец цикла.
конец процедуры.

использование такой процедуры:

П1('123',2,''),
т.е. из строки '123' все строки не длинее двух символов начиная с пустой строки (пустая строка не учитывается).

в Delphi (Pascal)

Код


var
slovo:string;
l:integer;
slova:array of string; // массив всех слов, что у нас получились

function is_in(m:array of string;s:string):boolean; // проверяет наличие строки s в массиве m
var i:integer;
begin
 result:=false;
 for i:=0 to high(m) do
  if (m[i]=s) then
   begin
   result:=true;
   break;
   end;
end;

procedure p1(s:string;a:integer;s1:string); // рекурсивная процедура, состовляющая слова
var i:integer;
begin
 for i:=1 to length(s) do
  begin
  if not is_in(slova,s1+s[i]) then
   begin
   setlength(slova,length(slova)+1);
   slova[high(slova)]:=s1+s[i];
   end;
  if (length(s1+s[i])<a) then p1(s,a,s1+s[i]);
  end;
end;

...
write('Введите слово: ');
readln(s);
write('Введите длину слов: ');
readln(l);
p1(slovo,l,'');
...
// вывод слов на экран из массива slova
...

Автор: W4FhLF 9.2.2007, 10:34

Код


#include "stdio.h" 
#include "windows.h" 

int main(int argc, char* argv[]) 
{ 
        static char szPassword[256]; 
        ZeroMemory(szPassword, sizeof(szPassword)); 

        static char szAlphabet[256]; 
        strcpy(szAlphabet, "ABC"); 

        static unsigned char bAlphabet[256]; 
        ZeroMemory(bAlphabet, sizeof(bAlphabet)); 

        int i = 0, k = 0; 
        while (TRUE) 
        { 
                bAlphabet[k] = (unsigned char)szAlphabet[i]; 
                if (!szAlphabet[i]) 
                        break; 
                k = (unsigned char)szAlphabet[i]; 
                i++; 
        } 

        while (TRUE) 
        { 
                __asm 
                { 
                    pushad 
                    mov edi,offset szPassword 
                    mov ebx,offset bAlphabet 
                L1: movzx eax,byte ptr [edi] 
                    xlat 
                    cmp al,0 
                    je L3 
                    mov [edi],al 
                    jmp L5 

                L3: xlat 
                    stosb 
                    jmp L1 

                L5: popad 
                } 
                printf("%s\n", szPassword); 
        } 
        return 0; 
}

http://www.insidepro.com/doc/003r.shtml

Автор: DeadLine 10.2.2007, 20:51

Хм...Мне интересно А Йода не может по приведенному исходнику восстановить алгоритм?

Автор: Strannik 10.2.2007, 22:44

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

Автор: Magister Y0da 13.2.2007, 05:57

ну или хотя бы можно код на паскале, у меня с C\C++ и Python не очень smile

А блин увидел =))