1. An Applied Algorithmic Activity:
- Posted by Patrick Barnes <mrtrick at gmail.com> Jun 29, 2004
- 444 views
Lets say we want to step through the numbers 1 to N, in a particular order. The order of the numbers can be arbitrary, but each number can only be visited once, and the order of the visits should be seeded by a number passed to it. For example: 1923840657 0123456798 7648235910 It seems like it needs some sort of hash value, but I couldn't for the life of me figure out how. How would you suggest I do this? Each seed doesn't have to generate a unique result, but it would be nice. -- MrTrick
2. Re: An Applied Algorithmic Activity:
- Posted by Matt Lewis <matthewwalkerlewis at yahoo.com> Jun 29, 2004
- 438 views
Patrick Barnes wrote: > > Lets say we want to step through the numbers 1 to N, in a particular > order. The order of the numbers can be arbitrary, but each number can > only be visited once, and the order of the visits should be seeded by > a number passed to it. > > For example: > 1923840657 > 0123456798 > 7648235910 > > It seems like it needs some sort of hash value, but I couldn't for the > life of me figure out how. > How would you suggest I do this? Each seed doesn't have to generate a > unique result, but it would be nice. One way to do this is to iterate using a number that is relatively prime to N. If two numbers are relatively prime, it means that their greatest common divisor is 1. So suppose N = 10. You could use 7, to pick a number at random, and you would get (modulo 10, of course): 7, 4, 1, 8, 5, 2, 9, 6, 3, 0 In euphoria:
integer N, n, p N = 10 p = 7 n = 0 for i = 1 to N do n = remainder( n + p, N ) ? n end for
Matt Lewis
3. Re: An Applied Algorithmic Activity:
- Posted by Patrick Barnes <mrtrick at gmail.com> Jun 30, 2004
- 422 views
> One way to do this is to iterate using a number that is relatively prime > to N. If two numbers are relatively prime, it means that their greatest > common divisor is 1. > > So suppose N = 10. You could use 7, to pick a number at random, and > you would get (modulo 10, of course): > > 7, 4, 1, 8, 5, 2, 9, 6, 3, 0 That looks good! Now I just need a lowest common denominator function:
function lcd(atom a, atom b) atom c while b do c = remainder(a, b) a = b b = c end while return a end function
(Hooray for Eulers method - http://www.mathwizz.com/fractions/help/help3.htm ) and that'll give me a list of possible seed values. Thanks all... this should work. -- MrTrick
4. Re: An Applied Algorithmic Activity:
- Posted by Rolf Schröder <Rolf.Schroeder at desy.de> Jun 30, 2004
- 452 views
Hi Patrick, Patrick Barnes wrote: > > Lets say we want to step through the numbers 1 to N, in a particular > order. The order of the numbers can be arbitrary, but each number can > only be visited once, and the order of the visits should be seeded by > a number passed to it. > > For example: > 1923840657 > 0123456798 > 7648235910 > > It seems like it needs some sort of hash value, but I couldn't for the > life of me figure out how. > How would you suggest I do this? Each seed doesn't have to generate a > unique result, but it would be nice. > -- is this a function - which is from Jiri Babor - which might be helpful for you?: function shuffle(sequence s) object temp integer j for i = length(s) to 2 by -1 do j = rand(i) temp = s[j] s[j] = s[i] s[i] = temp end for return s end function Have a nice day, Rolf ----------------------------------------------------- | Dr.Rolf Schröder | E B | | DESY MST-1 | C | | Notkestraße 85 | D | | D-22603 Hamburg | A | | Earth |--------------------------------| | Solar System | Phone : +49-40-8998-2628 | | Milky Way | Fax : +49-40-8994-2628 | | Local Group | mailto:Rolf.Schroeder at DESY.de | | Known Universe | http://desyntwww.desy.de/~rolf | -----------------------------------------------------
5. Re: An Applied Algorithmic Activity:
- Posted by Patrick Barnes <mrtrick at gmail.com> Jun 30, 2004
- 464 views
> is this a function - which is from Jiri Babor - which might be helpful > for you?: > > function shuffle(sequence s) > object temp > integer j > > for i = length(s) to 2 by -1 do > j = rand(i) > temp = s[j] > s[j] = s[i] > s[i] = temp > end for > return s > end function Unfortunately no, because of the randomness in it. The thing needs to be reproducible again. -- MrTrick
6. Re: An Applied Algorithmic Activity:
- Posted by "Unkmar" <L3Euphoria at bellsouth.net> Jun 30, 2004
- 437 views
----- Original Message ----- From: "Patrick Barnes" Sent: Wednesday, June 30, 2004 4:48 AM Subject: Re: An Applied Algorithmic Activity: > > is this a function - which is from Jiri Babor - which might be helpful > > for you?: ... > Unfortunately no, because of the randomness in it. The thing needs to > be reproducible again. > > -- > MrTrick include machine.e set_rand(i1) Set the random number generator to a certain state, i1, so that you will get a known series of random numbers on subsequent calls to rand(). function shuffle(sequence s, integer seed) object temp integer j set_rand(seed) for i = length(s) to 2 by -1 do j = rand(i) temp = s[j] s[j] = s[i] s[i] = temp end for return s end function unkmar