-1

I am in a cs 2010 class. Haven't ever worked on coding before or anything of the sort. I have an okay teacher but he has a very thick accent that is hard to understand. He recently gave us a project to complete over a few days. I have been having problems getting the last part of the project done.

The project asks you to generate 10,000 random numbers between 0-9999 and arrange them in an array of 10,000 numbers without repeating any of them. As you can see, this is basically asking you to make the array put the numbers 0-9999 in an array in order of least to greatest. My problem is the non-repeating numbers. I have been working on the code for over 4 hours trying to figure out how to make it not repeat and have had no luck. I have searched online for at least an hour and all other hints or solutions have not helped. This is the code I have so far, can anyone please help me?

 package array.sorter.project;

import java.util.Arrays;
import java.util.Random;

public class Sorting {
public static void main(String args[]){
int[] randomNumbers = new int[10000];

Random rand = new Random();{
for (int i = 1; i < randomNumbers.length; i++) {
  int n = rand.nextInt(10000);
  randomNumbers[i] = n;}


  for (int i = 0; i < randomNumbers.length; i++) {
      int smallestNo = randomNumbers[i];
      int posWithSmallest = i;
      for (int j = i+1; j < randomNumbers.length; j++) {
        int val = randomNumbers[j];
        if (val < smallestNo) {
          smallestNo = val;
          posWithSmallest = j;
        }
      }
      int tmp = randomNumbers[i];
      randomNumbers[i] = smallestNo;
      randomNumbers[posWithSmallest] = tmp;
}
Arrays.sort(randomNumbers);

for (int i = 0; i < randomNumbers.length; i++) {
      System.out.println("Position " + i + " : " + randomNumbers[i]);
    }



    }

}

}
Andrew Thompson
  • 168,117
  • 40
  • 217
  • 433
user2297587
  • 1
  • _"As you can see, this is basically asking you to make the array put the numbers 0-9999 in an array in order of least to greatest."_ No, I actually don't see. Where does the assignment imply anything about ordering? – Matt Ball Apr 19 '13 at 02:57
  • *"I have an okay teacher but he has a very thick accent that is hard to understand."* Communicate via. email (or otherwise in writing). – Andrew Thompson Apr 19 '13 at 02:58
  • 2
    10k random numbers, between `0 to 9999` & no repetition. You needn't even code so much for this! Just fill your array with numbers from `0-9999` and you're done! – Rahul Apr 19 '13 at 02:59
  • @MattBall Hello, sorry, I should have posted the exact instructions from the professor. 1. Write a program name sorting.java that will use an array to store 10,000 randomly generated numbers (ranging from 1 to 10,000 no repeat number) 2. Using the selection sort algorithm to sort the number in ascending order. 3. Display the sorted sequence, each line shows just one number – user2297587 Apr 19 '13 at 03:00
  • possible duplicate of [Unique random numbers in O(1)?](http://stackoverflow.com/questions/196017/unique-random-numbers-in-o1) – Matt Ball Apr 19 '13 at 03:00
  • @R.J - (don't forget to shuffle the array) – jahroy Apr 19 '13 at 03:01
  • @jahroy - Nope, that's not required, as the OP mentioned _order of least to greatest_ – Rahul Apr 19 '13 at 03:02
  • @R.J - Now that the OP has revealed the actual details of the assigment (which were originally hidden from us) everything makes sense. First do what you said, then shuffle the array, then sort, then print. – jahroy Apr 19 '13 at 03:10

4 Answers4

2

Instead of randomly generating 10000 numbers from 0 to 9999, generate 0...9999 in ascending order and shuffle the array. Make sure that your shuffling is unbiased, e.g. that there are n! ways it can complete (if you're not sure, desk check it with n = 3 to see if it is unbiased)

Patashu
  • 21,443
  • 3
  • 45
  • 53
  • This is the solution. Since it's an assigment, she probably won't be able to take advantage of the shuffle method. So... Se'll have to write her own shuffle method, which should be pretty straightforward and should be a good learning exercise. – jahroy Apr 19 '13 at 03:02
  • Thank you for the help, but as you can see in the comments, the exact instructions are to sort the array in ascending order. This is confusing to me, as I would think that would just mean to put the numbers 0-9999 in order in an array, but this seems extremely simple for a programming course. – user2297587 Apr 19 '13 at 03:03
  • @user2297587 I do not understand. Either you are expected to sort repeating random numbers or shuffle nonrepeating random numbers. (Or possibly shuffle nonrepeating random numbers, print, THEN sort, print to demonstrate you can do both?) – Patashu Apr 19 '13 at 03:04
  • 1
    @user2297587 - not every complex question has a complex solution! – Rahul Apr 19 '13 at 03:04
  • So... Either you don't understand the assignment, or the assignment is to create an ordered array, shuffle it, then sort it again. – jahroy Apr 19 '13 at 03:05
  • Finding a simple answer is the crux of the programmer's trade. It is not always possible, but always a goal to pursue. Simplest design is best, other things being equal. – 9000 Apr 19 '13 at 03:06
2

You can not generate 10000 random integers in range 0-9999 without duplicates, there are only 10000 of then, so you need all.

What you can do is to rearrange, shuffle them.

So:

  import java.util.Collections;
  import java.util.Arrays;

  ...
  int[] ten_thousand = new int[10000];
  for (int i=0; i < 10000; i+=1) ten_thousand[i] = i;
  return Collections.shuffle(Arrays.asList(ten_thousand));

Know your weapons :)

9000
  • 39,899
  • 9
  • 66
  • 104
  • Can you guys check my code for me? for (int i=0; i x[j]) { minIndex = j; } } if (minIndex != i) { int temp = x[i]; x[i] = x[minIndex]; x[minIndex] = temp; } } } } – user2297587 Apr 19 '13 at 03:11
  • @EvgeniyDorofeev: under Java 7, it just did. A syntax error there was, but in a different place. – 9000 Apr 19 '13 at 05:44
  • Try System.out.println(Arrays.asList(ten_thousand).size()); it will print 1 not 10000 as it's supposed to be – Evgeniy Dorofeev Apr 19 '13 at 05:53
