Erro na sequencia

Olá, :slight_smile:

Criei um programa que lê uma matriz quadrada e com a ordem dessa matriz determina todas as sequencias possiveis. Por exemplo, se a ordem da matriz for 4 determina todas combinaçoes com os numeros 0, 1, 2, 3.
Sendo que os numeros das combinações correspondem a posiçoes na matriz inserida. Para cada combinação o programa faz a soma maxima dos elementos da matriz.

O programa já cria todas as sequencias e descobre a soma maxima. Mas nao guarda a sequencia correspondente à soma maxima.

O codigo é o seguinte:

package mdisc;

import java.io.PrintStream;
import java.math.BigInteger;
import java.util.Random;
import java.util.Scanner;

/**
 *
 * @author 
 */
public class MDISC {
    
    public static void main(String[] args) {
        MDISC programa = new MDISC();
        programa.menu();
                
    }

    private final Scanner entrada = new Scanner(System.in);
    private final PrintStream saida = System.out; 
    private static int[][] matriz;  
    private static int[] p; 
    private static int somaMax; 
    private static int[] seq;


    /**
     * Executa este programa
     */
    
    
    public void executarMatrizInserida(){
        
        // Introdução dos valores da matriz no formato x,y,z,...
        saida.println("Introduza os valores no formato A,B,C,D: ");
        saida.println(" A  B ");
        saida.println(" C  D ");
        saida.println("Valores: ");
        String stringDeNumeros = entrada.nextLine();
        // converte a string para um vetor de strings
        String[] vetorString = stringDeNumeros.split(",");
        int[] vetorInt = stringsParaInts(vetorString);
        saida.println("Matriz introduzida: ");
        // converte o vetor para uma matriz
        matriz = converteVetorEmMatriz(vetorInt);
        int ordem = matriz.length;
        int v[] = new int[ordem];
        for (int y=0; y<ordem; y++){
            v[y]=y;
        }
        // imprime a matriz
        imprimirMatriz(matriz);
        permuta1(v);
        
        // sequencia
        System.out.println("Valor máximo: " + somaMax);
        System.out.println("Sequencia com soma máxima: " );
        for (int y=0; y<seq.length;y++) System.out.print(seq[y] + " ");
        menu();
            
    }
    
    private void permuta(int []vet, int n) {
         
        if (n==vet.length) {
            sequencias();
                             
        } else {
                     
            for (int i=0; i < vet.length; i++) {
             
                boolean enc = false;
             
                for (int j = 0; j < n; j++) {
                 
                    if (p[j]==vet[i]) enc = true;
                }
             
                if (!enc) {
                     
                    p[n] = vet[i];
                    permuta(vet,n+1);
                }
                 
            } //--for
             
        } //--if/else
         
    }
    public void permuta1(int [] vet) {
         
        p = new int[vet.length];
        permuta(vet,0);
        
    }
    
    public void sequencias(){
        
        int soma=0;
        for (int i=0; i < p.length; i++) {           
            
            
            if ( i+1==p.length){
                
                soma=soma+matriz[p[0]][p[p.length-1]];   
            }
            else {
                
                soma=soma+matriz[p[i]][p[i+1]];
            }  
        somaMaximaSeq(soma);    
        }
        
        
        
    }
    
    public void somaMaximaSeq(int soma){
        
        seq = new int[p.length];
                
        if (soma<somaMax){
            somaMax=soma;
            for (int i=0; i < p.length; i++) {
                seq[i]=p[i];
            }
         }
    }       
    
