鸟食轩

#1楼 [楼主]   回复  引用  查看    

一位51网友的解决方案，出发点非常的巧妙！

#2楼    回复  引用  查看    

这种方法不失为一种很高速的方法。但并不能达到完全的随机。

例如下面的例子，RandomSort2为连续的三次RandomSort1,结果随机分布得比较均匀，证明RandomSort1的效果并不够好。

<script>
function RandomSort1(arr)
{
for(var i=0;i<arr.length;i++)
{
var p=Math.floor(Math.random()*arr.length);
var v=arr[i];
arr[i]=arr[p];
arr[p]=v;
}
}
function RandomSort2(arr)
{
RandomSort1(arr);
RandomSort1(arr);
RandomSort1(arr);
}

var count=200;
var times=200;


TestRandomSort(RandomSort1);
TestRandomSort(RandomSort2);

function TestRandomSort(RandomSort)
{

var totals=new Array(count);
for(var i=0;i<count;i++)
totals[i]=0;

for(var t=0;t<times;t++)
{
var arr=new Array(count);
for(var i=0;i<count;i++)
arr[i]=i;
RandomSort(arr);
for(var i=0;i<count;i++)
totals[i]+=arr[i];
}

var max=0;
var min=88888888;

for(var i=0;i<count;i++)
{
var v=totals[i];
max=Math.max(v,max);
min=Math.min(v,min);
}

document.write(max+":"+min);
document.write("<br>");
document.write( Math.floor(100*(max-min)/(count*times/2))+"%" )
document.write("<hr>");
}

</script>


在DotNet中，可以生成同样长度的int数组，然后在里面填充随即数，
再用 Array.Sort(Array keys,Array items)来进行排序。

#3楼    回复  引用  查看    

sortFunc的方法相当于Dotnet的IComparer，在DotNet下用这个方法会很容易抛出错误。因为两个item比较的结果应该是一致的，而不是随机的。
另外，如果把sortFunc的方法放到上面的例子去测试，结果分布得更不平均。

#4楼 [楼主]   回复  引用  查看    

这个排序本身就不遵循均匀分布的，因为每个元素被处理的随机概率都不同，第一个元素的随机概率(被移动的概率)是：1/100，第二个是：1/100*1/99，第三个是：1/100*1/99*1/98，...，第100个是1/100*1/99*...*1/1。

#5楼    回复  引用  查看    

可以考虑这个没有这么高效的方法，
模仿DotNet的Array.Sort:

function RandomSort1(arr)
{
var len=arr.length;
var keys=[];
for(var i=0;i<len;i++)
{
keys[i]=Math.random();
}
SortByKeys(keys,arr);
}
function SortByKeys(keys,items,optionalComparer)
{
var len=keys.length;//assert len==items.length;
var pairs=[];
for(var i=0;i<len;i++)
{
pairs[i]={k:keys[i],v:items[i]};
}
if(optionalComparer)
pairs.sort( sortfunc1 );
else
pairs.sort( sortfunc2 );
function sortfunc1( x , y )
{
return optionalComparer(x.k,y.k);
}
function sortfunc2( x , y )
{
return x.k-y.k;
}
for(var i=0;i<len;i++)
{
items[i]=pairs[i].v;
}
}

#6楼 [楼主]   回复  引用  查看    

这个映射法太复杂了，不过理论上和random具有相同的分布效果:)

#7楼    回复  引用    

hehe,牌类游戏中常用的换位算法，其原理其实就是模拟了洗牌的过程。
采用了数组元素交换的方法，以此交换一个元素。其实如果要求更真实,可以采用一次交换特定数量的连续元素，这样更接近人类的洗牌模式。

#8楼    回复  引用    

补充：按照统计学，连续7次洗牌可以达到最佳效果（完全破坏原有次序）。

#9楼    回复  引用  查看    

@江千帆
没有对每次洗牌作限制吗？"完全破坏原有次序"是个不严谨的说法，什么叫完全破坏？没有两张牌的位置和洗牌前相同？还是说7次洗牌后牌的呈何种随机分布?!

#10楼    回复  引用    

