?

Log in

No account? Create an account
entries friends calendar profile SpaceParanoids.net Previous Previous Next Next
Programming Question of the Day - Jarrett Heather
Jarrett Heather's Journal
jarrett
jarrett
Programming Question of the Day
Okay, sorry I haven't updated lately. I spent a few days in Southshore Lake Tahoe. It was fantastic. Pics to come shortly.

Anyways, I had a programming task and I'm not sure I've discovered the most elegant solution, so I thought I'd unleash it on my readership (Shaun? Ryan?).

Given an array ary() with a upper boundary of u, how would you return all the terms in the array exactly once in random order?

Here's the best I can come up with:

for i = u to 0 step -1
    r = int(rnd * i)
    return ary(r)
    ary(r) = ary(i)
next


Actually, that doesn't look too bad. That would probably work, wouldn't it? Is there a better way?
8 comments or Leave a comment
Comments
jarrett From: jarrett Date: January 25th, 2005 06:19 pm (UTC) (Link)
I tried this in VBScript and it worked pretty much as I figured it would.

randomize timer
dim
ary, i, r
ary = array(1,2,3,4,5,6,7,8,9)
for
i = ubound(ary) to 0 step -1
    r = int(rnd * i)
    response.write ary(r) & ", "
    ary(r) = ary(i)
next


2, 1, 3, 4, 8, 5, 6, 7, 9,
macklinr From: macklinr Date: January 25th, 2005 06:33 pm (UTC) (Link)
Try it ten times in a row, and see if your last number is something other than 9. I don't have time to try it out right now, but I suspect (granted, only with a few seconds' scrutiny) a flaw where you will always return the last number in the array last.
jarrett From: jarrett Date: January 25th, 2005 06:42 pm (UTC) (Link)
Don't overlook the fact that in the example, ary(8) = 9.

The function int(rnd * i) will return an integer between 0 and (i - 1), which is initially the last term in the array. The upper boundary is 9, but the last index is 8.

randomize timer
dim ary, i, r, j
for j = 1 to 20
    ary = array(1,2,3,4,5,6,7,8,9)
    for i = ubound(ary) to 0 step -1
        r = int(rnd * i)
        response.write ary(r) & ", "
        ary(r) = ary(i)
    next
    response.write "<br>"
next

6, 9, 2, 5, 1, 7, 4, 8, 3,
2, 5, 8, 4, 6, 9, 7, 1, 3,
1, 4, 2, 7, 3, 6, 9, 5, 8,
2, 5, 4, 3, 7, 9, 8, 1, 6,
6, 1, 3, 2, 4, 9, 8, 7, 5,
2, 6, 4, 9, 1, 8, 7, 5, 3,
5, 1, 3, 4, 7, 8, 2, 6, 9,
1, 9, 2, 4, 7, 3, 5, 8, 6,
3, 9, 1, 8, 4, 7, 5, 6, 2,
8, 5, 1, 4, 3, 7, 2, 6, 9,
4, 7, 6, 1, 8, 2, 9, 5, 3,
8, 7, 4, 5, 2, 1, 9, 3, 6,
1, 5, 9, 2, 4, 3, 6, 7, 8,
5, 7, 6, 1, 2, 9, 8, 3, 4,
6, 1, 4, 7, 3, 5, 8, 9, 2,
8, 2, 1, 9, 6, 7, 5, 4, 3,
4, 6, 1, 3, 2, 5, 9, 7, 8,
1, 2, 9, 7, 4, 6, 8, 5, 3,
3, 7, 9, 4, 2, 8, 5, 1, 6,
6, 1, 3, 8, 9, 5, 4, 7, 2,
jarrett From: jarrett Date: January 25th, 2005 06:49 pm (UTC) (Link)
Wait, that looks right, but it's still seems to avoid picking the last term first (and the first term never comes last as a side-effect).
macklinr From: macklinr Date: January 25th, 2005 06:56 pm (UTC) (Link)
RND returns a value between zero and one, but that's not an inclusive "between".

