random list of natural numbers

[Mico]

Hi everyone!

While my first post to this forum was in 2005, during the last 5-6 years I did not interact with the community. It's my fault and I hope to be regarded as a prodigal son rather than as a black sheep, especially because (as usual!) I am back here for a reason.

I need to generate a list of natural numbers from 1 to n in random order and I thought it was an easy task. Unfortunately, my code works as expected with small n values, but miserably fails with larger ones (e.g. n>50000, but with sign of degradation with much smaller values).

Code: Select all

dim as ulong a,b,i,n

n=100000
dim as ulong x(1 to n)
for i=1 to n
   x(i)=i
next i

randomize timer
for i=1 to n
    a=culng(rnd*n)+1
    b=culng(rnd*n)+1
    swap x(a),x(b)
next

open "rand_i.prn" for output as 1
for i=1 to n
    print #1, x(i)
next i
close 1

end

Basically, the list does not look as a random list and most numbers stay exactly at the same place. I also tried to add a second for/next cycle around or within the one that swaps random values, but it did not help.

I am sure the reason why my code does not work as expected is trivial, but still I have not been able to fix it so far. Any hints?

All the best,

Mico

[badidea]

So you want each number (in range 1 to n) to occur exactly once in the list?

I think that a 'dymanic list' is easiest.
1. Create a list 1 to n in order (like you do)
2. Randomly select 1 number form the list (by index)
3. Remove the number form the ordered list (make list smaller)
4. Add that number to a new (random) list
5. repeat from step 2 until initial list is empty

Your methode is not a good one. Some numbers will not be chosen and stay at their initial (ordered) place. If you do much more swaps it should improve, but that is not every efficient. And what is much more? A skilled mathematician can calculate that, I can not.

Something like this (order of steps a bit different and not guaranteed bug-free):

Code: Select all

const N = 10 'or 100000

dim as ulong ol(1 to N) 'ordered list
for i as integer = 1 to N
   ol(i) = i
next

dim as ulong ol_size = N
dim as ulong rl(1 to N) 'random list
dim as ulong ol_index, rl_index = 1

randomize timer

while ol_size > 0
	'select an index from remaining list
	ol_index = int(rnd * ol_size) + 1
	'add the corresponding value to the ramdom list
	rl(rl_index) = ol(ol_index)
	'updte index / pointer for next loop
	rl_index += 1
	'move last element into the selected place, deleting this fom ordered list
	ol(ol_index) = ol(ol_size)
	'make the useful list shorter / ignore the last element
	ol_size -= 1
wend 

print "random list:"
for i as integer = 1 to N
	print rl(i) & " ";
next

[MrSwiss]

If you only want unique numbers (ranged) within a array of defined size of elements,
then this may be, what you are looking for: Unique Numbers Sequence Generator

WARNING: the closer the requested 'elements' are to the defined size of 'range', the longer it takes to run.
(since the uniqueness test is getting longer and longer, the bigger the array is defined, as well as,
rejecting more and more generated random numbers)

[coderJeff]

@badidea, I think you have the right method. Only one iteration of the list of numbers, and 1/n chance of any number moved to any other position

The number of elements is known so can do it with a fixed array of the total elements (numbers):

Code: Select all

const n = 5000
randomize timer

'' initialize
dim x( 1 to n ) as integer
for i as integer = 1 to n
	x(i) = i
next

'' shuffle
'' remaining choices index = i through n
'' new list stored at index = 1 through i
for i as integer = 1 to n
	'' choose a number from the remaining choices
	dim j as integer = int( rnd * ( n + 1 - i ) ) + i
	'' swap it to the last position in the new list
	swap x(i), x(j)
next

'' print some results
for i as integer = 1 to 10
	print i, x(i)
next
for i as integer = n - 9 to n
	print i, x(i)
next

sleep

[Mico]

Thank you very much, everyone!

I was aware that my solution was far from perfect, as the average probability to move each number to another place is the same, but it is just a probability and therefore some numbers just stay at their place. What was really surprising was that the amount of numbers that stay at their original place seems to grow with the dimension of the list and, frankly, I cannot understand the reason for that dependence.

However, all the solutions you proposed are way smarter than mine and work nicely. Those suggested by coderJeff and badidea can generate and write to an ascii file one million random integers in 0.2 seconds on my PC. As for the one suggested by MrSwiss the cons are that is much slower and cannot handle so many numbers, but the pro is that it actually generates random integers in a given interval rather than just shuffling a list.

Thank you again!