Computer Science Canada :: View topic - Randint from a set of numbers?

Computer Science Canada

Randint from a set of numbers?

Author:

skootles [ Sun Oct 02, 2005 12:48 pm ]

Post subject:

Randint from a set of numbers?

Wow... it's been a long time since I've been here Razz

But anyways, to the problem:

I want my program to choose a random number from a list of numbers. Right now, I just want the list to be from 1-8, so the list (obviously) would be: 1,2,3,4,5,6,7,8. Now, I could just do this:

code:

randint (variable,1,8)

But, I want it so that it only picks each number once. So, I was wondering if there was a way, for example, when the program selects... let's say... 5, it would then drop 5 from the list of numbers to choose from. Thus, the list would now be: 1,2,3,4,6,7,8

If that wasn't specific enough, I'll try to go into further detail.

Author:	beard0 [ Sun Oct 02, 2005 1:07 pm ]
Post subject:
Try putting your list of numbers in a flexible array (if you don't know what they are, the Turing help file is a good reference). Select a random number between lower(arrayName) and upper(arrayName), use that as your index. Then shuffle values down through your array, to replace the element you just "used", and remove the last element of your array - it is now ready for another selction.

Author:	skootles [ Sun Oct 02, 2005 1:14 pm ]
Post subject:
Arrays... I'm just starting to use those with turing. I've used them in VB, but only lightly. Anyways, thanks, I'll look up flexible arrays.

Author:	[Gandalf] [ Sun Oct 02, 2005 2:05 pm ]
Post subject:
Yep, I would do it like beard0 said. For any kind of 'list' you will for sure need to know arrays.

Author:	Cervantes [ Sun Oct 02, 2005 6:46 pm ]
Post subject:
[Gandalf] wrote: Yep, I would do it like beard0 said. For any kind of 'list' you will for sure need to know arrays. What about Linked Lists?

Author:	beard0 [ Sun Oct 02, 2005 7:01 pm ]
Post subject:
Probably a better idea from a programming point of view, but the array solution is probably an easier one to use. For someone just starting to use arrays, pointers may be a little too complex.

Author:	[Gandalf] [ Sun Oct 02, 2005 7:10 pm ]
Post subject:
Cervantes wrote: [Gandalf] wrote: Yep, I would do it like beard0 said. For any kind of 'list' you will for sure need to know arrays. What about Linked Lists? Would you be doing that without array knowledge?

Author:	Cervantes [ Sun Oct 02, 2005 7:11 pm ]
Post subject:
Ah, yes. I meant that solely as a comment to Gandalf. In fact, I was pondering whether to add a comment such as, "warning to skootles: clicking link may cause brain to explode".

Author:	TokenHerbz [ Sun Oct 02, 2005 9:08 pm ]
Post subject:
Array's are fairly simple, though the 2D arrays (which you dont need to know right now, but soon) can be a little more complicated... Anyways, i wrote the code you strived for, so if your really stuck, just post here, and ill show you the code, and explain to you how it works... But you must give it a good shot, its the only way to learn Good luck.!

Author:	Tony [ Mon Oct 03, 2005 8:27 am ]
Post subject:
tokenherbz wrote: Anyways, i wrote the code you strived for is it anything like this?

Author:

TokenHerbz [ Mon Oct 03, 2005 1:23 pm ]

Post subject:

...

im not so good at making efficiant code... this was mine...

code:

var maxnum: int := 10 %%Enter here your max number
var number: int %%This here is your number
var used: array 1 .. maxnum of boolean %%this will tell you if the numbers used or not

for i : 1 .. maxnum %%use a for statment to declare the array variable's
used(i) := false %%sets all the numbers NOT declared
end for
loop %%to keep the program going
for i: 1 .. maxnum %%use this for cause it holds the variables need'd (booleans)
randint(number,1,maxnum) %%randomizes your number
if number = i then %% if the random number = the one in the for
if used(i) = false then %%checks to see if the numbers been used
put number %%puts the number
used(i) := true %%now marks the number as been used
end if
end if
end for
end loop

Mine might not be as efficiant, but it works, i have problems making efficiant code, and i think thats my weak point... I must learn, or think more about how i can accomplish this... Nice code though Tony.

Author:

codemage [ Mon Oct 03, 2005 1:50 pm ]

Post subject:

This would be a slighly savvier method of implementing the main area of code, if you were to only use arrays. (The for & loop are switched, and there are a few other efficiency tweaks).

You essentially have parallel arrays here; one of them is a virtual array existing between 1 and maxnum.

Using arrays for this sort of code is very efficient with a small, consecutive array size. With really big nubmers, unsorted data types aren't so clean.

code:

for i : 1 .. maxnum
loop
number := Rand.Int (1, maxnum)
if used (number) = false then
put number
used (number) := true
end if
end loop
end for

Author:	beard0 [ Mon Oct 03, 2005 2:49 pm ]
Post subject:
codemage wrote: This would be a slighly savvier method of implementing the main area of code, if you were to only use arrays. Oh? Tony's is much better, as your method creates a random amount of wait time, incresing in expected duration each time through. It is actually quite inneficient.

Author:	Tony [ Mon Oct 03, 2005 3:35 pm ]
Post subject:
codemage - the unsorted list of unique number is what we're after. in your code forloop is not needed as the inside loop never exits beard0 points out the core difference in approaches. The idea is that when randomly picking a number you have a deminishing chance of getting a number that wasn't used yet. Example -- scramble 100 numbers in random order. randomly picking 1st unsorted number - 100% randomly picking 50th unsorted number - 50% randomly picking 100th unsorted number - 1% on average you make edit: 5 tries per number to be sorted (though you don't really notice that until you get into the last few numbers)

Author:

beard0 [ Mon Oct 03, 2005 7:23 pm ]

Post subject:

Tony wrote:

on average you make two tries per number to be sorted.

I get an average of 5.187378 tries per number to be sorted. Very Happy

code:

var x : real := 0
for i : 1 .. 100
x += 100 / i
end for
put x/100

Author:

md [ Mon Oct 03, 2005 9:09 pm ]

Post subject:

Since I'm too lazy to read all those people's posts; and since I might have a better solution anyways...

Why not just create an array (seem's you can't live without them), fill it with your data set (numbers), shuffle it (key), and then just step through the array.

Since I'm not much of a turing expert (ie. not at all) I'll write it in psudo-pascal which is a fairly simple language to grasp.

Pascal:

const
UPPER_BOUND = 8; (* or whatever number you want *)

var
data:array[1..UPPER_BOUND] of integer; (* data set *)
index:integer; (* current position in the array *)

i:integer;

procedure Shuffle
var
i, j:integer;
temp:integer;
begin
for i := 1 to UPPER_BOUND do
begin
j := (rand() mod UPPER_BOUND) + 1;
temp := data[j];
data[j] := data[i];
data[i] := temp;
end;
end;

function Random:integer;
begin
(* get the next element in the list *)
Random := data[index];

(* increment the index, if it is greater then the upper bound then *)
(* reset it to 1 and reshuffle the data set *)
index += 1;
if index > UPPER_BOUND then
begin
index := 1;
Shuffle;
end;
end;

begin
(* random seed *)
randseed := time();

(* fill the array with data *)
for i := 1 to UPPER_BOUND do
begin
write('Data (', i, ' of ', UPPER_BOUND, '):');
readln(data[i];
end;

(* Shuffle the data *)
Shuffle;

(* now output random numbers until the cows come home *)
while(true)
writeln(Random);

end.

Author:	beard0 [ Mon Oct 03, 2005 10:37 pm ]
Post subject:
Cornflake wrote: Since I'm too lazy to read all those people's posts; and since I might have a better solution anyways... You'd have done well to read them. This isn't what was wanted (unless, as is possible, I'm misunderstanding the pascal). It seems to me that your solution allows repeat output of the same number from the set: This is undesirable. Check out Tony's solution, as it seems to me by far the best.

Author:

skootles [ Tue Oct 04, 2005 12:09 am ]

Post subject:

Well, I didnt read most of the posts after Tony's (Didn't understand them much Razz

), but here's basically what I wanted (modified version of Tony's code):

code:

var size:int :=7 % Changed based on the letters in the word
var randN:int
var numbers:array 1..size of int
var word : string := "cookies" % Will be changed later

for i:1..size
numbers(i):=i
end for

for decreasing i:size ..1
randN := Rand.Int(1,i)
put word(numbers(randN))

numbers(randN):=numbers(i)

end for

Thanks for all the help Wink

Author:	TokenHerbz [ Tue Oct 04, 2005 1:29 am ]
Post subject:
scootles, dont use the code if you dont understand it... I want you to try it on your own now, and see if you can get it to work.

Author:	codemage [ Tue Oct 04, 2005 8:14 am ]
Post subject:
I missed Tony's complete solution. I'm aware of the inefficiency of the code I posted (see post). Like I explained, if the array was much larger, there'd be all sorts of wasted cycles. The snippet I posted was a re-write of the code done by tokenherbz - and wasn't meant to be a "best" solution.

Author:

Tony [ Tue Oct 04, 2005 8:14 am ]

Post subject:

beard0 wrote:

I get an average of 5.187378 tries per number to be sorted.

You're right. Here's another fun program

Turing:

const limit : int := 100

for try : 1 .. 10
var c : int := 0
for i : 1 .. limit
loop
c += 1
exit when Rand.Int (1, limit) >= i
end loop
end for
put "run #", try, ": ", c / limit, " tries per number"
end for

Author:	skootles [ Tue Oct 04, 2005 10:38 am ]
Post subject:
tokenherbz wrote: scootles, dont use the code if you dont understand it... I want you to try it on your own now, and see if you can get it to work. I understand the code I'm using (see above), so I think I'm good for now.

Author:

TokenHerbz [ Tue Oct 04, 2005 10:34 pm ]

Post subject:

Tony i ran your "fun" program and here where my resaults.

code:

run #1: 4.53 tries per number
run #2: 8.15 tries per number
run #3: 4.56 tries per number
run #4: 4.46 tries per number
run #5: 5.45 tries per number
run #6: 5.79 tries per number
run #7: 4.74 tries per number
run #8: 5.35 tries per number
run #9: 4.36 tries per number
run #10: 4.25 tries per number

What does this mean? i dont get what the test does?

I ran it over and over and...

Lowest number reached: 3.31
Highest number reached: 9.43

Author:	beard0 [ Tue Oct 04, 2005 10:42 pm ]
Post subject:
tokenherbz wrote: Tony i ran your "fun" program and here where my resaults. .... What does this mean? i dont get what the test does? I ran it over and over and... Lowest number reached: 3.31 Highest number reached: 9.43 It is a simulation of the bad method used above, with uncertain execution time. The program that I wrote in the post that Tony refers to computes the expected average number of guesses per number in each trial (for 100 numbers), using mathematical probabilities. Tony's actually runs 10 trials, to see the avergae number of guesses per number performed. As Tony's program is run over and over again, the average should tend towards my computed value.

Author:	Tony [ Wed Oct 05, 2005 7:30 am ]
Post subject:
tokenherbz wrote: Highest number reached: 9.43 This means that during such an odd run, your program had to pick a random number 943 times before finding enough to order 100 items.

You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy