Permutazioni vettore C con la ricorsione

[Allieva]

Salve a tutti. Premetto che non sono tanto brava con la programmazione, il mio Prof non è tanto bravo, ma a me piace tanto. Allora vi spiego. Devo fare un esercizio in C utilizzando la ricorsione.

1.Devo creare un vettore casuale di n elementi
1.creo un vettore di appoggio per creare le permutazioni
2.cercare le permutazioni
3.per ogni permutazione devo fare x calcoli
4. devo memorizzare x risultato
5. se Xrisultato è minore di XrisultatoPrecedente allora memorizzo il vettore
6. vado avanti con le permutazioni
7. torno al punto2.
8. Se vettore è uguale al vettore iniziale allora stampo vettore con Xrisultato minore.
9.Esco dal programma

per ogni permutazione del vettore dovrebbe questo xcalcolo:
A partire dal terzo elemento, per ogni elemento bisogna considerare il quadrato della differenza fra l'elemento stesso e l'elemento che lo precede, sommata alla metà del quadrato della differenza fra l'elemento stesso e l'elemento che lo precede di due posizioni.
E' troppo complicato, vero?

[meL.rtcw]

Non è troppo complicato però devi avere bene in mente 3 cose: come si fa una funzione ricorsiva, la differenza tra L e R-valore di una variabile e l'aritmetica dei puntatori.

In ogni caso la spiegazione di cosa deve fare l'algoritmo è un pelo confusionaria:
- lo scopo dell'algoritmo qual è? Da quello che ho capito io è quello di restituire il vettore che ha il risultato del Xcalcolo minore. Ricordando che il numero totale di permutazioni è n! quando stai considerando la k-esima permutazione devi avere memorizzato il risultato del Xcalcolo minore fino a quel punto ed il vettore corrispondente (questa è la parte più complicata: io passerei, alla funzione ricorsiva, per riferimento un puntatore che punta al vettore corrispondente al risultato minore ed il risultato minore alla k-esima permutazione).
- cosa deve fare quel calcolo è spiegato male (si parte dal 3° elemento e si esegue per ognuno questa formula: sqr(v[i]-v[i-1])+(sqr(v[i]-v[i-2])/2) e poi? boh).

Consiglio: prima scrivi la funzione ricorsiva che stampa tutte le permutazioni di un vettore v di n elementi (per semplicità usa pure un vettore tipo {0, 1, 2, 3, 4, ecc..} ) e poi pensa al resto (divide et impera).


ps. spero che il prof se ne sia accorto che ti piace e che ti inviti fuori una sera di queste, gh. scherzo.

[Allieva]

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

/* function to swap array elements */

void swap (int v[], int i, int j)
{
	   int	t;

	t = v[i];
	v[i] = v[j];
	v[j] = t;
}

void onChange(int a[], int v[], int n)
{
	int j;
	double x, y, z;
	
	for (j = 0; j < n; j++)
		printf ("%d ", a[v[j]]);
	printf ("\n");	
	
	for (j = 2; j < n; j++ )
	{
		x = pow(a[v[j]] - a[v[j-1]], 2);
		y = pow(a[v[j]] - a[v[j-2]], 2)/2;
		z = x + y;
		printf("Il quadrato della differenza tra %d e %d e' -> %f\n", a[v[j]], a[v[j-1]], x);
		printf("La meta' del quadrato della differenza tra %d e %d e' -> %f\n", a[v[j]], a[v[j-2]], y);
		printf("La somma tra %f e %f e' -> %f\n", x, y, z);
	}
}

/* recursive function to generate permutations */
void perm (int a[], int v[], int n, int i, void (*pfnOnChange)(int a[], int v[], int n))
{

	/* this function generates the permutations of the array
	 * from element i to element n-1
	 */
	int	j;
	int t;

	/* if we are at the end of the array, we have one permutation
	 * we can use (here we print it; you could as easily hand the
	 * array off to some other function that uses it for something
	 */
	if (i == n)
	{
		if ( pfnOnChange )
			pfnOnChange(a, v, n);
		/*
		for (j = 0; j < n; j++)
			printf ("%d ", v[j]);
		printf ("\n");
		*/
	}
	else
	{
		/* recursively explore the permutations starting
		 * at index i going through index n-1
		 */
		for (j = i; j < n; j++)
		{

			/* try the array with i and j switched */

			/* swap (v, i, j); */
			t = v[i];
			v[i] = v[j];
			v[j] = t;
					
			perm (a, v, n, i+1, pfnOnChange);

			/* swap them back the way they were */

			/* swap (v, i, j); */
			t = v[i];
			v[i] = v[j];
			v[j] = t;						
		}
	}
}
			
/* little driver function to print perms of first 5 integers */

int main(/*int argc, char *argv[]*/)
{
	clock_t c_start, c_end;
	double TempoImpiegato;  
	
	int *a;
	int	*v;
	int N;
	int i;

	N = 4;
	
	a = (int*)calloc(N + 1, sizeof(int));
	if ( !a )
	{
		printf("Error: insufficient memory.\n");
		return -1;
	}

	a[0] = 0;
	a[1] = 1;
	a[2] = 5;
	a[3] = 7;
	a[4] = 3;	
	
	v = (int*)calloc(N + 1, sizeof(int));
	if ( !v )
	{
		printf("Error: insufficient memory.\n");
		free(a);
		return -1;
	}		
	
	for (i = 0; i < N; i++)
		v[i] = i+1;
				
	c_start = clock();
	
	perm (a, v, N, 0, onChange);
	
	c_end = clock();
	TempoImpiegato = (double)(c_end - c_start) / CLOCKS_PER_SEC;
	printf("\nTempo impiegato -> %5.5f secondi\n\n", TempoImpiegato);   
	
	free(v);
		
	return 0;
}

ehehhee grazie per l'aiuto e per il consiglio del Prof ehehe..
Comunque ho fatto questo codice e ho alcuni problemi..
vorrei che mi facesse la somma di 4 + 18 +16 + 2 = 40
Dovrei visualizzare :
Vettore 15 73 e risultato dell'operazione 40

poi passo alla seconda permutazione:
1753 e risultato dell'operazione è 24

siccome 24 < risultato precedente allora
stampo il vettore 1753 e 24

e poi passo alle altre permutazioni e se non trovo numeri minori di 24 allora in finale stampo il risultato migliore ossia vettore 1753 e 24.

Spero possiate aiutarmi e se c'è qualche cosa che non va dite pure...Grazie

[meL.rtcw]

Consiglio #1: inizializza sempre le variabili. SEMPRE. xD

Se tu inizializzi z nella onChange a 0 poi puoi fare z += x + y all'interno del ciclo ed alla fine hai in z la somma totale.
A quel punto devi restituire alla funzione chiamante z in modo che possa fare il confronto con lo z minore precedente.
Come portarti appresso z ed il vettore ti ho dato un tip nel post precedente.

Ci sono un po' di errori logici, imho, nel senso prendi N = 4 e poi inizializzi "a" con 5 elementi e prendi in esame gli ultimi 4 invece che i primi 4... non capisco.

[Allieva]

void onChange(int a[], int v[], int n)
 {
 int j;
 double x, y, z = 0.0;
 for (j = 0; j < n; j++)
  printf ("%d ", a[v[j]]);
 printf ("\n");
 for (j = 2; j < n; j++ )
 {
  x = pow(a[v[j]] - a[v[j-1]], 2);
  y = pow(a[v[j]] - a[v[j-2]], 2)/2;
  z += x + y;
  printf("Il quadrato della differenza tra %d e %d e' -> %f\n", a[v[j]], a[v[j-1]], x);
  printf("La meta' del quadrato della differenza tra %d e %d e' -> %f\n", a[v[j]], a[v[j-2]], y);
  //printf("La somma tra %f e %f e' -> %f\n", x, y, z);
 }
 printf("La somma totale e' %f: \n", z);
 printf("\n\n");
 }

ho modificato la funzione onChange() e ora riesco a visualizzare per ogni permutazione il risultato dei calcoli.
Poi ho visto che nelle somme ci sono risultati uguali, quindi devo visualizzare la permutazione/i che il risultato è minore... alla fine è l'obiettivo dell'esercizio..
Come portarmi appresso z ed il vettore non ho capito bene:(

[Allieva]

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct tagMyList
{
 int *array;
 struct tagMyList *next;
} MyList;
typedef struct tagMyData
{
 int count;
 double sum;
 int arraySize;
 MyList *arrayList;
 MyList *last;
} MyData;
void onChange(MyData *pMyData, int a[], int v[], int n)
{
 int j;
 double x, y, z = 0.0;
 for (j = 2; j < n; j++ )
 {
  x = pow(a[v[j]] - a[v[j-1]], 2);
  y = pow(a[v[j]] - a[v[j-2]], 2)/2;
  z += x + y;
 }
 if ( pMyData->arrayList != NULL )
 {
  if ( pMyData->sum > z )
  {
   MyList *p2;
   MyList *p = pMyData->arrayList;
   while ( p )
   {
    free(p->array);
    p2 = p->next;
    free(p);
    p = p2;
   }
   pMyData->arrayList = NULL;
   pMyData->last = NULL;
   pMyData->count = 0;
   pMyData->arrayList = (MyList*)malloc(sizeof(MyList));
   if ( !pMyData->arrayList )
   {
    printf("Errore: memoria insufficiente.\n");
    pMyData->arrayList = NULL;
    return;
   }
   pMyData->arrayList->array = (int*)malloc(sizeof(int) * pMyData->arraySize);
   if ( !pMyData->arrayList->array )
   {
    printf("Errore: memoria insufficiente.\n");
    free(pMyData->arrayList);
    pMyData->arrayList = NULL;
    return;
   }
   pMyData->arrayList->next = NULL;
   pMyData->last = pMyData->arrayList;
   for (j=0; j<n; j++)
    pMyData->arrayList->array[j] = a[v[j]];
   pMyData->sum = z;
   pMyData->count = 1;
  }
  else if ( z <= pMyData->sum )
  {
   MyList *p = pMyData->last;
   p->next = (MyList*)malloc(sizeof(MyList));
   if ( !p->next )
   {
    printf("Errore: memoria insufficiente.\n");
    return;
   }
   p->next->array = (int*)malloc(sizeof(int) * pMyData->arraySize);
   if ( !p->next->array )
   {
    printf("Errore: memoria insufficiente.\n");
    return;
   }
   p->next->next = NULL;
   pMyData->last = p->next;
   for (j = 0; j < n; j++)
    p->next->array[j] = a[v[j]];
   pMyData->sum = z;
   pMyData->count++;
  }
 }
 else
 {
  pMyData->arrayList = (MyList*)malloc(sizeof(MyList));
  if ( !pMyData->arrayList )
  {
   printf("Errore: memoria insufficiente.\n");
   pMyData->arrayList = NULL;
   return;
  }
  pMyData->arrayList->array = (int*)malloc(sizeof(int) * pMyData->arraySize);
  if ( !pMyData->arrayList->array )
  {
   printf("Errore: memoria insufficiente.\n");
   free(pMyData->arrayList);
   pMyData->arrayList = NULL;
   return;
  }
  pMyData->arrayList->next = NULL;
  pMyData->last = pMyData->arrayList;
  for (j = 0; j < n; j++)
   pMyData->arrayList->array[j] = a[v[j]];
  pMyData->sum = z;
  pMyData->count = 1;
 }
 }
void perm(MyData *pMyData, int a[], int v[], int n, int i, void (*pfnOnChange)(MyData *pMyData, int a[], int v[], int n))
{
 int j;
 int t;
 if (i == n)
 {
  if ( pfnOnChange )
   pfnOnChange(pMyData, a, v, n);
 }
 else
 {
  for (j = i; j < n; j++)
  {
   t = v[i];
   v[i] = v[j];
   v[j] = t;
   perm (pMyData, a, v, n, i+1, pfnOnChange);
   t = v[i];
   v[i] = v[j];
   v[j] = t;
  }
 }
}
int main(/*int argc, char *argv[]*/)
{
 MyData md;
 MyList *p = NULL, *p2 = NULL;
 int *a;
 int *v;
 int N;
 int i;
 N = 4;
 a = (int*)calloc(N + 1, sizeof(int));
 if ( !a )
 {
  printf("Error: insufficient memory.\n");
  return -1;
 }
 a[0] = 0;
 a[1] = 1;
 a[2] = 5;
 a[3] = 7;
 a[4] = 3;
 v = (int*)calloc(N + 1, sizeof(int));
 if ( !v )
 {
  printf("Error: insufficient memory.\n");
  free(a);
  return -1;
 }
 for (i = 0; i < N; i++)
  v[i] = i+1;
 md.count = 0;
 md.arraySize = N;
 md.arrayList = NULL;
 md.last = NULL;
 perm(&md, a, v, N, 0, onChange);
 printf("%d permutazioni con somma minima = %f:\n", md.count, md.sum);
 p = md.arrayList;
 while ( p )
 {
  for ( i = 0; i < md.arraySize; i++ )
   printf("%d ", p->array[i]);
  printf("\n");
  p = p->next;
 }
 p = md.arrayList;
 while ( p )
 {
  free(p->array);
  p2 = p->next;
  free(p);
  p = p2;
 }
 free(a);
 free(v);
 return 0;
}

Secondo voi cosa c'è di sbagliato e come lo posso migliorare? Grazie

[meL.rtcw]

Due cose (non sono errori veri e propri, son appunti):
- nella onChange

if ( pMyData->arrayList != NULL ) {
      if ( pMyData->sum > z ) {
            // varie istruzioni
      }
      else if ( z <= pMyData->sum ) {
            // altre varie istruzioni
      }
}

quando fai quel else if dovresti mettere come condizione z == pMyData->sum in quanto logicamente il caso in cui z < pMyData->sum l'hai già processato durante il primo if. Quindi sebbene non comporti un errore tangibile è logicamente sbagliato.

- rimane, secondo me, un altro errore logico quando inizializzi "a" con 5 elementi avendo N = 4, in quanto secondo le specifiche iniziali dovresti costruire "a" in modo casuale dato il numero N di elementi.

Cmq brava. Buona l'idea della lista concatenata (suppongo tu l'abbia imparata durante il corso); applicarla ad un caso reale è tutt'altro che scontato

[Allieva]

Grazie dei consigli, il primo l`ho cambiato come mi hai detto tu..infatti devo costruire il vettore "a" con N numeri generati a caso, ma non so come gestirla.. potrei usare la funzione random?

[meL.rtcw]

Immagino di sì. Attenta però alle ripetizioni dei numeri generati dalla funzione random. Ti conviene controllare che i valori generati siano unici, secondo me.

Inviato dal mio Nexus 4 con Tapatalk 2

[Allieva]

 
int main(/*int argc, char *argv[]*/)
{
 MyData md;
 MyList *p = NULL, *p2 = NULL;
 int *a;
 int *v;
 int N;
 int i;
 N = 4;
 a = (int*)calloc(N, sizeof(int));
 if ( !a )
 {
  printf("Error: insufficient memory.\n");
  return -1;
 }

 a[0] = rand();
 a[1] = rand();
 a[2] = rand ();
 a[3] = rand();

 v = (int*)calloc(N, sizeof(int));
 if ( !v )
 {
  printf("Error: insufficient memory.\n");
  free(a);
  return -1;
 }
 for (i = 0; i < N; i++)
  v[i] = i+1;
 md.count = 0;
 md.arraySize = N;
 md.arrayList = NULL;
 md.last = NULL;
 perm(&md, a, v, N, 0, onChange);
 printf("%d permutazioni con somma minima = %f:\n", md.count, md.sum);
 p = md.arrayList;
 while ( p )
 {
  for ( i = 0; i < md.arraySize; i++ )
   printf("%d ", p->array[i]);
  printf("\n");
  p = p->next;
 }
 p = md.arrayList;
 while ( p )
 {
  free(p->array);
  p2 = p->next;
  free(p);
  p = p2;
 }
 free(a);
 free(v);
 return 0;
}

non riesco a fare il random.. che sintassi devo utilizzare?? Grazie..

[meL.rtcw]

http://www.cplusplus.com/reference/cstdlib/rand/ <-- trovi tutto quello che ti serve. Attenzione alle librerie da includere.

inizializza "a" dentro un for che non si può vedere un'inizializzazione esplicita come quella.