[JAVA] - permutazioni

[tigerjack89]

Ciao ragazzi.
Sto ancora cercando di capire fino in fondo gli array e i vettori.
In questo esercizio devo creare una semplice classe che mi dia la permutazione casuale di n numeri, senza che ve ne siano due uguali.

Ecco la mia classe

 
import java.util.Random;

public class Permutation 
{
	public Permutation(int aRange)
	{
		numbers = new int[aRange];
	}
	
	public int[] nextPermutation()
	{
		//Creo una classe con la stessa lungezza di numbers riempita di numeri da 1 a aRange
		int[] sortedNumbers = new int[numbers.length];
		for (int i=0; i < sortedNumbers.length; i++)
			sortedNumbers[i] = i+1;
		
		Random generator = new Random();
		
		int tempRange = numbers.length;
		
		for(int i = 0; i < numbers.length; i++)
		{
			int c = generator.nextInt(tempRange);
			System.arraycopy(sortedNumbers, c, numbers, i, 1);
			System.arraycopy(sortedNumbers, c+1, sortedNumbers, c, tempRange - c - 1);
			tempRange--;
		}
		
		return numbers;
	}
	
	private int[] numbers;
}

Tuttavia c'è qualcosa di sbagliato in questa classe...il problema è che non riesco a capire cosa!!
Ho provato ad eseguire anche manualmente il ciclo for...dovrebbe trovarsi, ma così non è.
Qualcuno potrebbe aiutarmi a capire dov'è l'errore??

Grazie infinite a tutti!

gl

[VincenzoTheBest]

Originariamente inviato da tigerjack89
Ciao ragazzi.
Sto ancora cercando di capire fino in fondo gli array e i vettori.
In questo esercizio devo creare una semplice classe che mi dia la permutazione casuale di n numeri, senza che ve ne siano due uguali.

Ecco la mia classe

 
import java.util.Random;

public class Permutation 
{
	public Permutation(int aRange)
	{
		numbers = new int[aRange];
	}
	
	public int[] nextPermutation()
	{
		//Creo una classe con la stessa lungezza di numbers riempita di numeri da 1 a aRange
		int[] sortedNumbers = new int[numbers.length];
		for (int i=0; i < sortedNumbers.length; i++)
			sortedNumbers[i] = i+1;
		
		Random generator = new Random();
		
		int tempRange = numbers.length;
		
		for(int i = 0; i < numbers.length; i++)
		{
			int c = generator.nextInt(tempRange);
			System.arraycopy(sortedNumbers, c, numbers, i, 1);
			System.arraycopy(sortedNumbers, c+1, sortedNumbers, c, tempRange - c - 1);
			tempRange--;
		}
		
		return numbers;
	}
	
	private int[] numbers;
}

Tuttavia c'è qualcosa di sbagliato in questa classe...il problema è che non riesco a capire cosa!!
Ho provato ad eseguire anche manualmente il ciclo for...dovrebbe trovarsi, ma così non è.
Qualcuno potrebbe aiutarmi a capire dov'è l'errore??

Grazie infinite a tutti!

gl

Perchè usi arrayCopy quando invece ti basta un semplice scambio?
In pratica devi scambiare l'elemento nella cella i con quello in cella c.

Inoltre tempRange deve essere pari a numbers.length - 1 e non capisco perchè lo decrementi.

[tigerjack89]

Originariamente inviato da VincenzoTheBest
Perchè usi arrayCopy quando invece ti basta un semplice scambio?
In pratica devi scambiare l'elemento nella cella i con quello in cella c.

Però se faccio qualcosa come numbers[i] = sortedNumbers[c] copio solo il riferimento a quella cella di quell'array...o sbaglio?

Inoltre tempRange deve essere pari a numbers.length - 1 e non capisco perchè lo decrementi.

Perchè i numeri non devono ripetersi. Se lascio tempRange invariato, il generatore di numeri casuali mi darà sempre un numero tra 0 e range.

