[Dúvida] limitar combinações

[alves077 0]

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 5 de Março de 2013 por alves077

[HappyHippyHippo 1178]

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 0]

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 1178]

que resultados deveriam ser apresentados para este conjunto ?

{1, 2, 3}

[alves077 0]

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 1178]

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

[alves077 0]

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 1178]

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 0]

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 6 de Março de 2013 por alves077

[HappyHippyHippo 1178]

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 0]

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 1178]

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 96]

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 0]

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 96]

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 0]

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