Non Repeating Generator

  • (2 Pages)
  • +
  • 1
  • 2

15 Replies - 4125 Views - Last Post: 17 August 2010 - 03:49 AM Rate Topic: -----

#1 eghowell  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 24-December 09

Non Repeating Generator

Posted 14 August 2010 - 02:31 AM

Hello,

I have a question and could use some help with a piece of code I'm trying to get working. This program checks for a file and if its not there creates it. Then it populates the file with 100 numbers randomly using the math.random method. The problem seems that when the random numbers are created duplicate numbers are created and I don't get 100 unique numbers only 100 randomly generated numbers with duplicates. Is there another method or something else I should be using?

When its all said and done I want a sequential group of numbers from 0 to 99.


import java.util.*;
import java.io.*;

public class numberToarrange
{
public static void main(String[] args) throws Exception
{
// Check if source file exists
File file = new File("Sample1.txt");
File file1 = new File("SampleOut.txt");

// If file doesn't exist, create it

if (!file.exists())
{
// Create the file
Formatter output = new Formatter(file);

// Generates 100 integer numbers to file
for (int i = 1; i <= 100; i++)
{
output.format("%d ", (int)(Math.random() * 100));
}
output.close();

}

// Create scanner for file input from file Sample1.txt
Scanner input = new Scanner(file);
// Create an array
int[] numbers = new int[100];

// Loop to store file content in an array
for (int i = 0; i < 100; i++)
numbers[i] = input.nextInt();

// Sorts entire array
Arrays.sort(numbers);

// Loop used to output sorted numbers in Array
for (int i = 0; i < 100; i++)
System.out.print(numbers[i] + " ");

// Create sorted file
Formatter output1 = new Formatter(file1);

for (int i = 0; i <= 99; i++)
{
// int num = numbers[i];
output1.format("%d ", (int)(numbers[i]));
}
output1.close();

}

}




Is This A Good Question/Topic? 0
  • +

Replies To: Non Repeating Generator

#2 Crunch  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 139
  • View blog
  • Posts: 1,222
  • Joined: 28-July 09

Re: Non Repeating Generator

Posted 14 August 2010 - 04:01 AM

I will give you the pseudo-code for doing this

int value=0;
int array[] = new int[100];

while(true){
value = generated random number;
Search array for value;
if value not found in array :- Insert it into array and use it
}



Was This Post Helpful? 0
  • +
  • -

#3 b0ng01  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 38
  • View blog
  • Posts: 169
  • Joined: 16-July 10

Re: Non Repeating Generator

Posted 14 August 2010 - 04:38 AM

You're kind of confusing when you say that you want 99 random numbers between 0-99. But, what I believe you want is 100 unique numbers. I adjusted it so that you got numbers between 0-1200 and removed the file work. That looks like it was working. The hardest part about this is getting the unique numbers. To force creation and implementation of unique randoms I used a set.

import java.util.HashSet;
import java.util.Set;