一个得到全排列的算法，这里演示了得到4个元素的全排列
而且得到其中每一个元素的时间都相同，算法复杂度为O(n)，然后就可以通过随机数算法得到一个0到元素全排列总数-1的整数，之后将元素数组和该随机数传入sequence方法中，就可以返回一个随机的排列了。
可以将此算法改成可以计算超大数的商，余，以便应用于洗牌（因为54的全排列实在太大了）
private void button1_Click(object sender, System.EventArgs e)
{
string result="";
string []sl= {"A1","A2","A3","A4"};
for(int i=0;i<24;i++)
{
ArrayList il = sequence(sl,i);
foreach(string s in il)
{
result+= s+ " ";
}
result += "\n";
}
MessageBox.Show(result);
}

public static ArrayList sequence(IList seq,long index)
{
int seqc = seq.Count;
int divider = 2;
ArrayList result = new ArrayList();
result.Add(seq[0]);
for(int i=1; i<seqc; i++)
{
int new_index = Convert.ToInt32(index % divider);
index = index/divider;
result.Insert(new_index,seq[i]);
divider ++;
}
return result;
}
---------------------------
返回结果
---------------------------
A4 A3 A2 A1
A4 A3 A1 A2
A4 A2 A3 A1
A4 A1 A3 A2
A4 A2 A1 A3
A4 A1 A2 A3
A3 A4 A2 A1
A3 A4 A1 A2
A2 A4 A3 A1
A1 A4 A3 A2
A2 A4 A1 A3
A1 A4 A2 A3
A3 A2 A4 A1
A3 A1 A4 A2
A2 A3 A4 A1
A1 A3 A4 A2
A2 A1 A4 A3
A1 A2 A4 A3
A3 A2 A1 A4
A3 A1 A2 A4
A2 A3 A1 A4
A1 A3 A2 A4
A2 A1 A3 A4
A1 A2 A3 A4

---------------------------

#11楼    回复  引用    

有谁能提供VB的语句

#12楼    回复  引用    

有那位网友， 能提供 vb6。0 随机排序

#13楼    回复  引用    

Math.random()是基于系统时间（作为参数）产生随机数的，如果不喜欢用random，直接用系统时间的某个算式（例如用数组长度求余，然后移除被选中的数组元素）也可以达到同样的效果，当然效率的话就不突出（不过Math.random()本身就是一个高消耗的函数，调用它的话也不能说有多高效,代码行数少和高效毕竟还不是一个概念），但是应该比映射算法不差吧。

#14楼    回复  引用    

如果是非安全用途没有必要对每个数都去一次随机数进行新位置计算，因为取随机数用了乘法，不是最省计算量的。完全可以先生成一个随机数K，排序时用K和索引及键值（原值的或替换值）组合一些位运算来达到每次都是“随机”的K，总体计算量低多了，特别适合很大的数组随机排序。不过那个取模的算法还没想出替代方案，就剩下这个耗CPU多些。

seed=9876543210;
key = Math.random()*seed;
function Shuffle(ary)
{
for ( var i=ary.length-1 ; i >= 0 ; i-- )
{
var v = (key)%ary.length;
var tmp = ary[v];
ary[v] = ary[i];
ary[i] = tmp;
key = (key^i)||tmp;
}
return ary;
}

#15楼    回复  引用    

C#:

private void button2_Click(object sender, System.EventArgs e)
{
arrInt = InitArray(1,100000);
arrInt = RandomSort(arrInt);
System.Text.StringBuilder sb = new System.Text.StringBuilder();
for( int i = 0; i < arrInt.Length-1; i++ )
{
sb.Append(arrInt[i].ToString() + "\r\n");
}
textBox1.Text = sb.ToString();
sb = null;
}

public int[] RandomSort(int[] arr)
{
int k = arr.Length-1; // 要保存的位置
Random rad=new Random();
for( int i = 0; i < arr.Length-1; i++ ) // 执行N-1次循环，随机产生要被打乱的数据所在的位置
{
int idx = rad.Next(0,k+1);
// 交换数据
int n = arr[idx];
arr[idx] = arr[k-1];
arr[k-1] = n;
// 递减要保存的位置
k--;
}
return arr;
}

int[] arrInt = null;
private int[] InitArray(int min, int max)
{
arrInt = new int[max - min];
for(int i = min; i < max; i++)
{
arrInt[i-min] = i;
}
return arrInt;
}
我用了十万，速度也很快。

#16楼    回复  引用    

可以在这里看一下,我的结果
http://www2.webng.com/efme/123.asp