ordenar una matriz segun la suma de las filas y las columnas

[jose_d]

Hola como estan
espero me puedan ayudar con este algoritmo ya que llevo varios meses dandole y nada, cual es la idea tengo una matriz esta la tengo que ordenar de tal manera que las filas me sumen lo mismo o trate de ser lo mas equitativo posible ,moviendo lo que tengo en las columnas.

la idea que tuve fue tener una matriz imagen la cual lleno columna por columna teniendo en cuenta la sumatoria esto lo logro lo malo es que me carga el comienzo de cada fila.

ej

Código:

	  1  2  3  4  5  6  7  8  9  10  11  12  13  14
g1   x  x  x  x  x  x   x  x   d  d   d	 d   d   d
g2   d  d  d  d  d  d  d  d   x  x	x	 x	x	x

supongamos que la cantidad de X que debe tener la primera fila es 8 el algoritmo lo hace y queda de esa manera lo cual no me sirve por que sobrecargo una fila al comienzo deberia de quedar asi.

Código:

	  1  2  3  4  5  6  7  8  9  10  11  12  13  14
g1   x  x  d  d  x  x   d  d   x   x   d	 d   x   x
g2   d  d  x  x  d  d  x  x   d  d	x	 x	d   d

espero me entiendan y me puedan ayudar

muchas gracias de antemano

[SuperRaskao]

parece que es un problema dificil... creo que no existe una solucion eficiente.

La solucion seguro dependera del tamaño de la matriz

segun lo que entendi lo que quieres es colocar los valores de la matriz de manera que las filas sumen lo mismo o lo mas cercano posible (que significa eso?) y solo permites intercambiar los valores que estan en una misma columna para lograrlo...

una forma de hacerlo es evaluar todas las formas en que puedes permutar las columnas para ver si una de esa satisface la condicion...

seguramente tendras que usar alguna tecnica de backtracking...

[10go]

José:
Si bien no entendí tu problema, creo que te puede ayudar estudiar los métodos de ordenacion y búsqueda (Estructuras de Datos) como burbuja, quicksort, etc. Creo que ahí podés encontrar la solución. Suerte.

[jose_d]

Hola muchachos primero que todo gracias por responder
1.

Código:

 segun lo que entendi lo que quieres es colocar los valores de la matriz de manera que las filas sumen lo mismo o lo mas cercano posible (que significa eso?)

se que el la suma no me va a dar exacto por eso necesito que sea lo mas cercanos posible

otra pregunta que me surge a partir de sus respuestas que es backtracking??
por otro lado apunta de estructura de datos creo que puede salir algo pero no tengo muchos conocimientos gracias por las respuestas voy a investigar para ver como lo resuelvo de todas maneras son bienvenidas todas las sugerencias

gracias de nuevo

[SuperRaskao]

Te pregunte eso porque hay varias formas de definir "mas cercano posible" una podria ser minimizar la maxima diferencia en el resultado de la suma de dos filas diferentes.

Backtracking es una tecnica de busqueda exaustiva... encontrar todas las permutaciones de un conjunto de numero se puede resolver usando backtracking



para resolver tu problema podrias usar lo siguiente

Código:

class Matrix {
	
	static int [][] M;
	static int [][] R;
	static int [][] T;
	
	static int mejor;
	
	
	static void permutar(int col, int pos, boolean [] U) {
		if(pos == T.length) {
		
			buscar(col + 1);
			return;
		}
		for(int i = 0; i < T.length; ++i) {
			if(U[i])
				continue;
			U[i] = true;
			T[pos][col] = M[i][col];
			permutar(col, pos+1, U);
			U[i] = false;
		}
	}
	
	static void buscar(int col) {
		if(col == T[0].length) {
			int val = evaluar();
		
			if(val < mejor) {
				mejor = val;
				R = new int [T.length][T[0].length];
				R = new int [T.length][T[0].length];
				for(int i = 0 ; i < T.length; ++i)
					for(int j = 0 ; j < T[0].length; ++j)
						R[i][j] = T[i][j];
			}
			return;
		}
		permutar(col, 0, new boolean [T.length]);
			
			
		
	}
	
	
	static int evaluar() {
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;
		for(int i = 0; i < T.length; ++i) {
			int sum  =0;
			for(int j  =0 ; j < T[i].length; ++j)
				sum += T[i][j];
			if(sum > max)
				max = sum;
			if(sum < min)
				min = sum;
			
		}
		return max - min;
		
	}
	
	
	static void imprimir(int [][] M) {
		for(int i = 0  ; i < M.length; ++i, System.out.println())
			for(int j = 0  ; j < M[i].length; ++j)
				System.out.print(" " + M[i][j]);
	}
	public static void main(String [] args) {
		M = new int [][]  {{1, 10, 4, 10},{2, 20 ,30, 3},{10, 3, 5, 9}};
		T = new int [M.length][M[0].length];
		mejor = Integer.MAX_VALUE;
		buscar(0);
		
		
		System.out.println("matriz original: ");
	
		imprimir(M);
	
	
		System.out.println("resultado: ");
		
		imprimir(R);
		
	}
}

[SuperRaskao]

Por cierto, como te dije antes la solucion es ineficiente. si pones una matriz relativamente grande tendras que esperar unos cuantos millones de años para que termine

[jose_d]

la matriz maxima es de 3x30
crees que sea muy demorado ???
que pena la demora pero apenas pude revisar

gracias