perché è un set ordinato naturalmente generato a 9 ma non a 10 cifre

0

codice trovato su link

Supponendo che il problema sopra indicato sia dovuto all'app di test e non dovuta specificamente al metodo generateRandomDigits ().

Quando NUMBER_OF_DIGITS_TO_ORDER è < = 9, ottengo un set ordinato naturalmente (solo cercando di dimostrare che è possibile), ma quando è impostato su 10 non ottengo mai un set simile e l'ho eseguito molte volte . Perché?

Sono più che aperto ai miglioramenti suggeriti al metodo generateRandomDigits () - sembra un po 'contorto.

    
posta yas 28.07.2012 - 23:07
fonte

2 risposte

1

La vera soluzione è commentare il tuo codice anche quando è un giocattolo. Ho scavato questo fuori dalla cantina (il metodo del numero casuale) e ho dimenticato che stavo sfruttando il valore predefinito di char e il comportamento di un ciclo for in i < whatever quando whatever è 0.

Per quanto riguarda la soluzione del codice, penso che i commenti che ho aggiunto spieghino la soluzione:

package numgen;

import java.text.DecimalFormat;
import java.text.Format;
import java.util.ArrayList;
import java.util.Random;
import javax.swing.text.NumberFormatter;

public class NumGen {

private static char[] naturalOrderedNums = null;

//change value as desired for any given run
private static final int NUMBER_OF_DIGITS_TO_ORDER = 10;//must be <= 10

//change value as desired for any given run
private static final int TRIALS = 10;

//???????
//should create a number of arrays that allows for each
//possible permutation - hence: 3628800
//???????
//since 10 is max number of digits, 10! will suffice for all <= 10
private static final int NUMBER_OF_CHAR_ARRAYS = 3628800;// 10! = 3628800

private static int attempts = NUMBER_OF_CHAR_ARRAYS * TRIALS;

private static int totalHits = 0;

private static double totalPercentSuccess = 0;

//i already know it is within 8 decimal places, so good enough
private static DecimalFormat df = new DecimalFormat("#.########");

/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
    loadNaturalOrderedArray();
    double trialPercentSuccess;
    for (int i = 0; i < TRIALS; i++) {
        int trialHits = 0;
        ArrayList<char[]> listOfArrays = new ArrayList<>(NUMBER_OF_CHAR_ARRAYS);
        for (int j = 0; j < NUMBER_OF_CHAR_ARRAYS; j++) {
            listOfArrays.add(j, generateRandomDigits());
        }
        for (int j = 0; j < NUMBER_OF_CHAR_ARRAYS; j++) {
            char[] current = listOfArrays.get(j);
            if (isNaturalOrdered(current)) {
//                    printNaturalOrdered(current);//used only for debug - just want to see it sometimes
                totalHits++;
                trialHits++;
            }
            }
        trialPercentSuccess = ((double) trialHits / (double) NUMBER_OF_CHAR_ARRAYS) * 100;
        System.out.println("trialHits = " + trialHits);
        System.out.println("trialPercentSuccess = " + df.format(trialPercentSuccess));

        System.out.println("trial " + i + " is done");
        System.out.println("--------------------------------\n");
    }
    totalPercentSuccess = ((double) totalHits / (double) attempts) * 100;
    System.out.println("totalHits = " + totalHits);
    double hitsPerTrial = (double) totalHits / (double) TRIALS;
    System.out.println("hitsPerTrial = " + hitsPerTrial);
    System.out.println("totalPercentSuccess = " + df.format(totalPercentSuccess));
    System.out.println("DONE");
}

private static void loadNaturalOrderedArray() {
    naturalOrderedNums = new char[NUMBER_OF_DIGITS_TO_ORDER];
    for (int i = 0; i < NUMBER_OF_DIGITS_TO_ORDER; i++) {
        naturalOrderedNums[i] = Integer.toString(i).charAt(0);
    }
}

private static boolean areEqual(char[] current, char[] other) {
    int targetSize = NUMBER_OF_DIGITS_TO_ORDER;
    boolean areEqual = true;
    for (int i = 0; i < targetSize; i++) {
        if (current[i] != other[i]) {
            areEqual = false;
            break;
        }
    }
    return areEqual;
}

