• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

djthyrax

Todas as strings possíveis entre x e y de tamanho e cada caracter entre a e b

34 mensagens neste tópico

Algoritmo para fazer o que está escrito no título. :P

Postem aí soluções para este "problema" noutras linguagens :P

EDIT: Novo código, agora mais pequeno :P

// usando as letras que usei no titulo,
$limite = array('inf' => 97, 'sup' => 122); // 'inf' = a ; 'sup' = b

$tamanho = array('inf' => 3, 'sup' => 6, 'actual' => 0); // 'inf' = x ; 'sup' = y

for($tamanho['actual'] = $tamanho['inf']; $tamanho['actual'] <= $tamanho['sup']; $tamanho['actual']++) {
$vector = array();
$stop = false;
for($i = 0; $i < $tamanho['actual']; $i++)
	$vector[] = $limite['inf'];

while(!$stop){
	mostrar(); // não me chateiem por fazer output aqui, era a única opção, não ia propriamente armazenar os dados num vector... não haveria ram para isso 
	incr($tamanho['actual']-1);
}
}

function incr($chave){
global $vector, $limite, $stop;
if($vector[$chave]++ >= $limite['sup']){
	if($chave != 0){
		$vector[$chave] = $limite['inf'];
		incr($chave-1);
	}else $stop = true;
}
}

function mostrar(){
global $vector;
foreach($vector as $txt) echo chr($txt);
echo "\n";
}

Código antigo:

// usando as letras que usei no titulo,
$limite = array('inf' => 97, 'sup' => 122); // 'inf' = a ; 'sup' = b

$tamanho = array('inf' => 3, 'sup' => 6, 'actual' => 0); // 'inf' = x ; 'sup' = y

for($tamanho['actual'] = $tamanho['inf']; $tamanho['actual'] <= $tamanho['sup']; $tamanho['actual']++) {
$vector = array();
$stop = false;
for($i = 1; $i <= $tamanho['actual']; $i++)
	$vector[] = $limite['inf'];

$ultimo = count($vector)-1;

while(!$stop){
	mostrar(); // não me chateiem por fazer output aqui, era a única opção, não ia propriamente armazenar os dados num vector... não haveria ram para isso 
	if($vector[$ultimo]++ >= $limite['sup']){
		$vector[$ultimo] = $limite['inf'];
		incr($ultimo-1);
	}
}
}

function incr($chave){
global $vector, $limite, $stop;
if($vector[$chave]++ >= $limite['sup']){
	if($chave != 0){
		$vector[$chave] = $limite['inf'];
		incr($chave-1);
	}else $stop = true;
}
}

function mostrar(){
global $vector;
foreach($vector as $txt) echo chr($txt);
echo "\n";
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Podias dar um exemplo do output? Não me apetece analisar código PHP e só pelo título..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Podias dar um exemplo do output? Não me apetece analisar código PHP e só pelo título..

Output:

aaa

aab

aac

...

aaz

aba

abb

abc

abd

...

azz

baa

bab

bac

...

zzz

aaaa

aaab

aaac

aaad

...

aaaz

aaba

aabb

aabc

...

aazz

abaa

...

zzzz

aaaaa

aaaab

aaaac

...

zzzzzz

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

ah, por exemplo, uma password com 4 caracteres cujo charset vai de 0 a 9, ele dá as 10000 combinações?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

ah, por exemplo, uma password com 4 caracteres cujo charset vai de 0 a 9, ele dá as 10000 combinações?

Correcção, para uma password com 4 letras sem diferenciação maíusculas/minusculas, ele dá todas as combinações. :P
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

ah, por exemplo, uma password com 4 caracteres cujo charset vai de 0 a 9, ele dá as 10000 combinações?

Correcção, para uma password com 4 letras sem diferenciação maíusculas/minusculas, ele dá todas as combinações. :P

c'um catano :P isto é o chamado brute force (quando aplicado a passwords, etc etc)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

ah, por exemplo, uma password com 4 caracteres cujo charset vai de 0 a 9, ele dá as 10000 combinações?

Correcção, para uma password com 4 letras sem diferenciação maíusculas/minusculas, ele dá todas as combinações. :P

c'um catano :P isto é o chamado brute force (quando aplicado a passwords, etc etc)

Sim, o algoritmo dado poderá ser usado para brute forces, seja a passwords ou a outra coisa qualquer. Mas, no entanto, não passa de um gerador de strings. :)
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

em Haskell

comb mn mx inf sup = aux 1 [inf..sup] [[]] []
  where aux n l ac r  =
          if n > mx then r
          else let newl = [(h : t) | h <- l, t <- ac]
                   newr = if n >= mn then (r ++ newl) else r
               in aux (n + 1) l newl newr

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

sem testar, em C


char perm[15];

//n = numero de caracteres, a = inicial, b=final. Para chamar, fazer por exemplo go(0,3,97,122);

