L'altro modo per risolvere il problema sarebbe direttamente utilizzare un numero random che funga come indice di un array ma dopo aver "utilizzato" l'elemento di indice i il numero random non deve più ricomparire... non so se mi spiego!
Se l'array è di dimensioni note e fissate a priori ti basta affiancargli una ArrayList di pari dimensioni o un array, che serve solo per tenere traccia degli indici non ancora utilizzati (deve ovviamente essere inizializzato con tutti gli indici presenti nel primo array).
Ogni volta che ti appresti a generare un indice random devi prima:
- controllare che l'ArrayList degli indici possibili non sia vuoto;
- eseguire la generazione dell'indice random tenendo conto degli indici disponibili;
- rimuovere dagli indici disponibili l'indice random appena generato;
- infine prelevare il tuo elemento nel primo array.
Ti allego una classe dove ho usato un sistema simile nell'implementazione di un algoritmo di backtracking per generare schemi Sudoku 9x9.
Nel codice la parte che ti può dare spunti è all'interno del metodo generateSchema() e alle chiamate a metodi privati della classe che esegue (in particolare il metodo nextRandom()).
Ciao :)
package fbaro.sudoku.scheme;
import java.util.ArrayList;
import java.util.Random;
/**
* build up a new Sudoku schema using a backtracking algorithm tecnique while filling a
* cell one at time with a random generated number (whoes values are in the dominio).
* If the generated value is correct (no duplicate value in same region, column and row)
* than it is stored, otherwise discard it and try with a new one.
* If all values for current cell are invalid step back.
*
* @author francesco
*/
public class SudokuGenerator
{
private int[] gridValues;
private ArrayList<ArrayList<Integer>> available;
// Algorithm Statistics
private int loops; // counter for tracking total loops in the algorithm
private int stepsBack; // counter for tracking how many "steps back" has been performed
public SudokuGenerator()
{
gridValues = new int[81]; // 81 cells
available = new ArrayList<ArrayList<Integer>>(); // 9 values for each cell
for(int i = 0; i < 81; i++)
{
ArrayList<Integer> numberset = new ArrayList<Integer>(9);
for(int k = 1; k <= 9; k++)
{
numberset.add(new Integer(k));
}
available.add(numberset);
}
}
/**
* generate a new, valid, Sudoku schema.
*/
public void generateSchema()
{
int cellIndex = 0;
do
{
loops++;
if (notOutOfNumbers(cellIndex))
{
int randomIndex = nextRandom(cellIndex);
int value = available.get(cellIndex).get(randomIndex);
if (isValid(value, cellIndex))
{
gridValues[cellIndex] = value; // store value
available.get(cellIndex).remove(randomIndex); // remove used num
cellIndex++; // step foward!
continue;
}
else
{
available.get(cellIndex).remove(randomIndex); // invalid number
continue;
}
}
else
{
for(int i = 1; i <= 9; i++)
available.get(cellIndex).add(new Integer(i)); // replenish numbers
gridValues[cellIndex] = 0; // reset value
cellIndex--; // step back!
stepsBack++;
continue;
}
}
while(cellIndex < 81);
}
private boolean notOutOfNumbers(final int cellIndex)
{
return available.get(cellIndex).size() > 0;
}
private int nextRandom(final int cellIndex)
{
ArrayList<Integer> subset = available.get(cellIndex);
int limit = subset.size();
Random rand = new Random();
int index = rand.nextInt(limit); // between 0(inclusive) and limit(exclusive)
return index;
}
/**
* check if last generated value is not a duplicate in the region, row and colum.
*/
private boolean isValid(int randomVal, final int cellIndex)
{
boolean valid = true;
// check same row
int rowIndex[] = indexesOfRow(findRow(cellIndex));
for(int i = 0; i < 9; i++)
{
if (rowIndex[i] != cellIndex) // same cell, skip testing
{
if (gridValues[rowIndex[i]] == randomVal) // value alredy present
{
valid = false;
break;
}
}
}
// check same column
int colIndex[] = indexesOfColumn(findColumn(cellIndex));
for(int i = 0; i < 9; i++)
{
if (colIndex[i] != cellIndex)
{
if (gridValues[colIndex[i]] == randomVal)
{
valid = false;
break;
}
}
}
// check same region
int regionIndexes[] = indexesOfRegion(findRegion(cellIndex));
for(int i = 0; i < 9; i++)
{
if (regionIndexes[i] != cellIndex)
{
if (gridValues[regionIndexes[i]] == randomVal)
{
valid = false;
break;
}
}
}
return valid;
}
private int findRow(final int index)
{
double division = Math.ceil((index + 1.0) / 9.0);
return (int) division;
}
private int findColumn(final int index)
{
int modulo = (index+1) % 9;
modulo = (modulo != 0) ? modulo : 9;
return modulo;
}
private int findRegion(final int index)
{
int row = findRow(index);
int column = findColumn(index);
int sumRow;
if (row <= 3)
sumRow = 0;
else
if (row <= 6)
sumRow = 3;
else
sumRow = 6;
int sumColumn;
if (column <= 3)
sumColumn = 1;
else
if (column <= 6)
sumColumn = 2;
else
sumColumn = 3;
return sumRow + sumColumn;
}
private int[] indexesOfRow(int row)
{
int[] indexArray = new int[9];
int maxIndex = (row * 9) - 1;
int minIndex = maxIndex - 8;
for(int i = 0; i < 9; i++)
{
indexArray[i] = minIndex++;
}
return indexArray;
}
private int[] indexesOfColumn(int column)
{
int[] indexArray = new int[9];
for(int i = 0; i < 9; i++)
{
indexArray[i] = (column + 9*i) - 1;
}
return indexArray;
}
private int[] indexesOfRegion(int region)
{
int[] indexArray = new int[9];
int startingValue;
if (region == 1)
startingValue = 0;
else
if (region == 2)
startingValue = 3;
else
if (region == 3)
startingValue = 6;
else
if (region == 4)
startingValue = 27;
else
if (region == 5)
startingValue = 30;
else
if (region == 6)
startingValue = 33;
else
if (region == 7)
startingValue = 54;
else
if (region == 8)
startingValue = 57;
else
startingValue = 60;
int increment = 1;
int sum = 0;
for(int i = 1; i <= 9; i++)
{
if (i < 4)
sum = 0;
else
if (i > 3 && i < 7)
sum = 9;
else
if (i > 6)
sum = 18;
indexArray[i-1] = startingValue + (increment-1) + sum;
if (increment%3 == 0)
increment = 0;
increment++;
}
return indexArray;
}
public int getLoops()
{
return loops;
}
public int getStepsBack()
{
return stepsBack;
}
public int[] getValues()
{
return gridValues;
}
/**
* used fo testing the class
*/
public static void main(String[] argv)
{
// SudokuGenerator generator = new SudokuGenerator();
// long timeStart = System.currentTimeMillis();
// generator.generateSchema();
// long timeEnd = System.currentTimeMillis();
//
// int[] alpha = generator.gridValues;
// int c = 0;
// for(int i = 0; i < alpha.length; i++)
// {
// c++;
// System.out.print(""+ alpha[i] + ",");
// if (c%9 == 0)
// System.out.println("");
//
// }
// System.out.println("\ngenerated " + c + " values.");
// System.out.println("total loops: " + generator.getLoops());
// System.out.println("steps back: " + generator.getStepsBack());
// System.out.println("schema generated in " + (timeEnd-timeStart) + " milliseconds");
int testTimes = 100000;
int totalLoops = 0;
int totalStepsBack = 0;
long timeStart = System.currentTimeMillis();
for(int i = 0; i < testTimes; i++)
{
SudokuGenerator generator = new SudokuGenerator();
generator.generateSchema();
totalLoops += generator.getLoops();
totalStepsBack += generator.getStepsBack();
}
long timeEnd = System.currentTimeMillis();
System.out.println("average loops: " + totalLoops/testTimes);
System.out.println("average steps back: " + totalStepsBack/testTimes);
System.out.println("average generation time " + (timeEnd-timeStart)/testTimes + " milliseconds");
System.out.println("total time " + (timeEnd-timeStart) + " milliseconds, for running " +
"algorithm " + testTimes + " times.");
}
}