关于不重复随机取值的问题

Question

有一字符串mystr,比如其值为"abcdefghijklmnopqrstuvwxyz",我现在希望从中随机抽出5个不重复的字符,组成一个新的字符串num,不知如何以最高的效率来执行.下面是我写的代码,总觉得执行效率不够,因为temp不停地重新分配其值,可能影响速度.var
  k:integer;
  mystr,temp:,num:string;begin
  mystr:='abcdefghijklmnopqrstuvwxyz';
  temp:=mystr;
  num:=stringofchar(' ',5);
  randomize;  for k:=1 to 5 do
    begin
      n:=random(length(temp))+1;
      num[k]:=temp[n];
      delete(temp,n,1);
    end;end;

Answer 1

不如先在 mystr 中遍历一遍 获取相同的字符的下标 保存到一个容器里
可以用 二分 或者 冒泡。。复杂度。。寒 忘记了。。 n * log2(n) 还是什么的。。然后你只要对随机产生的数<下标去比较就好>与你保存相同的下标中比较...

Answer 2

是的,我通过对temp长度的变短排除,来得到5个不同的随机值。如果不这样，就有可能取的5个随机数中出现重复值。

Answer 3

random函数只能取一个值，如果能一次取若干个不同值就好了，比如 random（100，5）能一下子从0-99之间随机取5个值出来，这样就好喽，呵呵

Answer 4

算了,学统计的大哥来帮你.
我这个方法,可能语句会更多.
但实际上不操作字符串可能会好一些.
1.生成n个随机数,第n个随机数表示第n个字符
2.将n个随机数排序,我想一般你自己的工程里会有一个数组排序的过程.这样就不用写新的,不过排序时要记录原来的序号nth.
3.取排好序的前5位,或者5位
4.用这5个随机数代表的5个位的字符连接起来.

Answer 5

1.生成n个随机数,第n个随机数表示第n个字符
2.将n个随机数排序,我想一般你自己的工程里会有一个数组排序的过程.这样就不用写新的,不过排序时要记录原来的序号nth.
3.取排好序的前5位,或者5位
4.用这5个随机数代表的5个位的字符连接起来.生成的n个随机数中，极可能出现重复的，排序后就可能出现 1123344555..这样取前5个还是不行呀？

Answer 6

算了,兄弟,我想了一下这种正规的方法效率也不高.
只有5位就干脆这样来
建立一个5位的数组,
自动生成随机数,
每生成一个就和数组里的数比较.
如果有相同的就再生成下一个数,
如果不相同就存入数组,直到找到5个不同的数
这样的效率从概率上讲应该还行.
因为不知道delete的效率如何所以我也不能说是否比你的好不过应该是可行的.

Answer 7

老兄
你这就不对了生成重复的随机数是有可能的
但是根据随机数排序的次序是一定的.
而且我最后的说取值不是按随机数取,
是按随机数代表的n来取.
比如 'abcd' 生成 3,6,8,6;你的排序当然是看你用的什么法,但是反正结果一定是非二值的.
你排序后就成了8663,也就是cbda

Answer 8

你主要避免重新分配内存以及避免调用一些隐含的string操作就可以了
var
  k, l: integer;
  mystr,temp:,num:string;
  ptemp, pnum: PChar;
begin
  mystr:='abcdefghijklmnopqrstuvwxyz';
  temp:=mystr;
  num:=stringofchar(' ',5);
  randomize;  ptemp := Pointer(temp);
  pnum := Pointer(num);  l := Length(mystr);  for k := 1 to 5 do
  begin
    n := random(l);
    pnum^ := ptemp[n];    if n <> (l-1) then
      ptemp[n] := ptemp[l-1];
    dec(l);
    inc(pnum);
  end;
end;上面这样写的前提是temp和num必须是临时变量，而且没有复制给别的字符串

Answer 9

还有就是如果mystr是通过参数传递进来的话，应该在ptemp := Pointer(temp);
之前调用一下UniqueString(temp);

Answer 10

用COM的GUID不正是解决的好方案吗.只要不超过128个的数字,就可以用这个方法.
在DELPHI的Comobj程序单元中定义了一个方法CreateClassID程序.例如需要前8位.GUID前8位是在COM产生新的GUI值时是最容易变化的.
加入单元文件:ComObj
procedure Tform.GetID(var sJID:olevariant);
begin
  sJID:=CreateClassID;
  sJID:=copy(sJID,2,8);
end;

Answer 11

算知字符串mystr长度N,取4次
for a:=1 to 4 do
  begin
   temp:=mystr[random(n+1-a)+1];
  mystr[random(n+1-a)+1]:=mystr[n+1-a];
  mystr[n+1-a]:=temp
  end 意思就是  你从N个字符中取4个
第一次，是N选1，并将选出的数和第N个交换
第二次   是N－1选1（不含最后一个），并将选出的数与第N-1个交换。
第三次   是N-2选1（不含最后两个）， 并将选出的数与第N-2个交换。
第四次   是N-3选1 （不含最后三个），并将选出的数与第N-3个交换这就选完了，输出时  从第N个倒着输出4个，就是你选中的字符，同时输出顺序就是你选中的顺序。

Answer 12

晕 上面写错了  是
for a:=1 to 4 do
  begin
  m:=random(n+1-a)+1 
  temp:=mystr[m];
  mystr[m]:=mystr[n+1-a];
  mystr[n+1-a]:=temp
  end

Answer 13

楼上的兄弟程序想法不错，从简洁来讲是不错的，但是从效率上讲，和楼主的delete可能效果差不多，而且步骤好象还多一些。

Answer 14

楼主的算法和我用的原理是一样的~
主要是看delete()函数的效率。
在求字符随机位置的时候楼主不防改用数组求。
效率比字符串高~用数组求随机数的时候
可以用for()把数组从新赋值，或者用链表来实现
来代替delete()的功能~
链表删除原来位置快，找位置慢，
我觉得用数组找随机位置，再用结果找字符，
比用delete 效率高.....
别的算法不见得比这个效率高。

Answer 15

以上说的“用数组找随机位置”的意思是：
用数组来代替delete的功能，来改变每次取数后的数组内容。
个人觉得字符串操作比较慢.

Answer 16

谢谢朋友们的指点!我大家的启发下,我作了如下改进,速度快多了!
label 
  88;
var
  k,p,t:integer;
  mystr,num:string;begin
  mystr:='abcdefghijklmnopqrstuvwxyz';
  num:=stringofchar(' ',5);
  randomize;  for k:=1 to 5 do
    begin
      n:=random(length(mystr))+1;
      
      //在字符串中检查，如果已经取过，则取其后面一个值；
      for p:=n to length(mystr) do
        if mystr[p]<>' ' then 
           begin
             n:=p
             goto 88;
           end;      for p:=1 to n-1 do
        if mystr[p]<>' ' then
           begin
             n:=p
             goto 88;
           end;88:   num[k]:=mystr[n];
      mystr[n]:=' ';
    end;end;