Temas

Dejo aquí un método -que creo que funciona- para la resolución de un sistema de "n" ecuaciones lineales con "n" incógnitas.
Está basado en el algoritmo de Gauss (no sé si otros lo llaman de Gauss-Jordan u otros de Gauss-Jacobi). Sea como sea que lo llamen consiste en dejar la matriz de coeficientes en una matriz triangular con 0 (ceros) por debajo de la diagonal principal de a matriz de coeficientes. Y luego ir resolviendo despejando in cógnitas de atrás hacia delante.

Sé que es un método poco eficiente. Para empezar los errores de cálculos sucesivos (especialmente en sistema muy grandes con muchas ecuaciones) pueden producir desbordamientos (overflow) o que, si hay términos relativamente pequeños respecto a otros, se produzcan reducciones a "1" que desvirtúen el resultado final, para sistemas de ecuaciones muy particulares. Como mi intención es simplemente una primera aproximación para reslover sistemas del tipo de los que se dan en Ingeniería (cálculo de estructuras, mallas de tuberías, etc...) de momento éso no me importa demasiado.

También la forma de introducir los datos es totalmente ineficiente -a mano-. Es sólo para pruebas; lo suyo es que sea a partir de datos de matrices que previamente se hayan almacenado en disco. Es más, esas matrices no se introducirán a mano -ni siquiera en disco- sino que provendrán de otros programas que las habrán guardado en disco a partir de otros datos (matrices de rigidez de una estructura -de construcción- a partir de sus datos de longitud de barras, inercia, material, etc; o longitud de tubería, diámetro, material, persión, etc...).

Por lo tanto, el hecho de la forma de introducción de datos no debe de ser valorado; solo el funcionamiento del algoritmo de resolución del sistema.

Por lo tanto, respecto al programa en general, me gustaría tener opiniones sobre:
- Sobre todo: ¡fallos que pueda tener! - He probado varios sistemas, algunos con bastantes incógnitas, y los ha resuelto. He probado varios sistemas con fallos "evidentes" (filas = 0; columnas = 0; filas/columnas = combinación lineal de otras filas/columnas;...) y me los ha detectado. En ese sentido, mi miedo es más bien -no que no me detecte sistemas sin solución-, sino que sistemas que SÍ tienen solución, me los detecte como que no la tienen. ¿Veis algún fallo? ¿Alguna forma de mejorarlo?

- ¿Se podría mejorar, mediante un algoritmo iterativo, la solución? He visto cosas, pero ninguna lo suficientemente clara -para mi- sobre cómo mejorar una solución a partir de una primera solución. En concreto he leído sobre los métodos de Richardson, de Jacobi, de Gauss-Seidel, que incluso empiezan con vectores/matrices de soluciones "alejadas" de la solución verdadera; cuando se podría mplementar desde una primera solución "muy aproximada" - la que ofrece el algoritmo que aquí se da-; pero no sé como implementarla.

- Por último: sé que hay un método muy potente (y con reducción de operaciones y de tiempo de cálculo y de disminución por errores de operaciones (¡justo lo que quiero disminuir!) que es la "condensación de ecuaciones"..., pero no encuentro información viable. Si alguien me puede ofrecer literatura sobre ese tema, pues estaría genial.

Bueno, aquí dejo el código que he hecho, para las críticas/comentarios/ayudas/mejoras/etc... que creáis convenientes (cualquier cosa será bien recibida):

Código (c) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>

void intro_sistema (int n, double ** a);
void combina_fila (int j, int n, double ** a); // Para dejar coeficientes de la columna a cero
void intercambia_fila (int i, int j, int n, double ** a); // Para que no haya coefic. == 0 en la diagonal
void calcula_incognitas (int n, double ** a, double * solucion); // A partir de una matriz ya triangular

int main ()
{
int n; // numero ecuaciones lineales
int i, j;
double ** a = NULL; // matriz ampliada: coeficientes | terminos independientes
double * solucion = NULL;

printf ("Introducir no. de ecuaciones: ");
scanf ("%d", &n);

a = (double **) malloc ( n * sizeof (double *) ); // filas
for (j = 0; j < n; ++j)
a[j] = (double *) malloc ( (n+1) * sizeof (double) ); // columnas
solucion = (double *) malloc ( n * sizeof (double) );

intro_sistema (n, a);

for (j = 0; j < n-1; j++)  // Procesa elementos diagonal matriz coeficientes
{
if (a[j][j] == 0)
{
for (i = j+1; i < n; i++) // Busca un coeficiente de la misma columna != 0
{
if (a[i][j] != 0)
{
intercambia_fila (i, j, n, a);
break;
}
printf ("\n\nEl sistema no tiene solucion unica"); // No hay coficiente != 0 sobre el que pivotar
return 0;
}
}
combina_fila (j, n, a);
}

if (a[n-1][n-1] == 0)
{
printf ("\n\nEl sistema no tiene solucion unica\n"); // Toda la fila inferior es de ceros
return 0;
}
else
{
calcula_incognitas (n, a, solucion);
printf ("\n\n");
for (j = 0; j < n; j++)
printf ("soluc[%d] = %lf\n", j, solucion[j]);
}
return 0;
}

void intro_sistema (int n, double ** a)
{
int i, j;
double var;

printf ("\nIntroducir matriz de coeficientes del sistema de ecuaciones lineales\n");
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
printf ("a[%d][%d] = ", i, j);
scanf ("%lf", &var);
a[i][j] = var;
}
printf ("\nIntroducir terminos independientes del sistema\n");
for (i = 0; i < n; i++)
{
printf ("b[%d] = ", i);
scanf ("%lf", &var);
a[i][n] = var;
}
}

