There is this programming/mathematical problem I have; it is the problem of generating a sequence of n unique random numbers, where the random number $n$ is element of of the set $S = \{0, 1, 2, \cdots N-1\}$ (Like permuting the numbers, but without using memory.)
Recently I kinda solved the problem on my own, and I got a result that I've transcribed below, without the use of formal math, just programming.
Now, it seems that this problem has already been solved in past by constructing LFSR (Linear feedback shift register) by Galois or some other mathematician. (I actually found out about LFSR first, and then built my "kind of" soulution, because I couldn't understand the LFSR Wikipedia article, and didn't just want to copy-and-paste the source code.)
My problem is I don't understand a word of formal mathematics and would like to learn how to solve this problem and compare my solution with that of what LFSR produces, so my question is:
Can you compare what I did below and somehow translate it to formal math?. So I can compare what I did and what the formal mathematicians were doing, and why they were doing it?
Remember, I only really understand programming terms, e.g., I only understand memory and its adressing, memory states, strings of zero and ones, etc. I don't understand primitive polynomials, field theory, and other mathy words.
Thanks very much in advance, if you can help me I promise a beer next time I see any one of you.
Here is the code I produced below: (You can run it in your browser -- I can't guarantee that it's correct but I believe the idea should be close enough, and I lack any other idea how to solve it:
//------------------------------------------------- function getPlacement( num ){ //; knuth permutations var places = []; for( var i = 0; i < num; ++i ) places.push( i ); var last_index = num-1; for( var i = num; i > 0; --i ){ var rnd_index = Random( i ); places = swap( places, rnd_index, last_index ); last_index--; } return places; } function readNum( num, placement ){ var numstr = num.toString(2); numstr = zeroextend( numstr, placement.length ); var numarr = numstr.split(''); var ret = []; for( var i = 0; i < placement.length; ++i ){ ret.push( numarr[ placement[i] ] ); } return ret.join(''); } function UniqRndSeq( maxLength, output ){ var placesNeeded = maxLength.toString(2).length; var randomPlacement = getPlacement( placesNeeded ); var initPosition = Random( maxLength ); var cnt = initPosition; var rndn; var numret = []; do{ rndn = parseInt( readNum( cnt, randomPlacement ), 2); output( rndn ); if( Containz( numret, rndn ) ) alert(rndn); numret.push(rndn); ++cnt; cnt = cnt % maxLength; } while( cnt != initPosition ); } //------------------------------------------------- //; helper funs var outp = []; function display( num ){ outp.push( num + "
" ); } function Random( x ){ return Math.floor(Math.random()*x); } function Containz( arr, num ){ for( var i = 0; i < arr.length; ++i ){ if( arr[i] == num ) return true; } return false; } function swap( list, a, b ){ var tmp = list[a]; list[a] = list[b]; list[b] = tmp; return list; } function zeroextend( num_bin_str, length ){ while( num_bin_str.length != length ){ num_bin_str = "0" + num_bin_str; } return num_bin_str; } //------------------------------------------------- function init(){ UniqRndSeq( 256, display); document.body.innerHTML = outp.join(''); }