| Author |
Message |
Terje Mathisen
Guest
|
 Posted:
Tue Feb 01, 2005 7:57 am Post subject:
Re: Relocating application architecture and compiler support |
|
|
Mabden wrote:
| Quote: | Well, my tile game uses a simple "shuffle" routine that I've never even
examined once. I just run through all the tiles and randomly place them
in "the bag". If it isn't a good function then I guess my game might
generate the same tile set twice. So far I haven't noticed it happening,
tho. One day I should look into "proving" it is not omitting some
combinations, or repeating some. But, hey, it's only a tile game, NOT a
matter of life and death. OH it's for the Palm OS and it's free here:
|
What you've described does sound like the one and only proper shuffle
routine:
You want a routine that takes N tokens (cards/chips/whatever) and return
any of the N! (N factorial) possible permutations with equal probability.
The easiest way to do this in-place is to start with the full array,
then pick a random number in [0..N-1] range. Swap this entry with the
last entry (this could end up being a NOP if the entry selected was the
last entry!), then decrement N.
Repeat until only a single entry remains.
Assuming your random number picker can return any integer in a fixed
range with equal probability (yes, I know this is the _hard_ part!),
then you've just generated a shuffle where all possible permutations are
equally likely.
void shuffle(item *data, int nrofitems)
{
int r, i;
item t;
for (i = nrofitems-1; i > 0; i--) {
r = randomrange(0,i); /* Return an int in the [0..j] range */
/* Swap: */
t = data[i]; data[i] = data[r]; data[r] = t;
}
}
Terje
--
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching" |
|
| Back to top |
|
 |
Jan Vorbrüggen
Guest
|
| Posted:
Tue Feb 01, 2005 1:29 pm Post subject:
Re: Relocating application architecture and compiler support |
|
|
| Quote: | What you've described does sound like the one and only proper shuffle
routine:
|
The algorithm I used was, I believe, your's in reverse - sort-of. I generated
N random numbers in the range 0..1, sorted them, and then used the set of
sorted indices to generate the sweep, as physicists running Monte Carlo
simulations call it. I suppose your swap procedure is basically running
a sort algorithm piece-meal.
Jan |
|
| Back to top |
|
|
Terje Mathisen
Guest
|
| Posted:
Tue Feb 01, 2005 4:38 pm Post subject:
Shuffle algorithms (Was: Re: Relocating application architec |
|
|
(followups pruned)
Jan Vorbrüggen wrote:
| Quote: | What you've described does sound like the one and only proper shuffle
routine:
The algorithm I used was, I believe, your's in reverse - sort-of. I
generated
N random numbers in the range 0..1, sorted them, and then used the set of
sorted indices to generate the sweep, as physicists running Monte Carlo
simulations call it. I suppose your swap procedure is basically running
a sort algorithm piece-meal.
|
Yes, more or less: It does less work, but requires a slightly more
complicated random number generator.
If I had to use your fp rand() function, then I'd simply scale the
generated value by N and truncate: At this point the resulting value can
be used to directly select the item to be placed last.
OTOH, I have also used something quite similar to your approach when I
needed to satisfy more complicated criteria:
A varying number of competitors will start in a varying number of
orienteering competitions, up to a maximum of 6. Since it can be an
advantage to start late, we want each competitor who starts in all 6
races to get one starting time in each sixth part of the total start
interval.
At the same time we want to make sure that all members of a single
family (defined as people with the same surname and the same club
affiliation) will start at approximately the same time each day, since
we assume they will travel in a single car, and the total start interval
can be more than four hours.
My solution was to first select a permutation of the numbers
(1,2,3,4,5,6), assign this to all family members, and then for each day
and person add a random fraction.
Do this for all families first, then use the single racers to fill up
the rest, before sorting each class separately.
Multiple classes can share a single course, so the course with the most
competitors determined how long the start would take. I used Bresenham
to interleave one or more classes into a single course and over the
total start interval.
Terje
--
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching" |
|
| Back to top |
|
|
freddy1X
Guest
|
| Posted:
Wed Feb 02, 2005 5:10 am Post subject:
When program bugs don't matter( was:Relocating application . |
|
|
Mabden wrote:
| Quote: | "Dan Koren" <dankoren@yahoo.com> wrote in message
news:41fe1269$1@news.meer.net...
"Terje Mathisen" <terje.mathisen@hda.hydro.com> wrote in message
news:ctl128$dj$2@osl016lin.hda.hydro.com...
Dan Koren wrote:
"Nick Maclaren" <nmm1@cus.cam.ac.uk> wrote in message
news:cte84t$nt0$1@gemini.csx.cam.ac.uk...
But I think that we are agreed that
even small scale embedded coding
should not be treated as a joke,
i.e. where mistakes don't matter,
even if you can usually get away
with it.
*NO* coding should be treated as a joke.
Agreed.
One should treat every byte one writes
as a matter of life and death.
That, in my not so humble opinion, is
rubbish,
It is not.
and you almost certainly know it.
|
( cuts )
I once wrote a dos-basic program inspired by the Novell screen saver /
activity indicator thing. I had 3 "pythons" moving around the screen at
random, eventually to discover one of the other's trails and start tracking
that instead. If the program were coded error-free, then in short order
all three would have been tail chasing in a tight loop. As it is, they
would break away momentarily from the tracking and start off in a random
direction. In this way they would eventually negotiate the entire screen
space. I liked this behavior better than what the intended one would have
given me and thus never corrected the program.
I still have it around here somewhere. On a fast machine the activity
looks more like maggots. <G>
There are many places where I would not tolerate such a blatant programming
error. This is one of the few where the error was the better choice.
--
not valid unless cashier activates card
/\>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\/
/\ I may be demented \/
/\ but I'm not crazy! \/
/\<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\/
* SPAyM trap: there is no X in my address * |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in