# why is a naturally ordered set generated at 9 but not 10 digits

Presuming that the problem indicated above is due to the test app and not due specifically to method generateRandomDigits().

When NUMBER_OF_DIGITS_TO_ORDER is <= 9, I do get a naturally ordered sets (just trying to prove that it is possible), but when it is set to 10 I never get such a set and I've run it many times. Why?

I am more than open to suggested improvements to method generateRandomDigits() - it seems a bit convoluted.

-
because it starts from zero ;) – Yusubov Jul 28 '12 at 21:51
I don't do Java. But on a quick look, I can see that you have a line like: naturalOrderedNums[i] = Integer.toString(i).charAt(0); This line is executed inside a loop from zero to 9, if you go beyond 9 the LHS array will start duplicating data. – NoChance Jul 28 '12 at 22:54

## 2 Answers

The real solution is to comment your code even when it is a toy. I dug this out of the cellar (the random number method) and forgot I was taking advantage of the default value of char and the behavior of a for-loop in the `i < whatever` when `whatever` is 0.

As for the code solution, I think the comments I added explain the solution:

``````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;
}
``````

Now, I get ordered nums, on occasion.

edit:

Put whole app in instead of just method. Now has logging as per gnat. Hits are higher than I expected but good enough for now. Incidentally, I've run it many times and I no longer get the error noted in link above; don't have a clue what caused the change.

``````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++;
}
}
``````
-

You need to try harder - in the sense, more attempts are needed to increase chances to get 10 digits set.

Regarding the program, it would greatly benefit from logging improvement. The way it is done now, program output just lacks an information that would help to identify what is going on there.

If you add few lines to the `main` method to count the number of found arrays and re-run the program with improved logging, you will likely get a much better feeling of where it all is coming at as the value `NUMBER_OF_DIGITS_TO_ORDER` increases. Consider logging like this:

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

Let's start with "small" case to see how things go. Look, program drops random (unique) digits, say from 0 to 2 into 3628800 arrays (`NUMBER_OF_CHAR_ARRAYS`) - making essentially 3628800 attempts and checking how much times it gets get `0,1,2`. We sure get it a lot.

• Thing is, there are only `3*2=6` possible combinations that could get into our randomly generated array - first place can be occupied by any of three digits, second place can be occupied by any of two remaining digits; as for the third place, we don't have any options here as long as first and second places are occupied. Given this, we can expect to get about `3628800/6=600000`.

Okay, now let's do the same to digits 0 to 6. Number of attempts remains the same, 3628800, but array we want is getting harder to randomly generate because it's longer: `0,1,2,3,4,5,6`. For array of this length, there are `6*5*4*3*2` possible combinations - and our chances to get it with same 3628800 are `6*5*4=120`, more than hundred times lower than were with array `0,1,2`. And it only will get worse as the length of array increases.

Finally, let's try "win a lottery", to get `0,1,2,3,4,5,6,7,8,9` - all the ten digits perfectly lined up - with the same number of attempts that brought us so much luck with 3 digits, noticeably less luck with 6 digits and pretty shaky luck with 9 digits? "Pretty shaky" - in my trial runs, I was getting nine digits 2 to 5 times; getting yet another digit "in the line" is likely to be 10 times harder than that.

• There are whopping `10*9*8*7*6*5*4*3*2` combinations possible with 10 unique digits - this makes our chances `10*9*8*7~=5000`, about five thousand times worse that what we've got for our number of attempts for 6-digit ordered set.

Expecting 10 digits ordered set to show is pretty much like buying hundred lottery tickets and wondering

## why didn't I win jackpot?

-
+1, you are the one to talk to for before the trip to Vegas :) – NoChance Jul 29 '12 at 3:02
@gnat - "need to log better", your right. that would help. Thanks for the input! – yas Jul 29 '12 at 17:17
This answer is a little too snarky for my tastes. Can you present much of the same information in a more professional manner? – Bryan Oakley Jul 30 '12 at 11:12
@BryanOakley sure why not - revised wording – gnat Jul 30 '12 at 11:42