    public void executarMatrizAleatoria(){
        
        saida.println(" ");
        saida.println("Insira a ordem da matriz a gerar: ");
        int ordem = Integer.parseInt(entrada.nextLine());
        // gerar matrizes aleatoriamente com valores entre [0,100] com as diagonais em zero.
        int[][] matrizAleatoria = gerarMatriz(ordem, 100);
        saida.println(" ");

        // Imprimir matriz gerada aleatoriamente
        saida.println("Matriz gerada aleatoriamente de ordem " + ordem + ":");
        saida.println(" ");
        imprimirMatriz(matrizAleatoria);
        int v[] = new int[ordem];
        for (int y=0; y<ordem; y++){
            v[y]=y;
        }
        permuta1(v);
        // Sequencia da matriz
        //int [] seq = sequencia(ordem, 2);
        System.out.println(" ");
        System.out.println("Soma máxima: " + somaMax);
        System.out.println(" ");
        System.out.println("Sequencia com soma máxima: " );
        for (int y=0; y<seq.length;y++) System.out.print(seq[y] + " ");
        
        menu();
        
        
    }
    
    
    public void menu(){
        
        Scanner ler2 = new Scanner(System.in);
        System.out.println("   ");
        System.out.println("Insira a operação que deseja efetuar:");
        System.out.println("   ");
        System.out.println("1 - Matriz inserida e sequencia e soma máxima ");
        System.out.println("2 - Matriz aleatoria e sequencia e soma máxima ");
        System.out.println("3 - Fatorial");
        System.out.println("4 - Sair");        
        System.out.println("   ");
        System.out.print("Insira a opção: ");
        int opcao = ler2.nextInt();
        System.out.println("   ");
        switch(opcao){
            case (1):
                executarMatrizInserida();
                break;
            case (2):
                executarMatrizAleatoria();
                break;
            case (3):
                executarFatorial();
                break;
            case (4):
                System.exit(0);
                break;
              
        }        
    }
    
    /*
    * Converte o vetor anteriormente convertido em int para uma matriz quadrada
    */
    
    private int[][] converteVetorEmMatriz(int[] vetor) {
        
        int ordem = (int) Math.sqrt(vetor.length);
        matriz = new int[ordem][ordem];
        try {
            int posicao = 0;
            for (int linha = 0; linha < ordem; linha++) {
                for (int coluna = 0; coluna < ordem; coluna++) {
                    matriz[linha][coluna] = vetor[posicao++];
                }
            }
        } catch (ArrayIndexOutOfBoundsException e) {
            saida.println("Erro: Não introduziu valores correspondentes a uma matriz quadrada! " + e);
        }
        return matriz;
    
    }
    
    public void executarFatorial(){
        
        System.out.println("Insira um valor: ");
        int valor = entrada.nextInt();
        try {            
            System.out.println(fatorial(valor));
        } catch (ArrayIndexOutOfBoundsException e) {
            saida.println("Erro: Não introduziu valores correspondentes a uma matriz quadrada! " + e);
        }
        menu();
    }
    
    /*
    * Calcula o fatorial de um valor. Utilizamos o bigInteger para permitir calcular valores elevados
    */
    
    private BigInteger fatorial(int valor) {
        
        BigInteger factorial = new BigInteger("1");
        for (int i = 1; i <= valor; i++) {
            factorial = factorial.multiply(new BigInteger(i + ""));
        }
        return factorial;
    }

    /**
     * Gerar matrizes de ordem informada aleatoriamente com valores entre 0 e o 100, com as diagonais em zero.
     */
    
    private int[][] gerarMatriz(int ordem, int limite) {
        
        Random gerador = new Random();
        matriz = new int[ordem][ordem];
        for (int linha = 0; linha < ordem; linha++) {
            for (int coluna = 0; coluna < ordem; coluna++) {
                if (linha == coluna){
                    matriz[linha][coluna] = 0;
                }
                else {
                    int ger = gerador.nextInt(limite);
                    matriz[linha][coluna]=ger;
                    matriz[coluna][linha]=ger;
                }
            }
        }
        return matriz;
    }

    /**
     * Imprime a matriz passada pelo parametro
     */
    private void imprimirMatriz(int[][] matriz) {
        
        for (int linha = 0; linha < matriz.length; linha++) {
            for (int coluna = 0; coluna < matriz[linha].length; coluna++) {
                String espaco = matriz[linha][coluna] < 10 ? "  " : " ";
                saida.print(espaco + matriz[linha][coluna] + espaco);
            }
            saida.println(" ");
        }
    }

    /**
     * Converte um array de String para um array de inteiros
     */
    private int[] stringsParaInts(String[] strings) {
        
        int ints[] = new int[strings.length];
        try {
            for (int i = 0; i < strings.length; ++i) {
                ints[i] = Integer.parseInt(strings[i].trim());
            }
        } catch (NumberFormatException e) {
            saida.println("Erro: Não introduziu apenas numeros! " + e);
        }
        return ints;
    }
}

