Ir para o conteúdo
pessantiago

combinações possiveis

Mensagens Recomendadas

pessantiago

boas pessoal

tenho uma lista N conjunto de valores, e um unico valor M

N= 1,2,3,4,

M= 5

quero obter todas as combinações possíveis

	public static void main(String[] args) {
   int [] vals ={1,2,3,4} ;
   int sum = 5;

   System.out.println(combinacoes(vals, sum));  
}
  public static int combinacoes( int [] vals,int sum) {
	if (sum < 0) {
		return 0;
	}
	if (vals == null || vals.length == 0) {
		return 0;
	}
  int possiveis[] = new int[sum + 1];
	possiveis[0] = 1;
	for (int i = 0; i < vals.length; ++i) {
		for (int j = vals[i]; j <= sum; ++j) {

			possiveis[j] += possiveis[j - vals[i]];

		}
	}
	return possiveis[sum];

}

queria era retornar

1+4

4+1

2+3

3+2

etc

Editado por Rui Carlos
GeSHi

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

tens de verificar as seguintes combinações:

X1/X2

X1/X3

...

X1/Xn

X2/X3

X2/X4

...

X2/Xn

X3/X4

X3/X5

...

X3/Xn

...

Xn-1/Xn

e para isso, o teu ciclo interno não faz sentido


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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pessantiago

como assim?

é que nao entendo

quero obter dado um conjuntos de valores N e um numero M inteiro positivo , retornar todas condições possiveis que dêm a suma de 5.

ja andei a procurar no google mas nao chego lá

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

como assim?

é que nao entendo

explicar mais seria resolver o problema ... olha bem para as combinações que escrevi e pensa em como poderás obter esse "efeito"


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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

responde a estas simples questões :

- de onde apareceu o código que apresentaste ?

- o que está a fazer ?

- porque está a fazer o que está a fazer ?


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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

http://stackoverflow.com/questions/4243831/how-to-count-possible-combination-for-coin-problem

título do tópico

How to count possible combination for coin problem

isso é para contar o número de combinações e não para saber quais as combinações !!!

dizer que o resultado do Porto/Zenit ficou no total de 2, não sabes se o Porto marcou 2 e o Zenit nenhum, ou o Zenit marcou dois e o Porto nenhum ou marcaram os dois 1 golo !!!

Apaga esse código e pensa no que escrevi na primeira resposta


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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

conjunto : {X1, X2, X3, ... , XN}

combinações :

X1/X2, X1/X3, X1/X4, ..., X1/Xn-1,   X1/Xn
      X2/X3, X2/x4, ..., X2/Xn-1,   X2/Xn
             X3/X4, ..., X2/Xn-1,   X2/Xn
...
                         Xn-2/Xn-1, Xn-2/Xn
                                    Xn-1/Xn

como disse, mais do que isto é fazer o exercício ...

  • Voto 1

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pessantiago

entao espera vou ter que ter dois ciclos for né

do tipo

for( int i = 0; i<tamanho.do.array;i++){
  for(int j=i; j<tamanhodoarray; j++)
  }
}

Editado por Rui Carlos
GeSHi

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Rui Carlos

Sim, é mais ou menos isso.

Uma sugestão: começa por colocar dentro desse ciclo um System.out.println("" + vals + "/" + vals[j]);, e faz as correcções necessárias ao código, até que mostre os pares que o HappyHippyHippo indicou.

Depois de teres todos os pares, só precisarás de um if para seleccionar os pares que cumprem os requisitos.

O passo final será guardar os valores num array (em vez de os imprimir).

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pessantiago

ja tenho o seguinte codigo

   /**
    * @param args the command line arguments
    */
   public static void main(String[] args) {
      int M = 4;
      int [] array ={1,2,3,4} ;


        System.out.println(findCombinationsCount (M, array));  
   }
  public static int findCombinationsCount(int M, int vals[]) {
       if (M < 0) {
           return 0;
       }
       if (vals == null || vals.length == 0) {
           return 0;
       }

       for (int i = 0; i < vals.length; ++i) {
          for(int j=i+1;j<vals.length;j++)


              System.out.println("" + vals[i] + "/" + vals[j]);

           }

       return 0;

       }

   }


Editado por Rui Carlos
GeSHi

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pessantiago

a minha duvida agora é isto esta feito de forma exaustiva? testando todas as hipoteses

public class TP8 {
   /**
    * @param args the command line arguments
    */
   public static void main(String[] args) {
       int M = 5;
       int[] array = {1, 2, 3, 4};

       System.out.println(findCombinationsCount(M, array));
   }
   public static int findCombinationsCount(int M, int vals[]) {
       if (M < 0) {
           return 0;
       }
       if (vals == null || vals.length == 0) {
           return 0;
       }
              for (int i = 0; i < vals.length; ++i) {

                   for (int j = i + 1; j < vals.length; j++) {
                       if (M == vals[i] + vals[j]) {
                           System.out.println("" + vals[i] + "/" + vals[j]);
                       }
                   }
               }
     return 0;

   }
}