private static void printNaturalOrdered(char[] current) {
    int size = current.length;
    for (int j = 0; j < size; j++) {
        System.out.print(current[j] + " ");
    }
    System.out.println("----------------------------- is natural ordered\n");
}

private static boolean isNaturalOrdered(char[] current) {
    return areEqual(current, naturalOrderedNums);
}

private static char[] generateRandomDigits() {
    int targetSize = NUMBER_OF_DIGITS_TO_ORDER;
    int targetSizeMinusOne = targetSize - 1;
    StringBuilder sb = new StringBuilder(targetSize);
    Random random = new Random();
    char[] chars;
    boolean isUnique;
    while (sb.length() < targetSize) {
        //random.nextInt() WILL NEVER GIVE A NUMBER BEGINING WITH 0
        chars = Integer.toString(Math.abs(random.nextInt())).toCharArray();
        int numberOfChars = chars.length;
        //BY STARTING WITH i = 1 INSTEAD OF i = 0, THE FIRST CHAR IS ALWAYS THROWN OUT
        //THAT MATTERS SINCE, AS NOTED ABOVE: //random.nextInt() WILL NEVER GIVE A NUMBER BEGINING WITH 0
        for (int i = 1; i < numberOfChars; i++) {//WAS i = 0
            int currentValueOfChar = Integer.parseInt(String.valueOf(chars[i]));
            if (currentValueOfChar > targetSizeMinusOne) {//WILL ALWAYS FAIL WHEN NUMBER_OF_DIGITS_TO_ORDER = 10
                continue;
            }
            isUnique = true;
            for (int j = 0; j < sb.length(); j++) {
                if (sb.charAt(j) == chars[i]) {
                    isUnique = false;
                    break;
                }
            }
            if (isUnique && sb.length() < targetSize) {
                sb.append(chars[i]);
            }
        }
    }
    char[] randomNums = new char[targetSize];
    for (int i = 0; i < targetSize; i++) {
        randomNums[i] = sb.charAt(i);
    }
    return randomNums;
}

Ora, a volte ricevo i numeri ordinati.

modifica

Metti l'intera app al posto del solo metodo. Ora registra come per gnat . I colpi sono più alti di quanto mi aspettassi, ma abbastanza buoni per ora. Per inciso, l'ho eseguito molte volte e non ricevo più l'errore annotato nel link sopra; non ho idea di cosa abbia causato la modifica.

package numgen;

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Random;

public class NumGen {

    private static char[] naturalOrderedNums = null;

    //change value as desired for any given run
    //reasonably quick results at <= 8
    private static final int NUMBER_OF_DIGITS_TO_ORDER = 8;//must be: 0 >= NUMBER_OF_DIGITS_TO_ORDER <= 10

    //change value as desired for any given run
    private static final int TRIALS = 2;

    private static int numberOfCharArrays;

    private static int attempts;

    private static int totalHits = 0;

    private static double totalPercentSuccess = 0;

    private static ArrayList<char[]> listOfArrays = null;

    //i already know it is within 8 decimal places, so good enough
    private static DecimalFormat df = new DecimalFormat("#.########");

    private static ArrayList<DuplicateSequence> dupSequenceList = new ArrayList<>();

    /**
    * @param args the command line arguments
    */
    public static void main(String[] args) {
        init();
        runTrials();
        printNaturalOrderSummaryData();
    }

    private static void init() {
        loadNaturalOrderedArray();
        calculateNumberOfCharArrays();
        calculateAttempts();
    }

    private static void runTrials() {
        for (int i = 0; i < TRIALS; i++) {
            loadListOfArrays();
            testForNaturalOrder(i);
            testForDuplication();
        }
    }

