Problema con semplice scambio

[Giova411]

Buongiorno a tutti,
ho un po' di vergogna a chiedervi come risolvere, ma in modo efficente, uno scambio tra elementi in un vettore.
Abbiamo interi da 1 a N: sono precisamente tutti gli interi fra 1 e N.
Dovrei scambiarli di posto per ordinarli e tenere conto di ogni scambio, voglio il metodo più veloce.
Esempio: dato in input N=4 ed un vettore tipo: 3 2 4 1, dobbiamo ordinarlo dicendo che abbiamo fatto 2 scambi.
Cioé una sequenza di lunghezza minima ci dice di scambiare di posizione 1 e 3 e poi scambiare 3 e 4.

Spero sia chiaro.
grazie

[Giova411]

In C++, con lettura e scrittura da file creati allo scopo

#include <fstream>
using namespace std;
void swap(int a[], int i, int j)
{
 int temp = a[i];
 a[i] = a[j];
 a[j] = temp;
}

int main ()
{
  ifstream in ("input.txt");
  ofstream out ("output.txt");
  int n;
  in >> n;
  int *a = new int[n];   
 
  for (int i = 0; i < n; i++)
   in >> a[i];     

 int j = 0;
 int i = 0;

 while (( i<n ) )
 {
   if (a[i] != (i+1))
   {
   int t = a[i];
   swap(a,i,t-1);
    j++;
   }
i++;
 }
  out <<j<< endl;
  delete [] a;
  return 0;
}

Però non funziona bene!!!!! =(

[vict85]

Ma devi trovare il numero minimo di scambi? Un numero approssimativo lo puoi fare contando il numero di operazioni di scambio fatte da un qualsiasi metodo di ordinamento. Ma questo non fornisce il numero minimo di scambi, ma solo una sua approssimazione per eccesso.

Dovrei ragionarci per bene sopra ma penso che si possa costruire un prodotto di scambi ‘minimale’ a partire dalla rappresentazione della permutazione in cicli disgiunti. Un metodo corretto penso sia quello di portare la permutazione come prodotto di cicli disgiunti e tenere conto che il numero minimo di scambi di un ciclo è \(n-1\) dove \(n\) è la lunghezza del ciclo. Nota che il metodo che propongo non fa veri e propri swap ma mantiene il valore temporaneo durante il ciclo.

Questo è un codice che implementa ciò che ho descritto. Ma bisognerebbe assicurarsi che dal punto di vista teorico funzioni tutto.

#include <fstream>

//using namespace std;

int count_min_swap(int a[], int const n)
{
	int const N = n - 1;
	int sw = 0;
	for (int i = 0; i != N; ++i)
	{
		int j = a[i]-1;
		a[i] = i + 1;
		int m = 0;
		while (j != i)
		{
			++m;
			int const k = j;
			j = a[j]-1;
			a[k] = k+1;
		}
		sw += m;
	}
	return sw;
}

int main()
{
	std::ifstream in("input.txt");
	std::ofstream out("output.txt");
	// dovresti controllare se i file sono stati aperti correttamente

	int n;
	in >> n;
	// il valore di n inserito in input.txt ha senso?

	int *a = new int[n];

	// non correggo ma dovresti controllare che ci siano effettivamente n elementi
	// e che siano nella forma corretta.
	for (int i = 0; i != n; ++i)
		in >> a[i];

	int const sw = count_min_swap(a, n);
	out << sw << std::endl;

	delete[] a;
	return 0;
}

[Giova411]

Sì Vic era esattamente quello che volevo fare!!!
Grazie.

Non si puo' fare senza un while interno ad un for, vero?

[vict85]

Senza un doppio ciclo non penso. Insomma per ogni elemento devi seguire il ciclo. Ma si dovrebbero fare analisi di tipo algebrico. Prendo un block notes e faccio un po' di conti.

[vict85]

OK, ci ho ragionato e ho fatto un piccolo test a mano. Immagino che il tuo procedimento derivasse dal fatto che:
\(\displaystyle (abc\dotsm f)(ab) = (b)(a c\dotsm f) \)
che non è altro di quello che facendo lo swap. È evidente che in questo modo si riducono i cicli. L'idea era buona e mi scuso per avere frainteso il tuo codice. Purtroppo il procedimento è incompleto.

Il problema è che proseguendo da \(1\) ad \(n\) non tutti gli elementi vengono riordinati.

Il mio esempio a mano conteneva il ciclo \((1\,5\,10\,7\,9\,6\,8\,4)\). Proseguendo si ha
\((1\,5\,10\,7\,9\,6\,8\,4)(1\,5) = (5)(1\,10\,7\,9\,6\,8\,4) \)
\((4\,1\,10\,7\,9\,6\,8)(1\,4) = (1)(4\,10\,7\,9\,6\,8) \)
\((6\,8\,4\,10\,7\,9)(6\,8) = (8)(6\,4\,10\,7\,9) \)
qui comincia a comparire il problema: il ciclo contiene (6\,4\,dotsm) ma \(6\) e \(4\) sono stati superati dal contatore del ciclo.
\((7\,9\,6\,4\,10)(7\,9) = (9)(7\,6\,4\,10) \)
nuovamente lo stesso problema
\((10\,7\,9\,6\,4)(7\,10) = (7)(10\,6\,4) \)
e come vedi il ciclo non è stato completamente eliminato. Per concludere è necessario quindi un while all'interno di quel for.

Ma questa versione, basata sul tuo ragionamento, è un po' più raffinata della prima versione:

#include <algorithm> // per std::swap
#include <fstream>

//using namespace std;

int count_min_swap1(int a[], int const n)
{
	int const N = n - 1;
	int sw = 0;
	for (int i = 0; i != N; ++i)
	{
		int j = a[i]-1;
		a[i] = i + 1;
		int m = 0;
		while (j != i)
		{
			++m;
			int const k = j;
			j = a[j]-1;
			a[k] = k+1;
		}
		sw += m;
	}
	return sw;
}


int count_min_swap2(int a[], int const n)
{
	int sw = 0;
	for (int i = 0; i != n; ++i)
	{
		if (a[i] != (i + 1))
		{
			++sw;
			int const j = a[i] - 1;
			std::swap(a[i], a[j]);
		}
		while (a[i] < (i + 1))
		{
			++sw;
			int const j = a[i] - 1;
			std::swap(a[i], a[j]);
		}
	}
	return sw;
}

int main()
{
	std::ifstream in("input.txt");
	std::ofstream out("output.txt");
	// dovresti controllare se i file sono stati aperti correttamente

	int n;
	in >> n;
	// il valore di n inserito in input.txt ha senso?

	int *a = new int[n];

	// non correggo ma dovresti controllare che ci siano effettivamente n elementi
	// e che siano nella forma corretta.
	for (int i = 0; i != n; ++i)
		in >> a[i];

	int *b = new int[n];
	for (int i = 0; i != n; ++i)
	{
		b[i] = a[i];
	}

	int const sw1 = count_min_swap1(a, n);
	int const sw2 = count_min_swap2(b, n);
	out << sw1 << " " << sw2 << std::endl;

	delete[] a;
	delete[] b;
	return 0;
}

[Giova411]

Non ho parole!
Grazie davvero!!!!!!
Grazie Mille!!!!