void combina_fila (int j, int n, double ** a)
{
double factor;
int i, k;

for (i = j+1; i < n; i++)
{
if (a[i][j] != 0)
{
factor = -a[j][j] / a[i][j];
for (k = j; k < n+1; k++)
a[i][k] = (factor * a[i][k]) + a[j][k];
}
}
}

void intercambia_fila (int i, int j, int n, double ** a)
{
double var_intercamb;
int k;

for (k = j; k < n+1; k++)
{
var_intercamb = a[i][k];
a[i][k] = a[j][k];
a[j][k] = var_intercamb;
}
}

void calcula_incognitas (int n, double ** a, double * solucion)
{
double acumulador;
int i, j;

solucion[n-1] = a[n-1][n] / a[n-1][n-1];
for (i = n-2; i >= 0; i--)
{
acumulador = a[i][n];
for (j = i+1; j < n; j++)
acumulador = acumulador - (a[i][j] * solucion[j]);
solucion[i] = acumulador / a[i][i];
}
}


Pues nada, lo dicho, que se agradece cualquier comentario.

[camino []]

He escrito un código que compruebe si un grafo es o no conexo a partir de la matriz de adherencia del grafo. Creo que funciona, he hecho algunos ejemplos y parece que sí; adjunto unos gráficos. Supongo que debe de ser válido para otros. Pero me gustaría saber si a alguien se le ocurren contra-ejemplos, o si quiere exponer (puede ser por privado) una matriz de adherencia de un grafo (claro, yo los ejemplos que he hecho son a partir de grafos de los que conozco su representación gráfica en papel) para ver si funciona. Pero me gustaría probar con un grafo del que no conozca su representación gráfica en papel, sino solo su matriz de adherencia.

Pero sobre todo querría opiniones sobre el código, posibles fallos, y posibles mejoras. Solo opiniones generales, pseudocódigo quizá..., no hace falta código explícito; tampoco es para volver a escribirlo, que no tengo intención (salvo que vea fallos serios), sino para ver por dónde van los tiros.

Doy una idea general de cómo lo he hecho, luego expongo el código y luego pregunto las cosas que más me interesan.

La idea que se me ha ocurrido es algo parecido a "fuerza bruta". Se trata de recorrer todos los nodos que se pueda, a partir del primero. A partir del nodo inicial del grafo voy recorriendo un camino hasta que llega un nodo en el que no puedo ir más allá, doy marcha atrás y busco otro nodo para proseguir... y así sucesívamente. Voy yendo hacia adelante-atrás-adelante-atrás... Conforme voy agotando caminos posibles voy volviendo hacia atrás cada vez más, hasta que llega un punto en el que vuelvo al nodo de salida -después de haber ido explorando todos los caminos posibles-. En ese momento en el que he vuelto al nodo de partida veo si existe algún nodo al que no he llegado. Si existe es que el grafo es no conexo, ya que de haber habido un camino para llegar hasta él lo habría recorrido. Si no existen nodos sin visitar es que he llegado a todos y el grafo es conexo.

Ahora el código que he escrito y algunos ejemplos que he usado.

Código (c) [Seleccionar] Expandir

// Calcula si un grafo es conexo o no
#include <stdio.h>
#include <stdlib.h>

#define ORDEN_MATR (num_nodos * num_nodos)

void intro_grafo (int num_nodos, int ** matr_adher);
void procesa_grafo (int num_nodos, int nodo_actual, char * estado_nodo, int * camino, int posicion, char sentido, int ** matr_adher);
char es_conexo (int num_nodos, char * estado_nodo); // =0 si existe algun estado_nodo [i] == 0 ; =1 en caso contrario

int main ()
{
int num_nodos; // Nº de nodos del grafo
int ** matr_adher; // Matriz de adherencia del grafo
int nodo_actual; // El que se está procesando en un momento dado
char * estado_nodo; // 1 - si ya se ha pasado por él al menos una vez; 0 - en caso contrario
int * camino; // Guarda los nodos que se van recorriendo
int posicion; // subindice del arreglo camino [] que corresponde a nodo_actual
char sentido; // 1 si se va avanzando hacia nodo no visitado; 0 - si se va retrocediendo a nodo ya visitado
int i, j;

printf ("Introducir no. de nodos del grafo: ");
scanf ("%d", &num_nodos);
printf ("el numero es: %d\n", num_nodos);
// Declara arreglos
matr_adher = (int **) malloc ( ORDEN_MATR * sizeof (int *) ); // Filas
for ( i=0; i < num_nodos; i++ )
{
matr_adher [i] = (int *) malloc ( num_nodos * sizeof (int) ); // Columnas
}
estado_nodo = (char *) malloc ( num_nodos * sizeof (char *) );
camino = (int *) malloc ( num_nodos * sizeof (int *) );

// Inicializa variables
for (i = 0; i < num_nodos; i++)
for (j = 0; j < num_nodos; j++)
matr_adher [i][j] = 0; // Por defecto ningun nodo esta conectado con nigun otro
for (i = 0; i < num_nodos; i++)
estado_nodo [i] = 0; // Al inicio no se ha visitado ningun nodo
sentido = 1;
posicion = 0;
nodo_actual = 0;
camino [0] = 0;

// Ejecucion
intro_grafo (num_nodos, matr_adher);
procesa_grafo (num_nodos, nodo_actual, estado_nodo, camino, posicion, sentido, matr_adher);
if ( es_conexo (num_nodos, estado_nodo) )
printf ("El grafo es conexo\n");
else
printf ("El grafo NO es conexo\n");

return 0;
}