O codigo correspondente a fazer a soma maxima é o seguinte:

public void sequencias(){
        
        int soma=0;
        for (int i=0; i < p.length; i++) {           
            
            
            if ( i+1==p.length){
                
                soma=soma+matriz[p[0]][p[p.length-1]];   
            }
            else {
                
                soma=soma+matriz[p[i]][p[i+1]];
            }  
        somaMaximaSeq(soma);    
        }
        
        
        
    }
    
    public void somaMaximaSeq(int soma){
        
        seq = new int[p.length];
                
        if (soma<somaMax){
            somaMax=soma;
            for (int i=0; i < p.length; i++) {
                seq[i]=p[i];
            }
        }
    }

Alguem me consegue ajudar a guardar na seq a seuqencia com a primeira maior soma? Obrigado :slight_smile:

Tecnicamente…
Se uma matriz de ordem 2x2 possui os valores 1, 2, 3, 4, respectivamente, nas posições (0,0), (0,1), (1,0) e (1,1), não importa qual seja a sequência que eu faça a soma, o resultado será sempre o mesmo (10, no caso), não? Princípio básico da soma: a ordem dos fatores não altera o resultado.
Ou seja, se você vai fazer esse processamento todo, deverá sempre ter o retorno igual ao primeiro ou último que validou.

Olá!, eu nao somo o 1+2+3+4. Estes numeros vao corresponder a uma linha e coluna da matriz inserida que vai somar com os adiante!

Que?
Posta a fórmula que você está usando para isso, pois, até o momento, não parece fazer sentido para mim.

Eu tenho uma matriz de ordem 4 por exemplo:

0   12  71  70
12   0  95  34
71  95  0   3 
70  34  3   0

O programa vai gerar todas as sequencias com os valores 0, 1, 2, 3 que sao as posições na matriz.

Ele vai gerar por exemplo, a sequencia 1 , 0, 3, 2
Assim, o programa vai à linha 0 e coluna 1 e soma com a linha 1 e coluna 2 e soma com a linha 2 e a coluna 3 e por fim soma com a linha 3 e a coluna 0 que daria 12 + 95 + 3 + 70 = 180

E faria isso com todas as 16 sequencias possiveis com o 0,1,2,3.
O problema é que ele nao guarda a sequencia com a soma maior

Uma matriz de ordem 4 não tem só as posições 0, 1, 2 e 3. Ele possui as posições 00, 01, 02, 03, 10, 11, 12, 13, 20, 21, 22, 23, 30, 31, 32 e 33,
Essa definição de 4 posições é tua e era isso que não estava claro.

Tem certeza que, num universo de 16 posições, só existem 16 combinações possíveis?

Não guarda = não possui nenhuma informação ou = pega a última processada?

Nao, em 4 valores existem 24 combinaçoes possiveis. Na sequencia guarda sempre 0 0 0 0.
A minha duvida é mesmo como guardar a sequencia com soma maior pq o resto esta a funciar direitinho

No meu entendimento, o método sequencias deveria pegar uma sequência (0, 1, 2, 3 ou 10, 11, 12, 13 por exemplo) e verificar qual o valor da soma desta. Se fosse maior que o valor contido na variável maiorSoma, então, substituiria o vetor de 4 posições definido para armazenar a tal sequência (ai cabe a ti decidir se armazena as posições ou se armazena os valores ou ambos).

Queria que armazenasse as posições. Como posso fazer isso?

Usa um vetor de 4 posições. Cada posição do vetor será responsável por armazenar uma posição referente a sequência onde existe a maior soma.

Foi o que eu fiz! Mas nao esta a guardar! Nao sei o que fiz errado

Repito: a lógica nos métodos sequencias e somaMaximaSeq precisam ser revistas.
Ambos estão confusos e eu nem arrisco mexer, pois não sei qual lógica você empregou para fazê-los.
Veja, não existe elo entre o trecho a ser processado e as posições a serem armazenadas.
Aliás, estamos falando de uma matriz, logo, você não pode, simplesmente, armazenar apenas uma posição. Como você tem matrizes de duas dimensões (linha e coluna), precisa ter o cuidado de armazenar as posições referentes a linha e as colunas da sequência.