存在数学问题，它是生成n个唯一随机数序列的问题（随机数是n{ 0，…，n}的元素，（如排列，但不使用内存））
最近我解决了那个问题，我确实得到了一些结果（阅读下面的内容，不使用形式数学，只通过编程）。
而且这个问题似乎在过去已经被伽罗瓦或其他数学家通过构造线性反馈移位寄存器（lfsr）完全解决了。（我第一次偶然发现了lfsr并建立了我的“类似”的解决方案，因为我不理解wiki上的lfsr文章，也不想只是复制粘贴源代码）
问题是我一个字都不懂，想学一学，把我的解和lfsr的解比较一下，所以问题是：
你能不能把我做的和那件事比较一下，然后把它翻译成形式数学，反之亦然。所以我能理解我做了什么，形式数学家做了什么（为什么他们需要它）？
记住，我的语言是编程语言，我只理解内存及其地址、内存状态、0和1的字符串等，我不理解原始多项式、场论和其他数学单词。
非常感谢你，如果你能帮我，我见到你时会给你买瓶啤酒。
下面是我的代码（你可以在浏览器中运行它，我不认为它是正确的，但我相信这个想法应该很接近，我缺乏任何其他的想法如何解决它）。以下内容：
<html>
<head>
<script>
//-------------------------------------------------
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 + "<br>" );
}
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('');
}
</script>
</head>
<body onload="init();">
</body>
</html>
最佳答案
线性反馈移位寄存器（LFSR）是确定性的，即它不使用任何随机数函数因此，您的代码不太可能对lfsr建模。如果你对多项式环或有限域理论一无所知，就很难解释lfsr背后的数学。然而，适当的lfsr生成n位数字字的m序列，其中n是lfsr中的级数。序列的长度是2^n-1个单词（零个单词不在序列中）。一般来说，我们只关心序列中单词的一个位位置（在galois lfsr中，这通常是0位，但实际上所有位都具有相同的属性）。从每个单词中提取的这个位形成一个2^n-1长度的位序列，该序列具有与随机性相关的以下众所周知的数学特性：
平衡属性：当序列的长度接近无穷大时，序列中1的个数接近0的个数序列中1的个数实际上总是比0的个数大一个。请注意序列长度是奇数，因此1和0的个数不能相等。
运行属性：m+1长度的运行数是m长度运行数的一半。m长运行是所有1或0的m长位序列。
相关特性：当序列长度接近无穷大时，序列的自相关接近于零。也就是说，如果取序列并将其与在时间上被t个比特移位的自身进行比较，其中t不等于序列长度，则比较相等的比特位置的数目大致等于比较不相等的位置的数目。从本质上说，这意味着序列没有周期子序列。
您可以将代码的结果与这些属性进行比较，并得出自己的结论，即结果如何接近LFSR。
关于algorithm - 天真的LFSR，将编程语言转换为数学，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5368405/