/**
 *
 * @author tsama
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {

        // TODO code application logic here
       // SettlerBoard board = new SettlerBoard();
    //int[] uniqNum = null;
    Set set = new HashSet();
int numOfRand = 10;
int i = 0;
    while(i<10){
        int rand = (int)(Math.random()*1200);
        if(set.add(rand)){
           i++;
        }else{
            while(!set.add(rand))
            rand = (int) Math.random()*1200;
            i++;
        }
        }

 Integer[]  uniqNum = (Integer[])set.toArray(new Integer[set.size()]);


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

}



View PostCrunch, on 14 August 2010 - 03:01 AM, said:

I will give you the pseudo-code for doing this

int value=0;
int array[] = new int[100];

while(true){
value = generated random number;
Search array for value;
if value not found in array :- Insert it into array and use it
}




Wouldn't your pseudo-code create a problem where the value was found in the array and you need to replace it but your new randomly generated number is already in the array.
Was This Post Helpful? 0
  • +
  • -

#4 Vestah  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 21
  • View blog
  • Posts: 86
  • Joined: 15-October 09

Re: Non Repeating Generator

Posted 14 August 2010 - 05:35 AM

Is what you want a random permutation of an array containing the numbers 0-99 both inclusive once?

I have found a Stack overflow question which seems to have a nice discussion and solution on a problem which looks very much like yours.

If I understand your solution b0ng01 correctly, you generate 10 distinct numbers in the 0-1199 range and let them have the order decided by the hash set. This does not seem to solve the problem at hand, but it is interesting in its own right.

Also I suggest that you do not use the way Crunch outlined. It becomes slower and slower for each random number you want and freezes if you call it one time too many.

This post has been edited by Vestah: 14 August 2010 - 05:37 AM

Was This Post Helpful? 0
  • +
  • -

#5 Guest_Guest*


Reputation:

Re: Non Repeating Generator

Posted 14 August 2010 - 06:11 AM

View PostVestah, on 14 August 2010 - 04:35 AM, said:

Is what you want a random permutation of an array containing the numbers 0-99 both inclusive once?

I have found a Stack overflow question which seems to have a nice discussion and solution on a problem which looks very much like yours.

If I understand your solution b0ng01 correctly, you generate 10 distinct numbers in the 0-1199 range and let them have the order decided by the hash set. This does not seem to solve the problem at hand, but it is interesting in its own right.

Also I suggest that you do not use the way Crunch outlined. It becomes slower and slower for each random number you want and freezes if you call it one time too many.


He wanted 100, but I did 10, it would be simple to just have 100 numbers created. The ordering is another issue. But if I understand him correctly he wants 100 random numbers between 0-99 and at the end wants those random numbers to be put in order.

To adjust my code to do that, it would only require changing the range
rand = (int)(Math.random()*99);



and adjusting the number of numbers generated.
while(i<100)



Out of curiosity why do you say my solution is interesting?
Was This Post Helpful? 0

#6 bcranger  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,199
  • Joined: 01-February 10

Re: Non Repeating Generator

Posted 14 August 2010 - 07:44 AM

Use a Random object, do not call the Math.random() every single time. Instead, use the nextInt() method, and specify the max value exclusive as parameter.

As for your problem, it is very simple, here is a way you can approach getting the random numbers:
ArrayList<Integer> used = new ArrayList<Integer>();
Random r = new Random();
for(int i = 0; i < 100; i++)
{
  // replace with whatever max # desired, exclusive
  int n = r.getNextInt(101);
  if(used.contains(n))
    continue;
  else
    used.add(n);
  i++;
}
// now loop through the array and add to file


This post has been edited by bcranger: 14 August 2010 - 07:51 AM

Was This Post Helpful? 0
  • +
  • -

#7 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5882
  • View blog
  • Posts: 12,760
  • Joined: 16-October 07

Re: Non Repeating Generator

Posted 14 August 2010 - 08:14 AM

You have a set of 100 elements. You wish to get a random permutation of that set. The solution is to start with the complete set and randomly select from it until it's exhasted.

This is identical to how you shuffle a deck of cards, so searching on that will find you a solution.

Here's a basic one.
void randomizeArray(int [] a) {
	for(int i = a.length-1; i>1; i--) {
		int pos = (int)(Math.random() * (i+1));
		if (pos!=i) {
			int temp = a[i];
			a[i] = a[pos];
			a[pos] = temp;
		}
	}
}

int size = 100;
int [] array = new int[size];
for (int i=0; i<size; i++) { array[i] = i+1; }
randomizeArray(array);
for (int i=0; i<size; i++) { System.out.print(array[i] + " "); }
System.out.println();


Was This Post Helpful? 1
  • +
  • -

#8 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: Non Repeating Generator

Posted 14 August 2010 - 10:03 AM

Just fill an ArrayList with 100 numbers then remove them from a random position
ArrayList<Integer> al;
for(int i = 0; i < 100; i++)
   al.add(i);

int ranArray = new int[100];
Random ran = new Random();
for(int i = 0; i < 100; i++) {
   int next = ran.nextInt(al.size());
   a[i] = al.remove(next);
}


This post has been edited by pbl: 14 August 2010 - 07:44 PM
Reason for edit:: size(). Thanks Mac

Was This Post Helpful? 3
  • +
  • -

#9 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10658
  • View blog
  • Posts: 39,571
  • Joined: 27-December 08

Re: Non Repeating Generator

Posted 14 August 2010 - 05:54 PM

Don't forget the parentheses for size() here: int next = ran.nextInt(al.size);. :)
Was This Post Helpful? 0
  • +
  • -

#10 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: Non Repeating Generator

Posted 14 August 2010 - 07:45 PM

Oups... thanks macosxnerd101
Was This Post Helpful? 0
  • +
  • -

#11 Vestah  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 21
  • View blog
  • Posts: 86
  • Joined: 15-October 09

Re: Non Repeating Generator

Posted 15 August 2010 - 06:06 AM

I can your solution interesting b0ng01, because you use the structure of a HashSet to give a seemingly random order.

If you had actually tested your solution would have seen a number of problems.
I am not talking about the improper indention nor that (int) Math.random()*1200 that always gives 0.
With your given changes the resulting array always seem to same structure. I only tested 1 million iterations though.
The number of Math.random() calls is potentially unbounded. Experimentally it uses 418-419 calls on average for creating a set with all the numbers in the 0-99 range which is faster than I expected. (Min: 115, Max: 1832 for 1 million iterations)

Personally I would just use Collections.shuffle(list).
Here is the source code for Collections.shuffle(list, rnd): (The previous method just passes along a Random object. Note that I did not make this code.).
int size = list.size();
if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
    for (int i=size; i>1; i--)
        swap(list, i-1, rnd.nextInt(i));
} else {
    Object arr[] = list.toArray();

    // Shuffle array
    for (int i=size; i>1; i--)
        swap(arr, i-1, rnd.nextInt(i));

    // Dump array back into list
    ListIterator it = list.listIterator();
    for (int i=0; i<arr.length; i++) {
        it.next();
        it.set(arr[i]);
    }
}

Was This Post Helpful? 0
  • +
  • -

#12 eghowell  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 24-December 09

Re: Non Repeating Generator

Posted 16 August 2010 - 01:07 AM

I'm still at it trying to get this thing to work
Was This Post Helpful? 0
  • +
  • -

#13 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10658
  • View blog
  • Posts: 39,571
  • Joined: 27-December 08

Re: Non Repeating Generator

Posted 16 August 2010 - 04:59 AM

Can you post your code and problems?
Was This Post Helpful? 0
  • +
  • -

#14 g00se  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2777
  • View blog
  • Posts: 11,757
  • Joined: 20-September 08

Re: Non Repeating Generator

Posted 16 August 2010 - 09:42 AM

See http://technojeeves....-random-numbers
Was This Post Helpful? 0
  • +
  • -

#15 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: Non Repeating Generator

Posted 16 August 2010 - 08:32 PM

View Posteghowell, on 16 August 2010 - 02:07 AM, said:

I'm still at it trying to get this thing to work

and we should be able to deduct what is your problem by programmer's mind mental code transmission ? Post your code at least we'll know which of the multiple working proposed solutions you retained.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2