1

If you do not want to use shuffle

private static int[] generateRandom(int count) {
    int[] randomNumbers = new int[count];

    Set<Integer> checker = new HashSet<Integer>();

    Random rand = new Random();
    for (int i = 0; i < count;) {
        int nextInt = rand.nextInt(count);
        if (!checker.contains(nextInt)) {
            randomNumbers[i++] = nextInt;
            checker.add(nextInt);
        }
    }

    return randomNumbers;
}
Arun P Johny
  • 384,651
  • 66
  • 527
  • 531
0

I've written a O(n) algorithm to solve this problem inspired by the book Programming Pearls, 2nd Edition.the code is below,i will explain it later:

    /**
 * randomly select k numbers in [0,n),and sort them in random order.(k<=n)
 */
public static int[] getRandomArray(int n, int k) {
    if (k > n) {
        k = n;
    }
    int[] rets = new int[k]; // store the random ordered number
    int[] array = new int[n];// original array that array[i] is i
    for (int i = 0; i < n; i++)
        array[i] = i;
    Random random = new Random();
    for (int j = 0; j < k; j++) {
        // generate a random number between [j,n) as index
        int index = j + random.nextInt(n - j);
        // swap array[j] and array[index]，so array[0..j] are all non-repeat
        // random number
        int temp = array[index];
        array[index] = array[j];
        array[j] = temp;
        // store it in rets
        rets[j] = temp;
    }
    return rets;
}

explain:

to generate non-repeating 10,000 random numbers between 0-9999

can be considered to arrange number 0-9999 in random order。 1,the k number are stored in array,within which x in position x.

2,for the number j,random select a index from [j,n),that's index,

3,swap the position of j from j to index,(e.q. to swap the number at index to position j)

4,loop j from 0 to k,

BlackJoker
  • 3,099
  • 2
  • 20
  • 27