Facendo l'esempio di aRange = 10, il procedimento a cui ho pensato io è:
assegno a tempRange il valore 10;
creo un vettore di numeri ordinati da 1 a 10 (sorted numbers);
genero un numero casuale c compreso tra 0 e 9;
copio l'elemento sortedNumbers[c] in numbers[0];
rimuovo l'elemento c da sortedNumbers spostando indietro tutti i valori successivi;
//in questo modo, per esempio, se c =3, avrò sortedNumbers[] = {1 2 3 5 6 7 8 9 10 10}
decremento tempRange, in quanto ora voglio un numero casuale tra 0 ed 8, proprio perchè l'ultimo numero non mi serve più;
ripeto tutto.

Il ragionamento dovrebbe filare, no?

[VincenzoTheBest]

Originariamente inviato da tigerjack89
Però se faccio qualcosa come numbers[i] = sortedNumbers[c] copio solo il riferimento a quella cella di quell'array...o sbaglio?

Di certo lo scambio non si fa in questo modo! Devi usare una variabile temporanea per poter favorire lo scambio. E poi perchè usare un secondo array?

Originariamente inviato da tigerjack89
Perchè i numeri non devono ripetersi. Se lascio tempRange invariato, il generatore di numeri casuali mi darà sempre un numero tra 0 e range.

Ti sbagli. Scambiando gli elementi non causerai mai una ripetizione, in quanto non ne aggiungi dei nuovi.

[tigerjack89]

Originariamente inviato da VincenzoTheBest
Di certo lo scambio non si fa in questo modo! Devi usare una variabile temporanea per poter favorire lo scambio. E poi perchè usare un secondo array?

Ti sbagli. Scambiando gli elementi non causerai mai una ripetizione, in quanto non ne aggiungi dei nuovi.

Non riesco a seguirti. l'array numbers all'inizio è vuoto, o meglio riempito di 0.

Quello che faccio è prendere un numero a caso dall'array ordinato sortedNumbers e aggiungerlo nell'array numbers.

Dove toppo?

[VincenzoTheBest]

Originariamente inviato da tigerjack89
Non riesco a seguirti. l'array numbers all'inizio è vuoto, o meglio riempito di 0.

Quello che faccio è prendere un numero a caso dall'array ordinato sortedNumbers e aggiungerlo nell'array numbers.

Secondo me dovresti inizializzare numbers come fai con sortedNumbers e fare gli scambi all'interno di numbers stesso. Così facendo ti semplifichi il lavoro.

[satifal]

Indipendentemente dalla correttezza logica dell'algoritmo e dalle possibili migliorie, ho cercato di sistemare il tuo codice:

public int[] nextPermutation() {
	List<Integer> sortedNumbers = new ArrayList<Integer>();
	for (int i = 0; i < numbers.length; i++) {
		sortedNumbers.add(new Integer(i + 1));
	}
		
	Random generator = new Random();
	int tempRange = numbers.length;
		
	for(int i = 0; i < numbers.length; i++) {
		int c = generator.nextInt(tempRange--);
		numbers[i] = sortedNumbers.remove(c);
	}

	return numbers;
}

[tigerjack89]

Originariamente inviato da VincenzoTheBest
Secondo me dovresti inizializzare numbers come fai con sortedNumbers e fare gli scambi all'interno di numbers stesso. Così facendo ti semplifichi il lavoro.

Non sarebbe più complicato? Dovrei controllare ciclicamente se ci sono numeri uguali...

Indipendentemente dalla correttezza logica dell'algoritmo e dalle possibili migliorie, ho cercato di sistemare il tuo codice:

Ti ringrazio per il suggerimento, ma nemmeno così si trova ...dovrei ottenere dei numeri da 1 a n senza che si ripetono...per esempio se n = 10, una soluzione potrebbe essere

4 7 1 9 10 2 5 3 8 6

[VincenzoTheBest]

Originariamente inviato da tigerjack89
Non sarebbe più complicato? Dovrei controllare ciclicamente se ci sono numeri uguali...

No, affatto.

[satifal]

Originariamente inviato da tigerjack89
...
Ti ringrazio per il suggerimento, ma nemmeno così si trova ...dovrei ottenere dei numeri da 1 a n senza che si ripetono...per esempio se n = 10, una soluzione potrebbe essere

4 7 1 9 10 2 5 3 8 6

Scusa, ma hai provato il metodo da me postato? Io l'ho testato ed i numeri non si ripetono affatto.