    private static void printNaturalOrderSummaryData() {
        totalPercentSuccess = ((double) totalHits / (double) attempts) * 100;
        System.out.println("----------------------------------------------------------");
        System.out.println("\nDATA FOR OCCURANCE OF NATURAL ORDERING ACROSS ALL TRIALS:\n");
        System.out.println("\ttotalHits = " + totalHits);
        double hitsPerTrial = (double) totalHits / (double) TRIALS;
        System.out.println("\thitsPerTrial = " + hitsPerTrial);
        System.out.println("\ttotalPercentSuccess = " + df.format(totalPercentSuccess));
        System.out.println("\n\n>>>>>>>>>>>>>>>>>>>>>>>>>> DONE <<<<<<<<<<<<<<<<<<<<<<<<<<");
    }

    private static void loadListOfArrays() {
        listOfArrays = new ArrayList<>(numberOfCharArrays);
        for (int j = 0; j < numberOfCharArrays; j++) {
            listOfArrays.add(j, generateRandomDigits());
        }
    }

    private static void calculateNumberOfCharArrays() {
        int value = 1;
        for (int i = 2; i < (NUMBER_OF_DIGITS_TO_ORDER + 1); i++) {
            value *= i;
        }
        numberOfCharArrays = value;
    }

    private static void calculateAttempts() {
        attempts = numberOfCharArrays * TRIALS;
    }

    private static void testForNaturalOrder(int trialNum) {
        int trialHits = 0;
        double trialPercentSuccess;
        for (int j = 0; j < numberOfCharArrays; j++) {
            char[] current = listOfArrays.get(j);
            if (isNaturalOrdered(current)) {
                totalHits++;
                trialHits++;
            }
        }
        trialPercentSuccess = ((double) trialHits / (double) numberOfCharArrays) * 100;
        System.out.println("----------------------------------------------------------\tTrial " + trialNum + " is done");
        System.out.println("\nTRIAL OCCURANCES OF NATURAL ORDERING:\n");
        System.out.println("\ttrialHits = " + trialHits);
        System.out.println("\ttrialPercentSuccess = " + df.format(trialPercentSuccess));
    }

    private static void updateDupSequenceList(char[] current) {
        int size = dupSequenceList.size();
        boolean isListed = false;
        DuplicateSequence currentDupSeq;
        for (int j = 0; j < size; j++) {
            currentDupSeq = dupSequenceList.get(j);
            char[] dupSeqArray = currentDupSeq.getSequence();
            if (areEqual(current, dupSeqArray)) {
                isListed = true;
                currentDupSeq.incrementCount();
                break;
            }
        }
        if (!isListed) {
            dupSequenceList.add(new DuplicateSequence(current));
        }
    }

    private static void testForDuplication() {
        //create copy because of copy.remove(j); below
        @SuppressWarnings("unchecked")
        ArrayList<char[]> copy = (ArrayList<char[]>) listOfArrays.clone();
        //(copy.size() - 1) because the last item has nothing after it to compare to
        for (int i = 0; i < (copy.size() - 1); i++) {
            char[] current = copy.get(i);

            //j = (i + 1) because j = i or j = 0 would test the current against itself
            for (int j = (i + 1); j < copy.size(); j++) {
                char[] other = copy.get(j);
                if (areEqual(current, other)) {
                    updateDupSequenceList(current);
                    copy.remove(j);//speeds things up - why let it become item at i and check it again?

                    //j-- because copy.remove(j) shifts items, then next unchecked item is now at current j
                    //and would not be checked without decrement.
                    j--;
                }
            }
        }
        System.out.println("\n\nTRIAL DUPLICATION DATA:");
        int totalInstancesOfduplicateNumbers = 0;
        int numberOfSequencesWithDuplicates = dupSequenceList.size();
        System.out.println("");

        for (int i = 0; i < numberOfSequencesWithDuplicates; i++) {
            totalInstancesOfduplicateNumbers += dupSequenceList.get(i).getCount();
            //System.out.println("\tsequence = " + String.valueOf(dupSequenceList.get(i).getSequence()));
            //System.out.println("\tduplicate count for this sequence = " + dupSequenceList.get(i).getCount());
            //System.out.println("\t-------------------------------------\n");
        }
        System.out.println("\tnumberOfSequencesWithDuplicates = " + numberOfSequencesWithDuplicates);

        //because count in DuplicateSequence is the count of duplicates of a given sequence
        //and does not count the original/reference sequence occurance itself
        totalInstancesOfduplicateNumbers += numberOfSequencesWithDuplicates;
        System.out.println("\ttotalInstancesOfduplicateNumbers = " + totalInstancesOfduplicateNumbers);
        //note: duplications seem high
        double percentDuplication = ((double) totalInstancesOfduplicateNumbers / (double) attempts) * 100;
        System.out.println("\tpercentDuplication = " + new DecimalFormat("#.##").format(percentDuplication));
        System.out.println("\n\n");

    }

    private static void loadNaturalOrderedArray() {
        naturalOrderedNums = new char[NUMBER_OF_DIGITS_TO_ORDER];
        for (int i = 0; i < NUMBER_OF_DIGITS_TO_ORDER; i++) {
            naturalOrderedNums[i] = Integer.toString(i).charAt(0);
        }
    }

    private static boolean areEqual(char[] current, char[] other) {
        int targetSize = NUMBER_OF_DIGITS_TO_ORDER;
        boolean areEqual = true;
        for (int i = 0; i < targetSize; i++) {
            if (current[i] != other[i]) {
                areEqual = false;
                break;
            }
        }
        return areEqual;
    }

    private static void printNaturalOrdered(char[] current) {
        int size = current.length;
        for (int j = 0; j < size; j++) {
            System.out.print(current[j] + " ");
        }
        System.out.println("----------------------------- is natural ordered\n");
    }

    private static boolean isNaturalOrdered(char[] current) {
        return areEqual(current, naturalOrderedNums);
    }

    private static char[] generateRandomDigits() {
        int targetSize = NUMBER_OF_DIGITS_TO_ORDER;
        int targetSizeMinusOne = targetSize - 1;
        StringBuilder sb = new StringBuilder(targetSize);
        Random random = new Random();
        char[] chars;
        boolean isUnique;
        while (sb.length() < targetSize) {
            //random.nextInt() WILL NEVER GIVE A NUMBER BEGINNING WITH 0
            //BUT IT WILL RETURN A SINGLE DIGIT AND IT CAN BE 0
            chars = Integer.toString(Math.abs(random.nextInt())).toCharArray();
            int numberOfChars = chars.length;

            char currentChar;
            //random.nextInt() SOMETIMES RETURNS A SINGLE DIGIT AND IT CAN BE 0
            //IN THAT CASE, chars[1] WOULD FAIL
            if (numberOfChars == 1) {
                currentChar = chars[0];
            } else {
                currentChar = chars[1];
            }
            int currentValueOfChar = Integer.parseInt(String.valueOf(currentChar));
            if (currentValueOfChar > targetSizeMinusOne) {//WILL ALWAYS FAIL WHEN NUMBER_OF_DIGITS_TO_ORDER = 10
                continue;
            }
            isUnique = true;
            for (int j = 0; j < sb.length(); j++) {
                if (sb.charAt(j) == currentChar) {
                    isUnique = false;
                    break;
                }
            }
            if (isUnique && sb.length() < targetSize) {
                sb.append(currentValueOfChar);
            }
        }
        char[] randomNums = new char[targetSize];
        for (int i = 0; i < targetSize; i++) {
            randomNums[i] = sb.charAt(i);
        }
        return randomNums;
    }
}

class DuplicateSequence {

    private char[] sequence = null;

    /**
    * @return the sequence
    */
    public char[] getSequence() {
        return sequence.clone();
    }

    //the number of duplications, not total occurances.
    //if one duplicate is found, count is 1 but total
    //occurances is 2. Basically total = count + 1,
    // (duplicates + referenced sequence).
    private int count = 0;

    /**
    * @return the count
    */
    public int getCount() {
        return count;
    }

    public DuplicateSequence(char[] sequence) {
        this.sequence = sequence;
        this.count = 1;
    }

    public void incrementCount() {
        this.count++;
    }
}
    
risposta data 29.07.2012 - 19:11
fonte
5

Devi provare di più: nel senso, sono necessari più tentativi per aumentare le possibilità di ottenere 10 cifre.

Per quanto riguarda il programma, notevolmente trarrà vantaggio dal miglioramento della registrazione. Il modo in cui è fatto ora, l'output del programma manca semplicemente di un'informazione che aiuterebbe a identificare ciò che sta accadendo lì.