You won't get a 1 from RND, thus int(rnd * i) will never equal i, or your last term (the reason you get 0 is because int truncs the floating point part, which can result in 0). You might want to try "int(rnd * (i + 1))". This will increase your upper random limit without giving up 0.
jarrett From: jarrett Date: January 25th, 2005 07:46 pm (UTC) (Link)
Yes, that was exactly the bug. It was hardly noticable in the results, but the last item was never picked first, then the next to last was never picked second, and so on.

Because I'm a perfectionist, I wrote a routine to run the system x number of times and track the randomness of the results:

100 Loops:
                                   Position
       0      1      2      3      4      5      6      7      8      9   
0   12.50%  8.33% 11.11% 10.00% 11.11%  5.88% 16.67% 20.00%  7.69%  9.09%
1   14.29% 11.11% 12.50%  7.14%  9.09% 16.67%  7.14%  5.56% 14.29% 16.67%
2   14.29%  9.09% 20.00% 16.67%  7.69% 14.29%  8.33%  8.33%  9.09%  6.25%
3    6.67% 14.29% 14.29%  5.88% 11.11% 10.00% 12.50% 12.50% 12.50%  9.09%
4   20.00% 11.11% 11.11% 12.50% 12.50% 14.29%  7.69%  5.26%  6.67% 14.29%
5    6.25% 12.50%  8.33% 20.00%  6.25% 16.67% 11.11% 12.50%  8.33% 12.50%
6   14.29% 14.29%  5.00%  9.09% 25.00%  8.33% 10.00% 20.00% 10.00%  7.14%
7    7.14%  8.33%  8.33% 12.50%  9.09%  7.14% 20.00% 12.50% 25.00%  8.33%
8    8.33% 14.29% 10.00%  6.25%  8.33%  9.09% 11.11% 16.67% 10.00% 14.29%
9   11.11%  5.56% 12.50% 20.00% 14.29% 10.00%  7.14%  9.09% 10.00% 12.50%

Of course, the law of large numbers tells us we'll get a lot closer to 10% if we keep going.

Ten million loops:
                                   Position
       0      1      2      3      4      5      6      7      8      9   
0   10.01% 10.00% 10.00% 10.00% 10.00% 10.00% 10.00%  9.99% 10.00% 10.00%
1   10.00% 10.00%  9.99% 10.00% 10.00% 10.00% 10.00% 10.01% 10.00% 10.00%
2   10.00% 10.00% 10.00%  9.99% 10.00% 10.00% 10.00% 10.00% 10.00% 10.00%
3   10.00% 10.01% 10.00% 10.00%  9.99% 10.00% 10.00% 10.00% 10.01% 10.00%
4   10.00% 10.00% 10.00% 10.00% 10.01%  9.99% 10.00% 10.00% 10.00% 10.00%
5   10.00% 10.00% 10.00% 10.00%  9.99% 10.00% 10.00% 10.00% 10.00% 10.00%
6    9.99% 10.00% 10.00% 10.00% 10.00% 10.00% 10.01% 10.00%  9.99% 10.00%
7   10.00% 10.00% 10.00% 10.00% 10.00% 10.01% 10.00% 10.00% 10.00% 10.00%
8   10.00% 10.00% 10.00%  9.99% 10.00%  9.99%  9.99% 10.00% 10.01% 10.01%
9    9.99% 10.00% 10.01% 10.00% 10.00% 10.00% 10.00% 10.01%  9.99% 10.00%

That's a more even distribution than I expected. I guess that's how casinos stay in business, eh?
From: dark_wolfe Date: January 26th, 2005 01:13 am (UTC) (Link)
This just shows you have WAY too much time on your hands! :-)

(but kudos,nonetheless)
macklinr From: macklinr Date: January 25th, 2005 06:52 pm (UTC) (Link)
Like I said, a few seconds' scrutiny. I would have had more time to check it out, but that would have involved me not having to deal with everyone wanting a piece of me because I took yesterday off.

What you're effectively doing is a swap. Another idea you may want to do, depending on when you want to use the randomized data, is have a hird aray that you populate with the random data rather than just dumping it. Though, if you're just looking to simply dump it without much inbetween, it's more efficient the way you're doing it now.
8 comments or Leave a comment