void intro_grafo (int num_nodos, int ** matr_adher)
{
int nodo1, nodo2, peso;

printf ("Introducir conexiones y pesos entre nodos en la forma:\n");
printf ("nudo inicial... nudo final... peso conexion\n\n");
printf ("No es necesario introducir conexiones reciprocas, la conexion i-j automaticamente es = a la j-i\n");
printf ("Una nueva conexion i-j actualiza a la anterior si existiera\n");
printf ("para finalizar el grafo introduzcir nudo incial = 0 y nudo final = 0\n\n");
for (;;)
{
printf ("Nodo inicial: ");
scanf ("%d", &nodo1);
printf ("Nodo final: ");
scanf ("%d", &nodo2);
if (nodo1 == 0 && nodo2 == 0)
return;
else
{
printf ("Peso conexion: ");
scanf ("%d", &peso);
if (nodo1 != nodo2)
{
matr_adher [nodo1][nodo2] = peso;
matr_adher [nodo2][nodo1] = peso;
}
printf ("\n");
}
}
}

void procesa_grafo (int num_nodos, int nodo_actual, char * estado_nodo, int * camino, int posicion, char sentido, int ** matr_adher)
{
int j;
printf ("\nfuncion procesa_grafo\n"); // SOLO PARA DEPURACION DEL PROGRAMA - BORAR
printf ("nodo actual: %d\n", nodo_actual); // SOLO PARA DEPURACION DEL PROGRAMA - BORAR
estado_nodo [nodo_actual] = 1;
if ( (nodo_actual == 0) && (sentido == 0) )
return;

for (j = 0; j < num_nodos; j++)
if ( (matr_adher [nodo_actual][j] != 0) && (estado_nodo[j] == 0) )
{
posicion += 1; // Recorre la fila de la matriz del nodo en proceso hasta encontrar
camino [posicion] = j; // una conexión con un nodo que no hay sido visitado anteriormente,
sentido = 1; // si lo encuentra cambia el control del proceso a ese nodo
procesa_grafo(num_nodos, j, estado_nodo, camino, posicion, sentido, matr_adher);
}

posicion -=1; // Caso de recorrer toda la fila y no encontrar un nodo en avance
sentido = 0;  // retrocede al nodo anterior y cambial el control del proceso a ese punto
procesa_grafo (num_nodos, camino [posicion], estado_nodo, camino, posicion, sentido, matr_adher);
}

char es_conexo (int num_nodos, char * estado_nodo)
{
int i;
for (i = 0; i < num_nodos; i++)
if ( estado_nodo [i] == 0 )
return 0;
return 1;
}


Algunos ejemplo que he hecho



Algunas consideraciones:
- He considerado que un nodo no puede estar conectado consigo mismo; para saber si los nodos están conectados entre sí no hace falta, y estorba para el algoritmo.
- También he considerado solamente grafos en los cuáles los nodos están conectados en ambas direcciones: si se puede ir desde a hacia b, entonces también se puede ir desde b hacia a. (Creo que existen grafos en los cuáles puede haber trayectorias en un sentido pero no en el contrario).
- El peso de la conexión únicamente es útil para saber si dos nodos están conectados (==0 SI // !=0 NO), daría igual que fuesen sencillamente 1 ó 0. He dejado cualuier entero solamente por generalidad de la función de entrada de datos (no se trata de calcular longitudes mínimas o máximas de distintos caminos). Incluso podrían ser negativos ya que el programa solo considera si son o no igual a cero.
- He utilizado un arreglo (camino []) y una variable (posicion) para ir recorriendo la malla. Aunque creo que se podría utilizar una pila LIFO y push-pop).

Defectos que ya veo:
- Si el nodo 0 está aislado el programa se pierde. Se podría corregir fácilmente haciendo que antes de comenzar a procesar se comprobara que la fila 0 de la matriz no es todo ceros; pero es trivial y no merece la pena; no afecta al algoritmo.
- He visto -a través de las líneas 90 y 91 que están solamente para depuración- que el algoritmo pasa varias veces por nudos que no haría falta (no afecta a la eficacia del código pero sí a la eficiencia del mismo: retardo). Veo que ésto es así por comenzar siempre el análisis de cada nuevo nodo (fila) desde cero (línea 96) en lugar de hacerlo desde el último nodo (columna) que se visitó a partir del nodo_actual. Pero no estoy muy seguro de cómo corregirlo; se me ocurre tener otro arreglo similar a camino [] en el cuál se anote ese nº de columna y comenzar el bucle de la línea 96 en ese lugar en vez de cero. No lo he hecho porque, bueno, lo que me importa es más bien que la idea general funcione, ya que no se trata de una aplicación práctica. Además añadiría más argumentos a la función procesa_grafo, que ya tiene bastantes.

Entonces:
- ¿Algún error de bulto? ¿Fallos, ejemplos de grafos que hagan que claramente el algoritmo no funcione...?
- ¿Alguna idea para corregir el bucle de la línea 96 y que no empiece desde cero?
- ¿Se mejoraría la eficiencia del programa usando una pila en lugar del arreglo y la posición?
- Y lo principal: ¿existiría otro tipo de algoritmo que no fuera recorrer todos los caminos posibles?; no sé, algo de tipo matemático, alguna propiedad matemática de la matriz de adherencia, algún método que use de expresiones matemáticas, en lugar de un algoritmo de recorrido paso a paso, que determine si el grafo es conexo o no. O en caso de algorimo de recorrido, ¿otra forma de hacer el recorrido que sea más eficiente?
- Por último: ¿alguna manera de programar más elegante (o eficaz) sin usar una función recursiva. Tengo entendido que los goto, las variables globales y la recursividad (por este orden) no son muy bienvenidas por los programadores ( al menos en C); y si se puede escribir un código más acorde a los usos habituales o deseables en programación, pues bienvenidos sean consejos.

