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

xoninas

[Ajuda]Gerar combinações de um código de 4 símbolos

12 mensagens neste tópico

Olá a todos,

vinha aqui pedir-vos ajuda para como obter todas as combinações possíveis de um "string" de um dado comprimento (Ex. n=20 símbolos) com um código de 4  símbolos distintos e possíveis em cada posição (tipo binário mas com 4).  Se eu for aumentando o comprimento do string em que ponto é que isto deixa de ser computável? No exemplo que eu dei penso que o numero de combinações possíveis será 4^20=1,09951E+12 

Expliquem como se eu fosse muito burro pois embora eu tenha formação em engenharia nada sei sobre programação.  :-[

Espero que não seja pedir demais...vamos ver como será a minha evolução em programação, quem sabe um dia trabalharei na empresa Google!  :P

Cheers!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ainda não percebi exactamente o que pretendes, mas vê estes tópicos:

http://www.portugal-a-programar.pt/index.php?showtopic=18355

http://www.portugal-a-programar.pt/index.php?showtopic=6933

Uma pesquisa por "combinações" ainda deve devolver mais alguns resultados.

Quanto a ser computável, deverá ser sempre, pode é não ser tratável.

Era mesmo isso (o tema do 1º tópico), obrigado! Vou ver com olhos de ver e tentar perceber.

P.S. eu tinha feito uma pesquisa mas não tinha acertado na mouche.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Basicamente o que pergunto é o mesmo do tópico:

http://www.portugal-a-programar.pt/index.php?showtopic=18355

o que quero tal como o autor do tópico mencionado é uma sequência (ou arranjo com repetição), ou seja calcular de quantas formas é possível colocar p elementos (tamanho do arranjo) de um conjunto com  n elementos em seqüência, podendo contar cada elemento mais de uma vez. A formula é:

nA'p=np

O tamanho é defenido e fixo tal como os elemento possiveís.

Isso não são combinações, pois a ordem é tida em conta, e porque podem haver elementos repetido. Isso são arranjos com repetição.

para n letras diferentes (por exemplo, A,B, e C), e sequências de m elementos:

--------------------------------------------------------------------------------

seq=[A,B,C]

para i de 0 a n^m-1

  k=i

  para j de 0 a m-1

    res[ i][j]=seq[k mod n]

    k=k div n

--------------------------------------------------------------------------------

Para as contas baterem certo, é necessário que os elementos de seq sejam indexados da posição 0 à posição n-1.

Rui Carlos, penso que percebeste no outro tópico o que era pedido. Eu é que não percebo o que escreveste!!! Como disse não percebo nada de programação, o que é "res", "mod", etc...

Agradecido pelo feedback,

Cheers!

P.S. vou investigar a USACO  :ipool:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

mod é uma operação matemática (divisão inteira).

res é o resultado, ou seja, a sequência de strings com as combinações.

res[m][n] é a letra de índice n da combinação m. Isto é, se o resultados fossem as strings

aa

ab

ba

bb

res[2][0] seria a primeira letra da terceira string. Ou seja, 'b'.

Basicamente usei a notação de array do C e linguagens similares.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Para calcular basta:

NChars (exemplo: 3 (a,b,c))

CmptCadeia (exemplo: 4 (abca))

E fazes: NChars^CmptCadeia

E porquê?

EXEMPLO

Elementos Possíveis: a,b,c

Comprimento Cadeia: 4

Quantas letras podes colocar na primeira posição da palavra?

- N Elementos Possíveis.

Na segunda posição, quantas letras podes pôr para combinar por exemplo com a letra 'a'?

- Continua a ser N Elementos Possíveis (neste caso, 3)

Na segunda posição, quantas letras podes pôr para combinar por exemplo com a letra 'b'?

- Continua a ser N Elementos Possíveis (neste caso, 3)

Ou seja já tens 3 do 'a', 3 do 'b' e depois ainda vais ter mais 3 do 'c'.

Na terceira posição, quantas letras podes pôr para combinar com as letras da posição 1 e 2 'aa'?

- Continua a ser N Elementos Possíveis (neste caso, 3)

E por aí fora.

Ou seja, vais ter de multiplicar o número de elementos possíveis por si Comprimento da Cadeia vezes. Ou seja (para o exemplo em cima):

3 elementos  *  3 elementos  *  3 elementos  *  3 elementos

Primeira Letra  Segunda Letra    Terceira Letra    Quarta Letra

Simplificando: elevas o número de elementos possíveis ao comprimento da cadeia.

P.S.: Não abri os links que deixaram nas replies.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pois, só que isso só te dá o número de permutações, e não as permutações propriamente ditas...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
NChars (exemplo: 3 (a,b,c))

CmptCadeia (exemplo: 4 (abca))

E fazes: NChars^CmptCadeia

sim essa é a forma de calcular o nº dos arranjo que eu quero mas eu quero mesmo é obter a lista.

seq=[A,B,C]

para i de 0 a n^m-1

  k=i

  para j de 0 a m-1

    res[ i][j]=seq[k mod n]

    k=k div n

vou tentar dissecar isto para ver se percebo...

seq=[A,B,C]

para i de 0 a n^m-1

seq=[A,B,C] é que se chama de array deste casos dos elementos A,B,C.

i de 0 a n^m-1 sendo i todas as permutações possiveis indexadas de 0 a n^m-1

  k=i

  para j de 0 a m-1

k=i será o que se chama de "alias" permitindo usar os mesmos campos em diferentes partes da equação em baixo??...

j de 0 a m-1 será a indexação de todas as posições da "string" igualmente a começar de 0 (que representa a 1ª posição).

res[ i][j]=seq[k mod n]

    k=k div n

Aqui é que me perco todo!!!

res[ i][j]=seq[k mod n] conforme a tua explicação "res" significa resultado e [ i]  é qual a string gerada e [j] a letra da posição dessa mesma string. Não percebo é porque res[ i][j] é igual a seq[k mod n].

Seq[k mod n] é um array de todas da divisão de todas string obtidas pelo numero de elementos???

k=k div n  então é que não atinjo mesmo??? k será igual há sua própria divisão por o numero de elementos???

Eu sei que deve ser muito básico mas eu não consigo atingir quer a lógica do algoritmo ou a própria sintaxe do código. Estou a por o carro à frente dos burros pois falta-me conhecimentos de base, mas por favor tenham paciência comigo.

Já tive a ver aquilo do USACO mas isso é muito andamento para mim, vou começar com algum tutorial do mais básico que há.

Já agora eu descobri outra solução na net para o mesmo problema:

To do this, assign each of your r objects to a digit, including zero, in a base-n number. Then generate all of the numbers from 0 to n^r -1. Inside this loop, convert the index in your outer loop to base n, mapping each digit to your object as you generate it, something like this:

Input n (n > 1 and you want to check that your value of n won't overflow your machine. For n = 1, you will want to do something special and output a string of r copies of your one element, once you get a value of r.)

Allocate n elements in character array "object ()" with each element of object() corresponding to one of the n objects in your set. (It is assumed that the base index is zero and goes up to n-1)

Initialize array object ()

Input r, checking for validity. (Note: because repetition is allowed, nothing in this problem requires that r ≤ n, but you will want to do something special for r = 0 and you want to check that n^r is not too big for your machine to handle.)

Allocate r elements in character array "perm ()" to hold the character string of the permutation while is being generated.

For permno from 0 to n^r - 1, do:

{

permcur := permno; permcur is a temporary copy of the number to be converted to base n and will change as the conversion progresses.

For digitplace from 0 to r-1, do:

Note: This converts the number from the least significant bit (digitplace = 0) to the most significant place.

{

IntegerDivide (permcur, n, permcur, digit) ; Routine IntegerDivide (dividend, divisor, quotient, remainder) performs an integer divide and returns the integer quotient and remainder in the latter two arguments.

perm (digitplace) := object (digit);

}

By the time this loop drops out the bottom, permcur should be zero.

Print perm;

Note: If the array perm is printed from left to right, the least significant digit will be on the left. This can be changed if necessary by decrementing the loop index digitplace to go from r-1 to 0 so that the most significant digit would be in place 0.

}

End of algorithm.

Cheers!  :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Deixo aqui uma implementação em C do algoritmo, para ver se deixa de haver problemas com a notação:

#include <stdio.h>
#include <math.h>

int main()
{
  char seq[]="01";
  int n=2, m=3;

  char res[8][4];

  int i, j, k;

  for(i=0; i<=pow(n, m)-1; i++)
  {
    k=i;
    for(j=0; j<=m-1; j++)
    {
      res[i][j]=seq[k%n];
      k=k/n;
    }
  }

  for(i=0; i<pow(n,m); i++)
  {
    res[i][m]=0;
    puts(res[i]);
  }

  return 0;
}

O que interessa aqui é o primeiro ciclo for e o seu conteúdo.

Isso vai gerar algo do género

000

100

010

110

001

101

011

111

Repara na forma como os valores variam nas várias colunas.

Na primeira os números repetem-se 1 (2^0) vez.

Na segunda repetem-se em blocos de 2 (2^1).

Na terceira repetem-se em blocos de 4 (2^2) vezes.

Com o resto da divisão inteira consegues fazer com que o valores vão alternando (k mod n ou k%n).

A dividir o valor de i sucessivamente por n (k=i, k=k div n ou k=i, k=k/n)*, consegues controlar o número de vezes que se repete o mesmo número, pois quando fazes a divisão inteira de valores por um número p, os resultados repetem-se em grupos de dimensão p.

Por exemplo, para p=2:

0/2=0

1/2=0

2/2=1

3/2=1

4/2=2

Bem, isto é um bocado complicado de explicar assim pela net, mas pronto :\

* Onde está k=k div n podia estar k=i div n^j, e talvez desta última forma seja mais fácil perceber.

EDIT: se não me engano, cada posição da matriz resultado vai ter o valor (linha/n^coluna)%n.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Peço desculpa... Não li bem o post... Li a parte do computável... :|

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