ajuda me so a retorna o array , é que nao estou a ver como se faz

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Rui Carlos

Devolver um array não é propriamente óbvio... Precisas mesmo disso, ou o objectivo do exercício é apenas imprimir os valores?

Se for necessário, podes começar por declarar um array para colocares os valores. Tendo em conta que queres devolver pares, penso que será boa ideia um array de bidimensional de tamanho [N*N/2][2], onde N é o tamanho do array de input (N*N/2 é superior ao número de pares que podes encontrar).

Depois, de cada vez que encontrares um elemento, adicionas ao array.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pessantiago

o problema é que posso ter N elementos no conjunto por exemplo 1,2,3,4,5,6 dou um inteiro 6 por exemplo,tenho de achar todas os subconjuntos possiveis

1+2+3 =6

1+5 =6

2+4 =6

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Rui Carlos

Pensei que as combinações tivessem de ser de dois elementos...

Isso já pede um algoritmo recursivo, e não me parece que vá ser muito simples.

A primeira coisa que me vem à cabeça, para gerar todas as combinações, seria algo do género:

função comb(array1, array2)
 se array2 for vazio
   imprime array1
 senão
   comb(adiciona(array2[0], array1), remove(array2[0], array2))
   comb(array1, remove(array2[0], array2))

Penso que isto devia funcionar. A ideia seria fazer:

comb([], [1, 2, 3])
 comb([1], [2, 3])
   comb([1, 2], [3])
     comb([1, 2, 3], [])
       imprime([1, 2, 3])
     comb([1, 2], [])
       imprime([1, 2])
   comb([1], [3])
     comb([1, 3], [])
       imprime([1, 3])
     comb([1], [])
       imprime([1])
 comb([], [2, 3])
   comb([2], [3])
     comb([2, 3], [])
       imprime([2, 3])
     comb([2], [])
       imprime([2])
   comb([], [3])
     comb([3], [])
       imprime([3])
     comb([], [])
       imprime([])

Isto já não propriamente simples de implementar, e provavelmente convinha já usares objectos e arrays mais dinâmicos.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Rui Carlos

Percebeste o algoritmo que te indiquei para gerar todas as combinações?

Pelo menos para acumular as combinações que dão a soma pretendida, penso que o ArrayList é útil. Para a movimentação de elementos de um conjunto para o outro na chamada a funções, podes usar um array com uma variável N a dizer-te que só deves considerar os primeiros N valores do array, por exemplo.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

mais uma referência (claro que não é em Java porque isso é trabalho teu) :

#include <stdio.h>
#include <string.h>

void solve_print(int NSolves, size_t N, int Solves[][N]) {
   for (int i = 0; i < NSolves; i++) {
       printf("%d >> Solve : ", i);
       for (int j = 0; j < N && Solves[i][j] != 0; j++) {
           printf("%d ", Solves[i][j]);
       }
       printf("\n");
   }
}

int solve_sum(size_t N, int Solve[N]) {
   int sum = 0;
   for (int i = 0; i < N; i++) {
       sum += Solve[i];
   }
   return sum;
}

void solve_push(size_t N, int Solve[N], int value) {
   for (int i = 0; i < N; i++) {
       if (Solve[i] == 0) {
           Solve[i] = value;
           return;
       }
   }
}

int comb(int NSolves, size_t N, int Solves[][N], int X[N], size_t left, int M) {
   int Solve[N];

   memcpy(Solve, Solves[NSolves], sizeof(int) * N);
   int sum = solve_sum(N, Solve);

   for (int j = left; j < N; j++) {
       if (sum + X[j] == M) {
           solve_push(N, Solves[NSolves++], X[j]);
           memcpy(Solves[NSolves], Solve, sizeof(int) * N);
       } else {
           solve_push(N, Solves[NSolves], X[j]);
           NSolves = comb(NSolves, N, Solves, X, j + 1, M);
           memcpy(Solves[NSolves], Solve, sizeof(int) * N);
       }
   }

   return NSolves;
}

int main() {
   int X[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
   int N = sizeof(X) / sizeof(int);
   int Solves[N*N/2][N];
   int M = 12;

   memset(Solves, 0, sizeof(Solves));
   int NSolves = comb(0, N, Solves, X, 0, M);

   solve_print(NSolves, N, Solves);

   return 0;
}

Editado por HappyHippyHippo

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

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.