int go(int pos,int n,int a,int b) {
 int i;
 if (pos==n) {
   for (i=0;i<n;i++)
     printf("%c",perm[i]);
   putchar('\n');
 }
 else
   for (i=a;i<=b;i++) {
     perm[pos]=i;
     go(pos+1,n,a,b);
   }
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Também em Haskell

import Control.Monad

gerarStrings menor maior inicio final = concatMap (`replicateM` [inicio..final]) [menor..maior]

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Que eu saiba algoritmia passa muito mais pelo pseudocódigo do que mostrar algo em várias linguagens.

Fiquei na mesma e não percebi nada do que vocês fizeram!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Que eu saiba algoritmia passa muito mais pelo pseudocódigo do que mostrar algo em várias linguagens.

Fiquei na mesma e não percebi nada do que vocês fizeram!

Bem, no 1º post era pedido para mostrar soluções noutras linguagens. Algoritmia passa muito pouco por pseudocódigo. O pseudocódigo é muito limitado e quase ninguém usa para demonstrar algoritmos, sendo normalmente usado no inicio à programação.

Bem, como ainda ninguém explicou a solução, vou dar a via que segui para resolver o problema. Não sei se será útil, já que dei uso principalmente à Monad de Listas, um conceito muito poderoso que a sua implementação (penso eu) só existe em Haskell. Existem várias bibliotecas para outras linguagens que tentam implementar o conceito de Monads nessas linguagens, mas ainda não vi nenhuma bem conseguida.

Analizando o problema, até parece ser simples. E é, excepto o pequeno facto de ser strings de tamanho variável.

Então verificaremos primeiro como seria gerar uma string com apenas um tamanho.

Gerar todas as strings possíveis de tamanho x e cada caracter entre a e b

A resolução deste problema é bastante simples. Basta encadear vários ciclos para obter um caracter entre a e b. Ou seja, para gerar strings de tamanho x, irá ser necessário ter x ciclos encadeados.

Exemplo, para gerar todas as strings possiveis de tamanho 3 com caracteres entre "a" e "d".

lista = ['a','b','c','d']
listaStrings = listaVazia

paracada Char c1 em lista
    paracada Char c2 em lista
        paracada Char c3 em lista
              adiciona listaString  (c1, c2, c3)

Claro que podemos usar uma linguagem mais poderosa, com conceitos mais poderosos para exprimir os ciclos encadeados. Como Python e listas por compreensão.

lista = ['a', 'b', 'c', 'd']
[ [c1,c2,c3] for c1 in lista for c2 in lista for c3 in lista]

Então para resolver o problema inicial só basta saber quantos ciclos gerar dinâmicamente e encadealos. E aqui é que entra o conceito de monads de listas em Haskell.

O conceito de listas por compreensão em Python é não mais que uma cópia barata da versão de Haskell. Digo barata porque Python apenas suporta a funcionalidade normal de listas por compreensão, o conceito em Haskell vai muito mais além. Em Haskell as listas por compreensão é apenas açucar sintático para se exprimir mais facilmente o uso da Monad de Listas.

--O exemplo de python em Haskell seria
[[c1,c2,c3] | c1 <- lista, c2 <- lista, c3 <- lista]

--Que pode ser traduzido para
do 
  c1 <- lista
  c2 <- lista
  c3 <- lista
  return [c1,c2,c3]

-- Que e tambem acucar sintatico mas para as Monads em gerais
-- Que pode ser traduzido para codigo Haskell puro como

lista >>= \ c1 -> lista >>= \ c2 -> lista >>= \ c3 -> return [c1,c2,c3]

A notação "\ x -> blah" é a forma de definir uma função anónima em Haskell (também designada como função lambda), sendo x o argumento da função. O ">>=" é uma função monádica de ordem superior usada para interligar várias acções monádicas.

Não vou estar aqui a esplicar todo o conceito de Monads já que isso dava pano para mangas, basta apenas pensarem que uma acção monádica é uma função como outra qualquer. E como as funções estão para o Haskell como as Strings estão para o Perl, é bastante simples encadear dinâmicamente os ciclos.

Para começar, é simples definir uma função para replicar um elemento n vezes.

replicar 0 _ = []
replicar n elemento = elemento : replicar (n-1) elemento

-- replicar 5 'a'
-- ['a', 'a', 'a', 'a', 'a']

Este elemento é qualquer coisa inclusive funções. Portanto é fácil fazer uma função para replicar uma acção monádica e conjugar os valores.

replicarMonads 0 _ = []
replicarMonads n monad = do
        elemento <- monad
        resto <- replicarMonads (n-1) monad
        return (elemento:resto)

Portanto fazer replicarMonads 3 ['a', 'b', 'c', 'd'] irá produzir o mesmo resultado que a versão indicada no inicio por listas por compreensão.

Como replicarMonads é uma função uma pessoa pode brincar com ela, e basta apenas passar para esta função os tamanhos das strings a serem geradas. Isto também é facilmente conseguido com a popular função map (todas as linguagens modernas possuem uma versão desta função, acho que não preciso de explicar). Ou seja, se quizer-mos strings de tamanho 3 a 6 só basta fazer

map (\ n -> replicarMonads n ['a', 'b', 'c', 'd']) [3, 4, 5, 6]

O problema é que irá gerar uma lista de lista de strings, ou seja uma lista para cada n de tamanho. Como dissemos para ser de tamanho 3 a 6 irá ser uma lista com 4 elementos cada elemento uma lista de strings desse tamanho. Portanto é pegar na lista de listas e concatenar essas listas.

A função replicarMonads já existe e é a replicateM. E em relação ao map e à concatenação já existe uma função em Haskell que faz as duas coisas ao mesmo tempo, concatMap.

Espero que tenha dado para perceber. :(

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ainda bem que gostaram. Isso significa que tenho direito a uma bolacha?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Boas... solução em assembly (x86/NASM)  :cheesygrin:

section .data
fmt db "%s",10,0

section .bss
min resd 1
max resd 1
start resb 1
stop resb 1
buf resd 1
args resd 1

section .text

extern printf
extern malloc
extern free
extern atoi

global main
main:

pop edx
pop eax

dec eax
	jz @no_args

cmp eax, 4
	jne @no_args

pop eax
mov [args], eax

push DWORD [eax+4]
call atoi	
test eax, eax
	jz @no_args

mov [min], eax

mov eax, [args]
push DWORD [eax+8]
call atoi
test eax, eax
	jz @no_args

cmp eax, [min]
	jb @no_args

mov [max], eax

mov eax, [args]
mov ebx, [eax+12]
mov al, [ebx]
mov [start], al

mov eax, [args]
mov ebx, [eax+16]
mov al, [ebx]
cmp al, [start]
	jb @no_args

mov [stop], al

jmp @mem

@no_args:
jmp @exit

@mem:
mov eax, [max]
inc eax

push   eax
call malloc

test eax, eax
	jnz @got_buf

jmp @exit

@got_buf:

mov [buf], eax
xor ebx, ebx
mov dl, [start]
mov ecx, [min]

@fill_loop:
mov [eax+ebx], dl
inc ebx
cmp ecx, ebx
	jz @end_str

mov [eax+ebx], dl
inc ebx
cmp ecx, ebx
	jnz @fill_loop

@end_str:
mov BYTE [eax+ecx], 0

@main_loop:
push DWORD [buf]
push fmt
call printf

mov edx, DWORD [buf]
inc BYTE [edx]

mov al, [edx]
cmp al, [stop]
	jbe @main_loop

xor ebx, ebx

@inc_index:
mov al, [start]
mov [edx+ebx], al
inc ebx

@check_stop:
mov al, [edx+ebx]
cmp al, [stop]
	je @inc_index

test al, al
	jz @null_char

inc BYTE [edx+ebx]

jmp @main_loop

@null_char:
cmp ebx, [max]
	je @end_loop

mov al, [start]
mov [edx+ebx], al
mov BYTE [edx+ebx+1], 0

jmp @main_loop

@end_loop:
push DWORD [buf]
call free

@exit:
mov eax, 1
push 0
int 0x80

ret

intes  :thumbsup:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Boas...

Para assemblar e correr o código:

nasm -f elf file.asm -o file.o
gcc file.o -o file
./file 1 4 a d

Onde 1 seria o minimo do tamanho, 4 o maximo de tamanho, a o primeiro caracter e d o ultimo caracter.

Este funciona começando com uma string de tamanho min, gerando as várias combinações para esse tamanho, progredindo para uma string de tamanho superior, apenas deslocando o caracter nulo.

Intes  :eek:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Boas,... mais uma vez tava praki a coçar os tomates e a tirar macacos, decidi resolver este problema usando ruby. É uma boa forma de praticar esta linguagem na qual sou principiante.

class Char
def initialize(first, last)
	@arr = (first..last).to_a
	@index = 0
end
def succ
	@index += 1
	if @arr.length == @index
		@index = 0
		return nil
	end
	return 1
end
def to_s
	@arr[@index].to_s
end
end

class Word
def initialize(minimum, maximum, str, stp)
	@min = minimum
	@max = maximum
	@start = str
	@stop = stp
	@arr = [ ]

	@min.times do 
		@arr += [ Char.new(@start,@stop) ]
	end
end
def succ
	i = 0
	while i < @arr.length && !@arr[i].succ
		i += 1
	end
	if i == @arr.length
		if @arr.length < @max
			@arr += [ Char.new(@start,@stop) ]
		else
			return nil
		end
	end
	return 1
end
def to_s
	@arr.to_s
end
end

MINIMUM = 1
MAXIMUM = 5
START = "a"
STOP = "z"

w = Word.new( MINIMUM, MAXIMUM, START, STOP)

puts w.to_s

while w.succ
puts w.to_s
end

intes  :cheesygrin:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Alguém me mete isto em VB.NET?

É que eu não percebo um cu dessas linguagens maradas que meteram para ai.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Começa por tentar resolver o problema e depois expõe as tuas dúvidas sobre como o fazer...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Começa por tentar resolver o problema e depois expõe as tuas dúvidas sobre como o fazer...

Não percebi...

O problema é que eu não percebo nada dessas linguagens.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora