Maggio 2022 - Domanda 2

/** Domanda 2. Definite una funzione 
     void Mescola(vector<int> &V)
di argomento un vettore V di n elementi. Mescola modifica 
il valore originale di V scambiando, per ogni indice i=0,…,n-1 
del vettore, l’elemento di posto i con un qualche elemento 
successivo, di posto un qualche indice ij<n scelto a caso. 
Suggerimento. Definite una funzione void swap(int& x, int& y)
 per scambiare due valori interi. Per ottenere un intero casuale 
tra i compreso e n escluso usate la formula i+rand()%(n-i). 
Esempio. Partendo dal vettore V = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 
e applicando Mescola(V) si ottiene una permutazione completamente 
casuale di V.

 */

//TESTO DOMANDA 2: completate il seguente programma
#include <math.h>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <time.h>
using namespace std;

void scambia(int& a, int& b){
	int t = 0;
	t = a;
	a = b;
	b = t;
}

void Mescola(vector<int>& V) {
    int i = 0, j=0;
    int l = V.size();
    
    for(i=0; i<l; i++){
    	j = (i+rand())%(l-i);
	// ATTENZIONE: mettere le
	// parentesi attorno a (i+rand())
	// per normalizzare in modo corretto
	// l'indice creato (di modo che sia
	// compreso tra 0 e l-1).
        scambia(V[i], V[j]);	
    }
}
/* NOTA: se non si usa la swap(), ma si fa lo scambio
   direttamente nella Mescola, NON si deve fare:

   int t = V[i];
   V[i] = V[(i+rand())%(l-i)];
   V[(i+rand())%(l-i)] = t;

   perche' cosi' si potrebbero generare due indici casuali
   diversi. Occorre usare un indice j:
   
   j = (i+rand())%(l-i);
   int t = V[i];
   V[i] = V[j];
   V[j] = t;
*/
   



void print(vector<int> V, int a){
  if (a < V.size()) {
     cout << V[a] << " "; print(V, a+1);
  }
}

int main() {
   srand(time(NULL)); //inizializzazione successione casuale
   int n=10; vector<int> V(n); for(int i=0;i<n;++i) {V[i]=i;}
   cout << "\n V:\n"; print(V,0);
   Mescola(V);
   cout << "\n dopo aver mescolato V:\n"; print(V,0);
   cout << endl; system("pause");
}