[Dúvida] limitar combinações

[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

Edited March 5, 2013 at 10:33 PM by alves077

[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}

[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

[HappyHippyHippo]

que resultados deveriam ser apresentados para este conjunto ?

{1, 2, 3}

[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.

[HappyHippyHippo]

é para descartar também os [1,2,2], [1,3,3] e [2,3,3] ?

[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

[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 ?

[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

Edited March 6, 2013 at 12:37 AM by alves077

[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

[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} ?

[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 ...

[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.

[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

[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 🙂

[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