English Amiga Board

English Amiga Board (https://eab.abime.net/index.php)
-   Coders. General (https://eab.abime.net/forumdisplay.php?f=37)
-   -   Picking names at random from a list (https://eab.abime.net/showthread.php?t=62502)

Champions_2002 03 January 2012 15:38
Picking names at random from a list
 
Hi there, i have decide to learn Basic programming, and i have done the little things in AMOS.

the problem i have is

i have 12 names that i want to be picked at random and then print to screen

i.e

name 5
name 1
name 12
name 10
and so on


how do i do this please

Ed Cruse 03 January 2012 19:07
Quote:
Originally Posted by Champions_2002 (Post 793899)
Hi there, i have decide to learn Basic programming, and i have done the little things in AMOS.

the problem i have is

i have 12 names that i want to be picked at random and then print to screen

i.e

name 5
name 1
name 12
name 10
and so on


how do i do this please

Stores the 12 names into a string array, use a random generator to pick which one, mark that one with an integer array as being used, run the random generator until you get a name that hasn't been used. If AMOS doesn't have a random generator then there are several ways to make simple ones with floating pointer numbers. Somewhere I have a simple one but I can't find it, it does from 0 to 1.0 so you scale and offset it to get what you want.

Leffmann 03 January 2012 19:59
In AMOS you can use f.ex Rnd(10) to return an integer from 0 up to and including 10, and if you insert the line Randomize Timer in the beginning then you get different numbers every time you run your program.

Thorham 03 January 2012 20:16
What you need is a shuffling algorithm. Durstenfelds shuffling algorithm is the best one, as it can only pick each item in your list once, and it has no bias (meaning that any bias comes from your random number generator, and from not implementing some extra code to handle a certain kind of bias).

If you have questions, ask :great

Fisher-Yates shuffle: http://en.wikipedia.org/wiki/Fisher–Yates_shuffle
Durstenfeld shuffle for computer use: http://en.wikipedia.org/wiki/Fisher–...dern_algorithm

Ed Cruse 04 January 2012 17:29
Quote:
Originally Posted by Thorham (Post 793927)
What you need is a shuffling algorithm. Durstenfelds shuffling algorithm is the best one, as it can only pick each item in your list once, and it has no bias (meaning that any bias comes from your random number generator, and from not implementing some extra code to handle a certain kind of bias).

If you have questions, ask :great

Fisher-Yates shuffle: http://en.wikipedia.org/wiki/Fisher–Yates_shuffle
Durstenfeld shuffle for computer use: http://en.wikipedia.org/wiki/Fisher–...dern_algorithm

Doesn't a shuffle algorithm still have to have some kind of random generator in it? The shuffle still has to be random and therefor can still have a bias.

Thorham 04 January 2012 18:14
Quote:
Originally Posted by Ed Cruse (Post 794092)
Doesn't a shuffle algorithm still have to have some kind of random generator in it? The shuffle still has to be random and therefor can still have a bias.
The only source of bias in the Durstenfeld shuffling algorithm comes from not handling mod bias (I can give you an explanation of this). When this is taken care of, the algorithm itself is bias free, and the only source of bias comes from the RNG used, and is therefore external (because the RNG isn't part of the shuffling algorithm).

Another shuffling algorithm (a very bad one) picks two random numbers and swaps the entries in the list you're shuffling based on those two picks. This is a biased method. Even when your RNG is completely bias free, this shuffling algorithm's output will still be biased.

Radertified 04 January 2012 22:43
It feels so weird going back to BASIC after so many years of using proper languages C, C++, etc., but I decided to give it a try. Booted up AMOS and came up with the following:

http://i.imgur.com/3FzDA.png

(sorry. No idea how to export as text in AMOS, so a screenshot it is)

It creates an array of 10 entries (well, 11 according to the manual, which is why there's index 10), selects a random number, then displays that entry. Super simple.

A shuffle algorithm is overkill for such a simple task :)

Hope that helps you, Champions_2002.

Thorham 05 January 2012 05:33
Quote:
Originally Posted by Radertified (Post 794141)
A shuffle algorithm is overkill for such a simple task :)
Yes, it is. I mis-read the question. But it may still be useful if items shouldn't be picked more than once, even though it probably doesn't apply here.

Ed Cruse 05 January 2012 21:05
Quote:
Originally Posted by Thorham (Post 794095)
The only source of bias in the Durstenfeld shuffling algorithm comes from not handling mod bias (I can give you an explanation of this). When this is taken care of, the algorithm itself is bias free, and the only source of bias comes from the RNG used, and is therefore external (because the RNG isn't part of the shuffling algorithm).

Another shuffling algorithm (a very bad one) picks two random numbers and swaps the entries in the list you're shuffling based on those two picks. This is a biased method. Even when your RNG is completely bias free, this shuffling algorithm's output will still be biased.
Then wouldn't the method I described be as bias free as the RNG. It's real simple, do an RNG from 0-11 and pick from the list and then mark that entry as picked. Then run the generator again and use that pick unless it's already been picked in which case run the generator again until you get an unpicked entry. Now obviously when you get to the end of the list the generator will get run a lot because the probability of an entry having already been pick is high. There should be no bias though.

Thorham 05 January 2012 23:22
Quote:
Originally Posted by Ed Cruse (Post 794362)
Then wouldn't the method I described be as bias free as the RNG. It's real simple, do an RNG from 0-11 and pick from the list and then mark that entry as picked. Then run the generator again and use that pick unless it's already been picked in which case run the generator again until you get an unpicked entry. Now obviously when you get to the end of the list the generator will get run a lot because the probability of an entry having already been pick is high. There should be no bias though.
I really don't know. It has to be tested ;) But re-picking numbers doesn't seem to be a problem (although these things can be tricky to judge properly).

I just listed Durstenfelds algorithm because it's the most efficient. It allows you to shuffle any kind of array in-place, and it only has to re-pick a random number once in a while (although for big moduli this will take extra code to handle efficiently). Also, for smaller arrays, it's possible to use a modulus list, making the thing even faster.


All times are GMT +2. The time now is 00:08.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.

Page generated in 0.04897 seconds with 11 queries