[JAVA] array/random

[DevilMalak]

salve a tutti c'è un problema che posso risolvere in due modi....
un modo è quello di avere un array di numeri random da 0 a n che però devono essere 2 per ognuno.. né di più né di meno. (esempio: un array con 36locazioni deve avere tutti i numeri da 0 a 17, due volte, mescolati casualmente)

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!

Le soluzioni che ho provato non funzionano perché avrei la necessità di tornare all'inizio del ciclo senza che l'indice incrementi nel caso l'elemento random sia già stato utilizzato! Nel primo caso comunque pensavo anche semplicemente di creare un array ordinato tipo 0,0,1,1,2,3,3 e così via ma non saprei come mescolarlo senza incappare nel problema del numero generato casualmente che può "tornare"...

Ogni suggerimento è ben accetto, grazie

[banryu79]

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.");
    }
}

[cionci]

Mi pare di capire che tu voglia mescolare un vettore. Ti descrivo la situazione più semplice (con l'ArrayList è perfetto).
Hai due ArrayList, uno sorgente ed uno destinazione. Sorgente è pieno e destinazione è vuoto. Fino a quando il sorgente non è vuoto:
- estrai un numero intero fra 0 e la dimensione dell'ArrayList sorgente - 1
- elimini l'elemento corrispondente all'indice estratto con il metodo remove (l'arraylist viene compattato) ed inserisci l'elemento estratto in fondo all'arraylist di destinazione

[DevilMalak]

più tardi guarderò meglio, intanto ti ringrazio!

[cionci]

Ritiro tutto:

Collection.shuffle(arraylist);

[DevilMalak]

grazie mille a entrambi, alla fine ho utilizzato Collections.shuffle(List) come consigliato da cionci perché mi è stato molto più semplice avendo già preparato il resto ma ringrazio ugualmente entrambi...

Ciao!