Gracias de antemano por las respuestas.

[estándar]

¿Existe alguna razón por la que un mismo código C -estándar + librerías stdio.h - stdlib.h- se comporte de forma distinta en un entorno Linux-Ubuntu -compilador gcc-, que en otro entorno Windows-compilador-MinGW (gcc).

En concreto:

para una variabe declarada como:

Código (c) [Seleccionar] Expandir

int variable;

y un uso de ella con:

Código (c) [Seleccionar] Expandir

scanf (%d", &variable);

en el entorno Linux-Ubuntu me funciona con cualquier nº entero, pero en Windows-MinGW sólo me funciona si variable <=9. En cuanto  le meto variable = 10, 11, 12,... el programa simplemente se sale al terminal sin dar explicaciones.

NOTA: en el entorno Linux el nombre del programa es el mismo del programa fuente sin ".c"; en en el entorno Windows lo llamo nombre del programa ".exe". Lo he probado tanto desde Visual Studio -a través del run- como directamente en CMD-Windows compilando con gcc a mano y ejecutando a mano nombre-del-programa.exe.
En el entorno Linux siempre en consola compilado y ejecutado a mano.

[si el compilador o el Sistema Operativo adaptan esas operaciones]

Tengo entendido que la rapidez de las operaciones de lectura/escritura en disco dependen de si se hacen varias en bloque o como datos aislados uno a uno. No sé seguro si ésto es así -y menos en los SSD-, es lo que yo tenía entendido; pero si no es así se puede ahorrar la lectura de lo que sigue.

Dado por cierto lo anterior lo que quiero saber es si el compilador o el Sistema Operativo adaptan esas operaciones a la memoria disponible -de una forma transparente para el programador- o debe ser éste quien programe esas operaciones de la forma más eficiente.

Lo aclaro con un ejemplo concreto. Supongamos que un programa hace una multiplicación de matrices que están almacenadas en archivo en disco y que, por su dimensión, no caben en la memoria del ordenador y, por tanto, no pueden leerse de una tacada y operar con ellas en memoria, guardar el propducto también en memoria y al final grabar en disco el resultado de una vez.

Lo más fácil para el programador -pero quizá no lo más eficiente en tiempo de ejecución- es mediante bucle leer un dato de fila de una matriz, leer un dato de columna de la otra, multiplicar y acumular el producto, proceder igual con el siguiente elemento de fila, el siguiente de columna, volver a acumular el producto y cuando se haya terminado el producto fila x columna grabar el resultado en disco; y volver a proceder con fila-columna.

La pregunta es: ¿si se programa de esa forma, en tiempo de ejecución, se ejecuta también así o bien al compilar, o al ejecutar el S.O. realizan las operaciones E/S (disco) en bloques según la RAM disponible y hacen esas operaciones en pequeños bloques en RAM?

¿O bien es responsabilidad del programador -si quiere mejorar la eficiencia- el prever más bucles adicionales y más arreglos adicionales que realizen, por ejemplo, lectura de 100 datos de fila, 100 de columna (el 100 es un ejemplo, podría ser otro), los almacenen en en RAM, operen con ellos, realicen otras 100 lecturas, etc., hasta terminar con fila-columna, almacenar en otro arreglo (de otros 100 datos), proseguir multiplicando, cuando ya tenga 100 resultados escribirlos de golpe en el disco... y proseguir hasta acabr el producto de las matrices?

En resumen: que si el programador para mejorar la efciencia tiene que programar (valga la redundancia) las operaciones de lectura/escritura en bloque adaptados a la RAM, o puede confiar esa labor al compilador o al S.O.: en tiempo de ejecución de forma transparente para él.

[vida media]

¿Hay estudios/muestreos, ya sean hechos por los propios fabricantes o por organizaciones de terceros: comercializadores, usuarios, entidades de control independientes, organizaciones  universitarias, investigadores, organizaciones de consumidores, etc, que hayan estudiado sobre sobre la vida media de los ordenadores de gama medio/baja encendidos contínuamente? ¿Según marcas/modelos? Ya sean portátiles o de sobremesa.

¿Y sobre cuál elemento del ordenador es el que suele fallar primero? Excluídas las pantallas/impresoras/teclados/unidades extraíbles. Referido a microprocesadores, ventiladores, memorias, discos duros.

Siguiendo las indicaciones aportadas por Serapis en  este hilo sobre la similtud de las permutaciones de "n" objetos con los números -en base "n"- de "n" dígitos, he escrito un código que creo funciona.

Al menos para 3-4 parece que lo hace correctamente; para más me es difícil saberlo porque visualmente y de memoria empiezan ya a ser muchas permutaciones. Pero por el aspecto visual conforme va calculando y por inducción -si funciona para n, debería de funcionar para n+1- parece que sí. Además he añadido unas líneas (no necesarias) para comprobar el nº total de permutaciones (líneas 14, 35, 45) y contrastarlo con n! y también concuerda.

Cosa distinta será la eficacia y por éso quería tener opiniones. Sobre que secuencias de código  son poco eficaces y cómo se podrían mejorar. Solo ideas generales, ni siquiera pseudo-código, no estoy pensando en escribir una aplicación como tal sino tener una idea de conjunto de cosas que no se deban hacer en programación.

Yo, algunas me huelo. Por ejemplo yo determino la 1ª y 2ª permutaciones porque la 1ª es el nº menor y la siguiente la misma permutando los dos elementos de menor orden (los 2 de la derecha). Pero a partir de ahí ya voy a saco aumentando 1 el nº y comprobando si es permutación o no. Imagino que (matemáticamente) se podrían saltar varios elementos, dependiendo de la base "n"; pero lo sé.

Otra cosa que me huelo que es mejorable es que yo para determinar si es una permutación o no, yo lo hago a cascoporro, comparo a partir del 2º elemento por la izquierda (el [1]) y hasta el último (el [n-1]) con todos los anteriores, y quizá éso haya formas de mejorarlo comparando por parejas o algo así, no sé.

También tras cada nueva permutación encontrada comprueba si es la última, para no seguir el bucle indefinidamente, pero a lo mejor habría alguna forma de ahorrar comprobaciones. A mí no se me ocurre. Solamente comprobar si el total es = a n!; pero éso no loquiero hacer (el cálculo que he hecho del total es solamente a efectos de contrastar si el código coincide con el nº que debe de salir).

Yo lo he intentado hacer lo más simple y legible posible, pero saber si habría otras maneras de hacerlo más legible o más eficaz. Siempre referido a este tipo de algoritmo, no a los otros que se comentaron en el hilo señalado. (Si me animo igual lo intento con el algoritmo que construye una permut. siguiente a una dada).

Código (c) [Seleccionar] Expandir

// Escribe las permutaciones de "n" elementos
#include <stdio.h>
#include <stdlib.h>

void imprime (int n,  int [] );
void cuenta_uno (int n, int []); // Aumenta 1 unidad al nº en base "n"
int es_permutacion (int n, int []); // Devuelve 1 si es permutación y 0 si no lo es

int main ()
{
int n, i;
int *digitos; // de un nº de "n" dígitos en base "n"
int suma_comprob;
int total_permut = 2; // Solo para comprobar si coincide con n! BORRAR*********

printf ("Introducir nº de elementos a permutar: ");
scanf ("%d", &n);
digitos = (int *) malloc ( n*sizeof (int) );
for (i = 0; i < n; ++i) // primera permutación
digitos[i] = i;
imprime (n, digitos);

i = digitos[n-2]; // segunda permutación
digitos[n-2] = digitos[n-1];
digitos[n-1] = i;
imprime (n, digitos);

// permutaciones subsiguientes
for (;;)
{
cuenta_uno (n, digitos);
if ( es_permutacion(n, digitos) )
{
imprime (n, digitos);
total_permut += 1; // BORRAR*********

// Comprueba si es última permutación
suma_comprob = 0;
for (i= 0; i < n; ++i)
if (digitos[i] == n-1 - i)
++suma_comprob;
if (suma_comprob == n)
{
free (digitos);
printf ("\nTotal permutaciones = %d\n", total_permut); // BORRAR*******
return 0;
}
}
}
}

void imprime (int n, int digitos[])
{
int i;
printf ("%d-", digitos[0]);
for (i = 1; i < n-1; ++i)
printf ("%d-", digitos[i]);
printf ("%d\n", digitos[n-1]);
}

void cuenta_uno (int n, int digitos[])
{
int posicion; // digito que se trata en un momento dado: [0], [1],...,[n-1]

posicion = n-1;
if (digitos[posicion] + 1 == n)
do
{
digitos[posicion]= 0;
posicion -= 1;
}
while (digitos[posicion] == n-1);
digitos[posicion] += 1;
}

int es_permutacion (int n, int digitos[])
{
int i, j;

// Se comprueba que todos los digitos[] sean distintos entre sí
for (i = 1; i < n; ++i)
for (j = 0; j < i; ++j)
if (digitos[i] == digitos[j])
return 0;
return 1;
}


https://www.elperiodico.com/es/sucesos/20211103/chico-conoce-chico-facebook-acaba-12617137

También hay que ser ingenuo para tener una relación meramente electrónica y confiar lo suficiente como para invertir dinero. Hay personas que van pidiendo a gritos que las estafen.

Me han hecho esta pregunta de Física -Óptica- que no he sabido contestar:
Según las leyes de reflexión de la luz, el ángulo del haz de luz reflejado es igual al del haz de luz incidente. El ángulo da igual el que sea. Hay un ángulo de entrada, una perpendicular a la superficie de reflexión, y un ángulo de salida. Respecto de esa perpendicular, el ángulo de entrada y el de salida son iguales. No hay direcciones ni ángulos preferentes.

Entonces: ¿por qué al mirarte en un espejo tu mano izquierda se refleja en tu derecha, y viceversa, pero tu cabeza no se refleja en tus pies y tus pies en tu cabeza? O, de otra forma, ¿por qué las cosas de la izquierda se reflejan en la dereha y las de derecha se reflejan en la izquierda, pero en cambio, las de arriba no se reflejan abajo y las de abajo arriba? ¿Si en las leyes de reflexión no hay direcciones ni ángulos preferentes?

[estado]

Recientemente se ha restringido la capacidad de modificar/editar mensajes en el tiempo, reduciéndola a un cierto tiempo a partir del mensaje original; por lo visto debido a que  algunos abusaron de la anterior disponibilidad de hacerlo indefinidamente para borrar sus textos escritos anteriormente.

No entro ni salgo en la decisión tomada por el staff. Pero si entro en un asunto colateral derivado del mismo. Como consecuencia de esa restricción no se puede cambiar el indicativo de un mensaje respecto de su estado; lo llamo así a falta de otro calificativo. Me refiero al icono que aparece en la 2ª columna por la izquierda en los tablones de mensajes. El que indica si es una pregunta, si ya está resuelto, etc.

En concreto veo que no se puede cambiar el icono y poner el de que ya está resuelto cuando un tema efectivamente está resuelto.

Por ejemplo me ha pasado en este tema abierto por mi, que ya está resuelto pero sólo puedo indicarlo en mi último mensaje:

https://foro.elhacker.net/programacion_general/iquestexiste_algun_algoritmo_para_escribir_las_pemutaciones_de_n_elementos_sin_almacenar_las_de_n1_elementos-t512494.0.html;msg2251655#msg2251655

Pero no aparece en el tablón general como resuelto:

https://foro.elhacker.net/programacion_general-b18.0/

Aparece en el mensaje, pero no en el tablón. Antes, cuando se podía editar, se podía cambiar el icono del primer mensaje cuando, después de respuestas satisfactorias, se podía dar el tema por resuelto.

Ahora no se puede y, evidentemente, en el primer mensaje no se puede dar el tema por resuelto o no resuelto, pues no se sabe en qué va a acabar la cosa.

Así que propongo que, aunque no se pueda editar el texto pasado cierto tiempo, sí se pueda modificar el icono de resuelto/pregunta/lo-que-sea indefinidamente en el tiempo por el autor del mensaje (no por otros).

[NO el nº de permutaciones]

Pues básicamente lo que quiero saber es éso. Yo sé formar las permutaciones de n elementos a partir de las de n-1 elementos. Solo se necesita partir de la definición de permutación. Si tienes las de n-1 elementos, solo hay que ir intercalando -por ejemplo suponiendo que las tienes escritas con los elementos de izquierda a derecha- el nuevo elemento n desde el lugar 0 hasta el lugar n+1 en todas la permutaciones anteriores de n-1 elementos.

Con lo cual puedes escribir (en teoría) un programa que escriba las permutaciones de cualquier número n de elementos. En realidad serían las permutaciones de n nºs naturales; ya luego tendrías que tener n signos gráficos asociados, pero con con permutar n nºs enteros (considerados como números no como dígitos) bastaría.

Así, para cualquier número n bastaría ir calculando/escrbiendo las permutaciones de 2 elementos, a partir de ellas las de 3 elelementos , y así sucesivamente hasta las de n elementos.

Pero claro, tienes que tener capacidad de almacenaje de las permutaciones de un número de elementos creciente, que además con las permutaciones es brutal; crece factorialmente.

Por eso me he preguntado si existiría un algoritmo que no necesitase almacenar las permutaciones de n-1 elementos, sino que solo mediante bucles fuese capaz de escribir las permutaciones directamente. De existir tal cosa podría ponerse el programa a trabajar, y aunque al final a la larga sería lo mismo, puesto que las permutaciones habría que o guardarlas en disco o guardarlas en papel, y el tiempo de trabajo del programa crecería hasta infinito -según le pidieras permutaciones de un nº creciente de elementos-; pero al menos, no colapsaría previamente por falta de almacenamiento. En todo caso colapsaría en el tiempo.

Yo le he dado algunas vueltas al asunto y creo que no, que no es posible tal algoritmo, y que cualquier algoritmo pasa por tener almacenadas las permutaciones de n-1 elementos para poder calcular las de n elementos. Pero como sé que -en esto- no paso de ser una medianía por eso pregunto.

¿Habría alguna manera de ir reproduciendo las permutaciones de un nº cualquiera de nºs naturales? ¿Sólo mediante bucles o algo así sin almacenar las de un nº de elementos anteriores?

----------------------------

A raíz de esta pregunta me surgió otra que, en puridad, debería estar en un foro diferente, el de Dudas Generales, o algo así. Pero bueno por no complicar la dejo aquí.
Y es: ¿existe alguna aplicación práctica (Ingeniería, Física... lo que sea) que necesite tener las permutaciones de un nº variable elementos?
NO el nº de permutaciones, que si sé que éso se emplea, desde la Física Termodinámica Estadística, pasando por la Mecánica Cuántica, hasta disciplinas probabilísticas. No, no el nº de permutaciones, sino las permutaciones en sí mismas. ¿Hay alguna aplicación práctica que las necesite?

Antes de nada decir que he buscado si el tema se había tratado antes. No lo he encontrado (igual por torpeza mía) así que lo expongo.

Tampoco he encontrado (a lo peor también por torpeza) forma de saber la fecha del primer mensaje que inicia un hilo, sin tener que entrar a leer el hilo. Desde el tablón general, desde el tablón del subforo o desde el tablón de últimos mensajes.

Así que sugiero que si fuese posible (no sé si lo será por las condiciones técnicas del foro), se pudiese saber la fecha de inicio de un hilo, la del primer mensaje que lo inicia, sin tener que entrar a leerlo, en la información previa.

Lo digo porque me ha pasado ya varias veces que entro a leer un mensaje reciente y me encuentro con que es alguien respondiendo a un mensaje de hace un año, o a veces bastante más como 5, 8 o 12 años. Es cierto que si sigues el foro día a día, y viendo el número de mensajes, hay casos en que te puedes imaginar que si el número es grande y el título no te suena de nada, debe de ser un mensaje antiguo. Pero hay otras veces en que si te pasas sin mirar el foro 6 - 7 días o más y el número de mensajes no es muy grande, piensas que se trata de un tema reciente.

Por ello pienso que sería buena idea, de ser posible, indicar en alguno de los tablones, la fecha de origen del primer mensaje de un hilo.

Donde vivo, desde hace unos 10 - 15 días, han aparecido al menos 3 redes wifi que tienen la característica de tener el nombre igual que otras ya existentes previamente -y vistas por mi desde hace bastante tiempo- mas un añadido terminado en "_ext" o "_EXT".

Por ejemplo si había una red de nombre "ALGO" aparece una red de nombre ALGO_EXT o ALGO_ext. A veces aparece una red con nombre + _ext///_EXT al mismo tiempo que la del nombre original, otras veces aparece solamente la red de SSID original y otras veces solamente la red con extensión _ext///_EXT.

Entre ellas está una que tiene el mismo SSID que la mía + "_ext". Por eso me mosquea, claro.

No he llegado a detectar ningún patrón temporal de aparaciones/coincidencias/concurrencias entre ellas y/o las de nombre original (por nombre original me refiero a las que no llevan extensión _ext///_EXT).

Los nombres originales de las redes (sin el _ext///_EXT) son los nombres o bien de routers o bien de ISPs. (MOVISTARXXXX, VodafoneXXXX, TP-LinkXXXX).

Como digo todas han aparecido en un periodo de 10 - 15 días.

Es un bloque de pisos. Las redes que aparecen de vez en cuando tienen una energía de señal diferente entre ellas y discordantes con las energías de las señales de redes con SSID sin el _ext///_EXT.

¿Alguna idea de a qué puede ser debido?  ¿Y/o de cómo investigar que pasa?

[reales]

Muchas veces recibimos mensajes e-mail procedentes de una dirección tales cómo:

nospam@unadireccióndecorreo.es

etc... (más o menos parecidas)
que proceden de webs y direcciones de correo reales (porque nos ha llegado el mensaje, si no, no nos habría llegado).

Puede ser quizá porque hemos intentado crearnos una cuenta en algún site, quizá porque alguien le ha dado nuestra dirección de correo a terceros, porque nosotros mismos nos hemos registrado en alguna web dando un mail, por lo que sea... y nos envían correo, por lo que sea. Pongamos que recibimos un mensaje con un remitente de ese tipo. Si le respondemos, o si enviamos u mensaje nuevo a esa dirección, ¿qué sucede con nuestro mensaje al llegar a su destino (el de ésa dirección que comienza con "no.spam"...etc) ?:

¿
-Que el receptor (no personalmente obviamente sino su programa de servidor) incluye el mensaje en una lista donde normalmente no la mirará nunca y pasado un cierto tiempo se borrará
-Que el receptor (en el sentido indicado antes - su programa) sencillamente borra el mensaje recibido y el Administrador del sitio nunca sabrá siquiera que ese mensaje estuvo allí
?

¿Otra cosa distinta de las anteriores?

No sabía si poner este tema aquí o en Hardware o en Electrónica. Me decido a ponerlo aquí por si hubiera formas de hacerlo mediante software/comandos-de-router.

Lo que quiero hacer es que la señal que manda mi router (los dB) para conectar mediante wifi con los dispositivos de red, sea más débil.

Pero lo querría hacer portable/desmontable. Supongo que físicamente lo podría hacer a base de "recluir/confinar" el router en una zona mediante fábrica (ladrillos/cemento,...) u otras barreras físicas. Pero lo que deseo es algo que no confine permanentemente el router (el aparato físico). Sino que pudiera montarlo/desmontarlo. ¿Quizá a base de chapas metálicas que se pudieran simplemente poner arriba-abajo-por-los-lados del router? ¿Qué espesor/material deberían ser? ¿Podría hacerse?

¿Podría hacerse mediante software; que el router emitiese con una señal de radio de menor intensidad que la que viene por defecto de fábrica, sin necesidad de barreras físicas exteriores que disminuyan la amplitud de la señal de radio?

Una mini-contribución muy tonta, pero bueno, igual algún dia le sirve a alguien para algo.

Son algoritmos para desordenar y ordenar números naturales, pero como esos números a su vez pueden ser subíndices de listas, arreglos, vectores, tuplas... o como quiera que se les llame, pueden servir para desordenar/ordenar otras cosas.

Por ejemplo ordenar listas de palabras, de entradas de datos, etc.

En cuanto a desordenar, normalmente para lo que sirven es para simular cosas al azar. Por ejemplo un bingo, o cualquier lotería. O, por ejemplo, si se tiene un arreglo de 52 elementos correspondientes a una baraja, si se desordenan los subíndices del arreglo se desordena el arreglo y se simula el barajamiento (vaya palabro, no sé si existe). O un arreglo de 28 elementos correspondientes a las fichas de dominó, al desordenar los subíndices se simula el "meneillo" de las fichas antes de jugar.

También se podrían simular cambios al azar para juegos de recorrido de itinerario con "incidentes" al azar. Por ejemplo, supongamos que queremos hacer un "Juego de la Oca" donde los "incidentes" (la posada, el puente, la calavera, las ocas...) no estén siempre en el mismo lugar sino que en cada nuevo juego se distribuyan en el itinerario de diferente manera, se podría usar.

Explico brevemente de palabra los algoritmos (no descubro las Américas, todo el mundo los conocerá).

DESORDENAR: en cada pasada se toma un elemento al azar de los que van quedando. Al principio se elige entre todos. El elemento elegido se extrae de la lista almacenándolo temporalmente en una variable. Se "corre" toda la lista desde el elemento seleccionado hasta el final. Si imaginamos la lista de elementos en horizontal, con el elemento inicial a la izquierda y el final a la derecha, pues desde el elemento seleccionado al azar y hacia la derecha se pasa cada elemento un lugar hacia la izquierda. Y luego se coloca el elemento extraído, almacenado temporalmente en una variable, en el último lugar (en el el último de la derecha). Ahora se ddisminuye en una unidad el nº de elementos a sortear ( ya solamente se sortea entre los elementos que van quedando a la izquierda) y se repite el proceso hasta llegar a que sólo quede un elemento a la izquierda y ya todos estarán desordenados.

ORDENAR: se va recorriendo la lista de izquierda a derecha, comparando cada elemento "i" con el siguiente "i + 1", cuando se encuentra que un elemento "i" es mayor que el siguiente "i + 1" (si es ordenar de menor a mayor; si fuera de mayor a menor la comparación sería que "i" fuese menor que "i + 1") se intercambian de lugar. Antes de iniciar el recorrido se pone una bandera (flag) que se cambia cuando se produce un intercambio de posiciones. El bucle es -en principo- infinito, sin condiciones, pero cuando la bandera no ha cambiado (no se ha producido ningún intercambio de posiciones) es que ya todos los elementos han quedado ordenados, y se sale del bucle.

Lo dejo todo den un programa en Java que, primero pide el nº de elementos que tendrá la lista, construye la lista de números naturales desde 0 hasta el ingresado - 1, e imprime la lista inicial ordenada. Luego la desordena e imprime la lista desordenada, y posteriromente la vuelve a ordenar e imprime la lista nuevamente ordenada. He señalado en el mini-programita los algoritmos de desordenación/ordenación.

Código (java) [Seleccionar] Expandir

import java.util.Scanner;

public class DesordenarOrdenarLista {
public static void main(String[] args) {
int numElementos;
int [] lista;
int numAzar;
int numSup; // para elegir numAzar entre 0 y numSup - 1
int var = 0;// guarda temporalmente un elemento de lista[]

Scanner teclado;
teclado = new Scanner(System.in);
System.out.println ("Introducir longitud de la lista");
numElementos = teclado.nextInt ();

lista = new int[numElementos];
for (int i = 0; i < numElementos; i++) {
lista[i] = i;
}
System.out.println ("Lista ordenada:");
for (int i = 0; i < numElementos; i++) {
System.out.print (lista[i] + "    ");
}
System.out.println ("");

// algoritmo de desordenación
numSup = numElementos;
for (int i = 0; i < numElementos - 1;i++) {
numAzar = (int) (Math.random() * numSup);
var = lista[numAzar];
for (int j = numAzar; j < numElementos - 1; j++) {
lista[j] = lista[j+1];
}
lista[numElementos - 1] = var;
numSup--;
}
// fin de algoritmo de desordenación

System.out.println ("Lista desordenada:");
for (int i = 0; i < numElementos; i++) {
System.out.print (lista[i] + "    ");
}
System.out.println ("");


// algoritmo de ordenación
for (;;) {
char flag = 0;
for (int i = 0; i < numElementos - 1; i++) {
if (lista[i] > lista[i+1]) {
var = lista[i];
lista[i] = lista[i+1];
lista[i+1] = var;
flag = 1;
}
}
if (flag == 0)
break;
}
// fin de algoritmo de ordenación

System.out.println ("Lista nuevamente ordenada:");
for (int i = 0; i < numElementos; i++) {
System.out.print (lista[i] + "    ");
}
System.out.println ("");
}
}



¿Por qué motivo podría tener alguien una red oculta sin contraseña? Si la ha ocultado por seguridad ¿por que la deja abierta y no le pone también contraseña?

No sé si este tema se ha tratado antes. Yo he buscado tanto con el buscador del foro como con Google opción site:foro.elhacker.net y no he encontrado nada.

No me refiero a pruebas sobre hackerismo, como war zone o similar, sino a hacer pruebas sobre las capacidades técnicas de edición de los mensajes del foro: incluir enlaces, vídeos, imágenes, editar código Geshi, cambios de color, tamaño de letras, posibilidad de incluir tabulados, viñetas, letras/fórmulas distintas al alfabeto tradicional, etc.

Sería un foro sólo para hacer pruebas de cómo escribir/editar los mensajes del foro de forma correcta; sin contenido real importante. Hay gente que dice no saber bien cómo insertar imágenes, etc. A mí mismo me ha pasado que he enviado imágenes demasiado grandes, y eso entorpece la lectura en los foros "reales", Pues en este foro se podrían hacer las  pruebas previas.

No ocuparía mucha memoria del servidor ya que, al ser pruebas, los mensajes se podrían eliminar, por ejemplo, a las dos semanas. Sí que ocuparían tiempo de moderadores ya que, inevitablemente podrían ser usados para spam/publicidad o contenidos inapropiados.

Podría tener una sección fija de mensajes sobre cómo utilizar las capacidades técnicas de edición del foro. He visto por ahí algún mensaje sobre cómo insertar imágenes, pero se podrían poner más: añadir enlaces, cómo utilizar etiquetas Gueshi, para qué sirven y cómo poner los símbolos de 'resuelto', 'pregunta', etc que aparecen a la izquierda; en fin, sacarle todo el jugo a la edición de mensajes. Como y cuando modificar mensajes u optar por un mensaje nuevo etc.

Como añadido, recomendaría que en la pantalla de nuevos registros, además de la letra pequeñita sobre las condiciones legales, se pusiera en letras bien grandes que antes de participar se leyeran los mensajes X... (aquí una lista) sobre normas de participación, y se citara la existencia de este sub-foro para hacer pruebas sin incordiar en los foros 'reales' con imágenes grandes, chicas, preguntas sobre 'cómo pongo ésto o aquello', etc; dejando los mismos sólo para contenido 'real'.

Es sólo una idea.