generation of a randomed sorted list of integers
i'm trying to generate a sorted list of integers but there is a restriction that these sorted randomed generated integers must be uniformaly distribued within the range of numbers needed for example (1 -1000)?does any body know how can we generate random numbers and at the same time sorted with uniform distribution?
i have thought about an idea like starting from 1 for example and and then let the difference between each two numbers is random within 1 to 10 then adding this random integer to the last number generated and soo on .. but i don't feel it is efficient as maybe the random difference would be 1 each time . so i will never get a uniformly sorted list .. any ideas or suggestions ,please?
[720 byte] By [
d_rotha] at [2007-11-27 8:03:17]
Add the ints 1 to 1000 to a List, then use the Collections.sort() method on it. Alternatively, you could use an array of ints and the Arrays.sort() method.
> i'm trying to generate a sorted list of integers but
> there is a restriction that these sorted randomed
> generated integers must be uniformaly distribued
> within the range of numbers needed for example (1
> -1000)?does any body know how can we generate random
> numbers and at the same time sorted with uniform
> distribution?
>
> i have thought about an idea like starting from 1 for
> example and and then let the difference between each
> two numbers is random within 1 to 10 then adding this
> random integer to the last number generated and soo
> on .. but i don't feel it is efficient as maybe the
> random difference would be 1 each time . so i will
> never get a uniformly sorted list .. any ideas or
> suggestions ,please?
My guess is that you generate the numbers first, then sort them. If you use the pseudorandom number generator, Random, will generate numbers with a roughly uniform distribution. You have to do some work to it if you want some other type of distribution.
> ...> You have to do some work to it if you want some other type of> distribution.One can use the nextGaussian() method from the java.util.Random class for a (pseudo) random "normally" distributed number.
> > ...
> > You have to do some work to it if you want some
> other type of
> > distribution.
>
> One can use the nextGaussian() method from the
> java.util.Random class for a (pseudo) random
> "normally" distributed number.
but he wants it uniformly distributed, which means he requires no distribution.
mmmm thanks for the suggestions , but actually it is a sort techniques assignment , so i just can't generate then sort , it must be generated without sorting but sorted at the same time!! then after that , i have to take this list and sort it with the sorted methods i have implemented , so , as they need to c the time taken by each of them on sorting a sorted list ?
> but he wants it uniformly distributed, which
> means he requires no distribution.
Yes, but my reply was not addressed to the OP, but at your comment that there's work to be done in order to get a (pseudo) random number other than a uniformly distributed one. My assumption was that you implied that there was only one possible distribution available with the java.util.Random class.
That's all.
; )
> mmmm thanks for the suggestions , but actually it is
> a sort techniques assignment , so i just can't
> generate then sort , it must be generated without
> sorting but sorted at the same time!! then after that
> , i have to take this list and sort it with the
> sorted methods i have implemented , so , as they need
> to c the time taken by each of them on sorting a
> sorted list ?
So? You can generate a list or array of (pseudo) random numbers and then sort that collection with the sort(...) method you yourself have implemented. Post back if you get stuck with a specific piece of code.
Good luck.
> Yes, but my reply was not addressed to the OP, but at
> your comment that there's work to be done in order to
> get a (pseudo) random number other than a uniformly
> distributed one. My assumption was that you implied
> that there was only one possible distribution
> available with the java.util.Random class.
> That's all.
> ; )
My bad, and thanks.
>
> So? You can generate a list or array of (pseudo)
> random numbers and then sort that collection with the
> sort(...) method you yourself have implemented. Post
> back if you get stuck with a specific piece of code.
> i can't sort , in order to sort again , it is needed to test my methods on an already sorted list that i generate without sorting it before the test.
i don't know if my question is clear enough ....it seems i can't explain properly what i need to say
> i don't know if my question is clear enough ....it
> seems i can't explain properly what i need to say
You need to add the numbers to the list one by one, sorting them as they're added? If so, then just generate the random numbers with the Random class, and pass it to the method you write that adds it to the list in the proper sorted position.
> i can't sort , in order to sort again , it is
> needed to test my methods on an already sorted list
> that i generate without sorting it before the test.
> i don't know if my question is clear enough ....
No, I'm afraid not. The above makes no sense to me. Why would you test your method on an already sorted list?
> it seems i can't explain properly what i need to say
Not to me at least.
> mmmm thanks for the suggestions , but actually it is
> a sort techniques assignment , so i just can't
> generate then sort , it must be generated without
> sorting but sorted at the same time!!
Ok, this doesn't make sense unless what you mean is that you have to build the list sorted - that is, you have to insert each new value into the list in the proper spot as you add to the list. Is that correct?
tsitha at 2007-7-12 19:45:24 >
do the random numbers have to be unique? or can numbers repeat?matfud