Se aggiungi poche righe al metodo main per contare il numero di array trovati e riesegui il programma con una registrazione migliorata, probabilmente otterrai una sensazione molto migliore di dove tutto sta arrivando come valore% aumenti diNUMBER_OF_DIGITS_TO_ORDER. Considera la registrazione come segue:

public static void main(String[] args1) {
    loadNaturalOrderedArray();
    // let's count our attempts
    long numberOfChecks = 0;
    // let's count our luck
    long numberOfNaturalOrdered = 0;
    for (int i = 0; i < TRIALS; i++) {
        ArrayList<char[]> listOfArrays = new ArrayList<char[]>(NUMBER_OF_CHAR_ARRAYS);
        for (int j = 0; j < NUMBER_OF_CHAR_ARRAYS; j++) {
            listOfArrays.add(j, generateRandomDigits());
        }
        for (int j = 0; j < NUMBER_OF_CHAR_ARRAYS; j++) {
            numberOfChecks++; // count our attempts
            char[] current = listOfArrays.get(j);
            if (isNaturalOrdered(current)) {
                numberOfNaturalOrdered++; // count our luck
                //printNaturalOrdered(current); // not important
            }
        }
        System.out.println("trial " + i + " is done");
        System.out.println("--------------------------------\n");
    }
    // print our luck
    System.out.println("number of natural ordered: [" + numberOfNaturalOrdered + "]");
    // print our attempts
    System.out.println("number of checks: [" + numberOfChecks + "]");
    // btw numberOfChecks is always TRIALS * NUMBER_OF_CHAR_ARRAYS
    System.out.println("DONE");
}

Iniziamo con il caso "piccolo" per vedere come vanno le cose. Guarda, il programma rilascia cifre casuali (univoche), diciamo da 0 a 2 su 3628800 matrici ( NUMBER_OF_CHAR_ARRAYS ) - facendo sostanzialmente 3628800 tentativi e controllando quante volte ottiene 0,1,2 . Siamo sicuri di averlo preso molto.

  • Il fatto è che ci sono solo% combinazioni possibili di% co_de che potrebbero entrare nel nostro array generato casualmente - il primo posto può essere occupato da una delle tre cifre, il secondo posto può essere occupato da una delle due cifre rimanenti; per quanto riguarda il terzo posto, non abbiamo nessuna opzione finché il primo e il secondo posto sono occupati. Detto questo, possiamo per ottenere circa 3*2=6 .

Ok, ora facciamo lo stesso con le cifre da 0 a 6. Il numero di tentativi rimane lo stesso, 3628800, ma l'array che vogliamo è sempre più difficile da generare casualmente perché è più lungo: 3628800/6=600000 . Per array di questa lunghezza, esistono% combinazioni possibili di% co_de - e le nostre probabilità di ottenerlo con lo stesso 3628800 sono 0,1,2,3,4,5,6 , più di cento volte inferiori rispetto a% con array 6*5*4*3*2 . E peggiorerà solo con l'aumento della lunghezza dell'array.

Infine, proviamo "vincere una lotteria", per ottenere 6*5*4=120 - tutte e dieci le cifre perfettamente allineate - con lo stesso numero di tentativi che ci hanno portato tanta fortuna con 3 cifre, sensibilmente meno fortuna con 6 cifre e fortuna piuttosto traballante con 9 cifre? "Abbastanza traballante": durante le prove, ricevevo nove cifre da 2 a 5 volte; ottenere ancora un'altra cifra "nella linea" è probabilmente 10 volte più difficile di quella.

  • Ci sono cinque combinazioni 0,1,2 possibili con 10 cifre univoche - questo rende le nostre probabilità 0,1,2,3,4,5,6,7,8,9 , circa cinquemila volte peggio di quello che abbiamo per il nostro numero di tentativi per un set ordinato di 6 cifre.

Aspettarsi 10 cifre ordinate da mostrare è come comprare centinaia di biglietti della lotteria e chiedersi

perché non ho vinto il jackpot?

    
risposta data 29.07.2012 - 01:23
fonte

Leggi altre domande sui tag