Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

alves077

[Dúvida] limitar combinações

Mensagens Recomendadas

alves077

Boa noite,

Tenho um array onde faço todas as combinações entre os números do array, mas quero limitar as combinações excluindo algumas que são desnecessárias. A ideia como faço é:

void in_comb(int contador)
{

int k;
if(n<n_maximo)
{
	for(k=;k<5;k++)
	{
		total[n]=comb[i];

		in_comb(n+1);
	}
}

}

Dando esta função todas as combinações de um determinado alfabeto que tenho o array comb, a minha questão é que por exemplo tenho combinações que queria excluir e não estou a conseguir, como por exemplo tendo o array = [1,2,3,4], não necessito da combinação 1111, Melhor queria fazer as combinações de um determinado número fixo de elementos em que se esses mesmos elementos forem todos 1 fossem fossem descartados , não sei se me fiz entender, alguém consegue dar uma ideia como posso fazer o pretendido?

Obrigado pela atenção,

alves077

Editado por alves077

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

não sei se me fiz entender

não

se só tens os elementos {1, 2, 3, 4}, nunca terás a combinação {1, 1, 1, 1}, istpo porque só tens um "1" e não apresentas os restantes valores a serem combinados {2, 3, 4}


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
alves077

Ok, tendo um alfabeto de 1,2 queria fazer as combinações fixas de 5 elementos, basicamente num array de 5 elementos por exemplo

[1,2,2,2,2]

[1,1,2,2,2]

[1,1,1,2,2]

[1,1,1,1,2]

Mas por exemplo dispensava a combina com todo 2's, se me fiz entender. Não e bem uma combinação porque estou aqui a repetir valores, queria basicamente fazer todos os casos possíveis de preenchimento num array de tamanho fixo com um determinado alfabeto no caso {1,2}.

O código que fiz faz todas os preenchimentos possíveis, de diferentes, não e bem o que pretendo, estou de volta mas não estou a conseguir chegar a solução credível..

Obrigado pela atenção,

alves077

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
alves077

num array de 5 elementos, por exemplo:

[1,1,3]

[1,1,2]

[1,2,3]

[2,2,3]

Todo o preenchimento possivel em 3 lugares com o alfabeto 1,2,3.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
alves077

A logica era descartar o caso base [1,1,1], só este, isto é, o primeiro elemento do alfabeto preenchido totalmente o array é descartada essa possibilidade. [2,2,2] já era aceito como o 3 tbm, só o caso 1 1 1 é que e descartável.

Obrigado pela atenção,

alves077

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

antes de pensares em descartar, não achas que seria melhor teres o código a correr para apresentar todos os casos possíveis ?


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
alves077

Sim e verdade, mas até ai estou com problemas, consegui gerar todas os preenchimentos com o código que apresentei, mas não consegui por em um array fixo os, e faz pela ordem que pretendo isto é começar pondo um 2 no array -> [2,1,1] e andar ocm o dois [1,2,1] depois [1,1,2]. Mas o que consegui fazer apresenta por exemplo os primeiros output

1

11

111

1111

11111

11112

11113

1112

11121

11122

11123

Este é o resultado esperado segundo o código que tenho, só que como vejo os preenchimentos não estou a conseguir como quero. queria antes algo como por exemplo:

11111

21111

12111

11211

por ai a diante, mesmo que não consiga por esta ordem ao menos com tamanho fixo já era qualquer coisa, mas mesmo ai estou com problemas para conseguir.

Obrigado pela atenção,

alves077

Editado por alves077

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

faz assim :

se tens os elementos {1, 2, 3 ... N} a serem distribuídos por X posições (da maneira como dizes)

cria um array com os seguintes elementos : {1a, 1b ... 1x, 2a, 2b ... 2x ... Na, Nb ... Nx} e fazes as combinações possíveis desses elementos pelas X posições:

exemplo :

domínio {1, 2, 3, 4} para 3 posições:

array de valores = {1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4}

agora cria as combinações destes elementos

agora, criar estes arrays é trivial porque o número de elementos é facilmente calculado


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
alves077

Não percebi o array que construís-te

array de valores = {1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4}

Se são 3 posições não deveria ser:

array de valores = {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4} ?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

Não percebi o array que construís-te

array de valores = {1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4}

Se são 3 posições não deveria ser:

array de valores = {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4} ?

certo ... é o que dá responder depois da meia noite ...


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pmg

O que tu queres são "multisets".

Podes contrui-los facilmente com uma função recursiva.

Repara:

caso base: Os multisets de 1 elemento pertecente a um determinado conjunto são os conjuntos com cada um dos elementos.

caso recursivo: Os multisets de N elementos pertencentes a um determinado conjunto são os conjuntos que têm cada um dos elementos junto com os multisets de N-1 elementos.


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
alves077

Sim @pmg é basicamente multisets que quero implementar, mas está difícil..

Pela lógica que percebi caso base por exemplo num array de 3 posições [1,2,3] são os conjuntos com cada um dos elementos isto é , {1} {2} {3}

o caso recursivo não estou a conseguir lá chegar, é começando no caso base ir combinando até chegar ao limite?

void in_comb(int contador)
{

   int k;
   if(n<n_maximo)
   {
       for(k=0;k<5;k++)
       {
           total[n]=comb[i];

           in_comb(n+1);
       }
   }
}

Não consigo definir bem os casos da recursividade, para construir bem os "sets", o que faço e todas as combinações possíveis dados os elementos, isto é, começo com um determinado número e faço todas as combinações começando com esse número, e por ai adiante, mas não consigo construir os set's que preciso..

Já tentei emendar com os casos base e recursivo que puseste, mas acho q não estou bem a perceber o conceito..

Obrigado pela atenção,

alves077

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pmg

Ao fazer a minha primeira versao dos multisets recursivos reparei num erro.

Por exemplo, para multisets de 5 elementos baseados no conjunto {1, 2, 3}, essa versao gerava {1, 1, 1, 1, 1}; {1, 1, 1, 1, 2}; {1, 1, 1, 1, 3}; {1, 1, 1, 2, 1} ...

Mas se reparares este ultimo multiset é o mesmo do segundo.

Para solucionar o problema bastou-me limitar os novos elementos a serem superiores ou iguais ao mais recente.

Mas faz a tua versao recursiva! A recursividade é simples :)


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
alves077

Obrigado pela apoio @pmg, acho que já consegui resolver o meu problema, já consegui criar multiset não utilizando uma forma muito recursiva, mas está a bater certo. Não estou muito habituado a usar algoritmos recursivos, mas com treino isto vai lá :)

Obrigado pela atenção,

alves077

Partilhar esta mensagem


Ligação 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

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.