[HN Gopher] Sattolo's Algorithm (2017)
___________________________________________________________________
Sattolo's Algorithm (2017)
Author : laybak
Score : 59 points
Date : 2020-09-15 18:47 UTC (4 hours ago)
(HTM) web link (danluu.com)
(TXT) w3m dump (danluu.com)
| kuratkull wrote:
| Weird, I was actually searching for a function that would do a
| "permutation of a list with exactly one cycle" an hour ago. I
| found Sattolo's, but found its use of random() disagreeable - it
| would depend on external/stdlib code and generate a new sequence
| every time if the seed is not fixed. Instead I looked into key
| schedules for cryptographic ciphers and found an easy solution -
| the key schedule function for RC4 for example. (My use does not
| care about the flaws/biases). It's a couple of lines of code,
| generates the same permutation for the same input+key - just use
| a couple of arbitrary hardcoded bytes as the key and you are
| done.
| UncleEntity wrote:
| Something like this: def sattolo(a, key):
| n = len(a) keylength = len(key) j = 0
| for i in range(n - 1): j = (j + a[i] + key[i %
| keylength]) % n a[i], a[j] = a[j], a[i]
|
| (key needs to be a byte string because it's easier that way)
|
| --edit--
|
| Doesn't work for producing a singlar path: >>>
| x = [0,1,2,3,4,5,6,7,8,9] >>> sattolo(x, b'zanzibar')
| >>> x [0, 2, 1, 5, 4, 3, 8, 6, 9, 7]
| jldugger wrote:
| > permutation of a list with exactly one cycle
|
| I'm having trouble parsing the motivation and terminology. When
| a list has one cycle, does that mean it repeats once? Or is
| this basically 'i want a random but stable order of events'?
| GuB-42 wrote:
| If you want a quick, easy and good quality random number
| generator, you might want to look at xorshifts.
|
| There are a lot of variations, but I particularly like the 128
| bit version from the original paper [1].
|
| Here is the entire code unsigned long xor128()
| { static unsigned long
| x=123456789,y=362436069,z=521288629,w=88675123;
| unsigned long t; t=(x^(x<<11));x=y;y=z;z=w;
| return( w=(w^(w>>19))^(t^(t>>8)) ); }
|
| Note: Do not use for security applications! It is not
| cryptographically secure. But if you need that, or if you are
| running Monte Carlo simulations and want nothing but the best,
| you probably should use specialized libraries anyways.
|
| [1]
| https://www.jstatsoft.org/index.php/jss/article/view/v008i14...
|
| Edit: And since we are in the subject of picking random numbers
| for Sattolo's algorithm. Using a simple modulo operator for get
| a range from a single random number going from 0 to 2^n-1 (like
| most RNGs produce) can introduce a bias. If the list is short
| and the numbers are large, it doesn't make that big a
| difference, but it is something to consider.
| Jtsummers wrote:
| The motivation for writing this amuses me. The Wikipedia prose
| "proof" is frustratingly familiar to many math textbooks I had
| when getting my BS many years ago. Fortunately, I had a couple
| professors who insisted on properly structuring proofs so that
| they were, you know, actually readable and understandable.
|
| That Wikipedia prose is like the lazy author's approach, it's a
| brain dump and not a real attempt to inform or educate. It is
| nice that there is Python code in the relevant section on the
| algorithm, that's informative (and why I like Python, it's
| executable pseudocode). But it would also be nice to have
| properly structured proofs to go along with the awful prose
| section (and either remove it or clean it up).
|
| Also, here's the discussion from when this was first posted:
| https://news.ycombinator.com/item?id=14967697
| benrbray wrote:
| I had the same experience as a math undergrad. Too many
| professors seem to have forgotten what it was like to be a
| student. They write books that are great reference material for
| their colleagues but which are utterly opaque to a student who
| is still working to build their foundation.
|
| Textbooks often format proofs as a sequence paragraphs, but
| this really obscures the logical structure of the argument. As
| a student, I found it very helpful to write down proofs as
| nested lists [1,2] instead.
|
| Admittedly, now that I have more experience, I do like my
| proofs to be more terse when I'm communicating them just to
| myself.
|
| [1]: https://benrbray.com/static/notes/separating-hyperplane-
| thm_... [2]: https://benrbray.com/static/notes/minimax-
| approx_nov16.pdf
| Jtsummers wrote:
| Your examples are, more or less, how I was taught to
| construct proofs. It's just much clearer and easier to
| read/follow than the prose-style in that Wikipedia page. And
| you can always supplement one with the other, just like the
| code example. Technically unnecessary since there was a prose
| description of the algorithm, but from a
| readability/understandability perspective it's immensely
| useful.
___________________________________________________________________
(page generated 2020-09-15 23:00 UTC)