1

我有以下代码：

def shuffle arr
  shuffled = []
  while arr.length > 0
    randNum = rand(arr.length)
    idx = 0
    unshuf = []
    arr.each do |item|
      if idx == randNum
        shuffled.push item
      else
        unshuf.push item
      end
      idx = idx + 1
    end
    arr = unshuf
  end
  return shuffled
end

puts(shuffle([ 11, 12, 13]))

我试图在调用unshuf该方法时了解数组的状态。每次调用方法之前shuffle，数组都会被重置为空数组。在这样的实施下，下一轮条件下推入的数字是如何保留的？unshufeachunshufif

4

3 回答 3

3

代码是这样工作的：

  • 创建一个空数组，将存储最终结果。

  • 获取一个介于 0 和初始数组占用之间的随机数。

  • 将 indexcounter 初始化为零。
  • 创建一个未洗牌的空数组。
  • 循环遍历初始数组
    • 将每个项目推到未洗牌的数组中，
    • 除了 indexcounter == 随机数的那个，它进入结果数组
    • 同时保留一个索引计数器。
  • 将未洗牌的数组重命名为初始数组。
  • 从第 2 步开始重复，直到初始数组为空。

不用说，这很笨拙。而且它是用一种非常非Ruby的方式编写的，保持手动索引并使用变量名，如randNum. 这也差不多：

def shuffle(arr)
  dup = arr.dup
  arr.size.times.map do # actually arr.map would work
    dup.slice!(rand(dup.size))
  end
end

但正如其他人所提到的，[1,2,3].shuffle是标准的 Ruby。

于 2012-12-30T23:24:15.147 回答
2

我不知道你从哪里得到上面的代码。Ruby Array#shuffle 方法调用#shuffle！本机方法rb_ary_shuffle_bang，其内容如下：

static VALUE
rb_ary_shuffle_bang(int argc, VALUE *argv, VALUE ary)
{
  VALUE *ptr, opts, *snap_ptr, randgen = rb_cRandom;
  long i, snap_len;

  if (OPTHASH_GIVEN_P(opts)) {
    randgen = rb_hash_lookup2(opts, sym_random, randgen);
  }
  if (argc > 0) {
    rb_raise(rb_eArgError, "wrong number of arguments (%d for 0)", argc);
  }
  rb_ary_modify(ary);
  i = RARRAY_LEN(ary);
  ptr = RARRAY_PTR(ary);
  snap_len = i;
  snap_ptr = ptr;
  while (i) {
    long j = RAND_UPTO(i);
    VALUE tmp;
    if (snap_len != RARRAY_LEN(ary) || snap_ptr != RARRAY_PTR(ary)) {
      rb_raise(rb_eRuntimeError, "modified during shuffle");
    }
    tmp = ptr[--i];
    ptr[i] = ptr[j];
    ptr[j] = tmp;
  }
  return ary;
}

在这里，您可以看到正确的洗牌方法。忽略上面代码的上半部分，注意只是while循环，它从上到下遍历数组，总是从索引下面的部分i随机选择一个元素，并将其移动到当前位置i，继续 decremented i。它的复杂性是 O(n) in n = 数组的长度，因为它应该用于洗牌。

然而，您书中的代码的工作方式完全不同：它总是rand( arr.length )从数组中选择一个元素 ( )，然后遍历数组以查看何时遇到具有该索引的元素，复杂度为 O(n**2/2) . 您的代码还提供了使用#push方法的一个很好的示例，尽管#<<已经足够了，因为每次只推送一个元素。idx您的代码给出了在each循环内手动维护索引的坏例子。#each_with_index应该改用方法。当然，在演示之外，应该完全放弃内部循环，而应该使用类似于本机#shuffle方法的方法。

于 2012-12-30T22:33:26.630 回答
1 
def shuffle arr
  shuffled = []

  while arr.length > 0
    randNum = rand(arr.length)

    idx = 0
    unshuf = []

    print '--- arr='; p arr # <--------
    arr.each do |item|
      if idx == randNum
        shuffled.push item
      else
        unshuf.push item
      end
      print 'shuffled='; print shuffled; print ', unshuf='; p unshuf # <--------
      idx = idx + 1
    end

    arr = unshuf
  end

  return shuffled
end

p shuffle([ 11, 12, 13, 14, 15])

执行 ：

$ ruby -w t.rb 
--- arr=[11, 12, 13, 14, 15]
shuffled=[], unshuf=[11]
shuffled=[], unshuf=[11, 12]
shuffled=[13], unshuf=[11, 12]
shuffled=[13], unshuf=[11, 12, 14]
shuffled=[13], unshuf=[11, 12, 14, 15]
--- arr=[11, 12, 14, 15]
shuffled=[13, 11], unshuf=[]
shuffled=[13, 11], unshuf=[12]
shuffled=[13, 11], unshuf=[12, 14]
shuffled=[13, 11], unshuf=[12, 14, 15]
--- arr=[12, 14, 15]
shuffled=[13, 11, 12], unshuf=[]
shuffled=[13, 11, 12], unshuf=[14]
shuffled=[13, 11, 12], unshuf=[14, 15]
--- arr=[14, 15]
shuffled=[13, 11, 12, 14], unshuf=[]
shuffled=[13, 11, 12, 14], unshuf=[15]
--- arr=[15]
shuffled=[13, 11, 12, 14, 15], unshuf=[]
[13, 11, 12, 14, 15]

解释： 的内容arr在 shuffled 和 unshuf 之间随机分布。然后 unshuf 替换 arr ，如果 unshuf 中有什么东西，while 循环会随机重新分配一点点 shuffle，一点点 unshuf。依此类推，直到 unshuf 为空。所以 shuffled 逐渐填充从arr最初给方法的参数中随机获取的元素shuffle，但arr也通过只保留 unshuf 元素逐渐清空arr = unshuf。当然，在移入 arr 后，unshuf 必须重置为空数组才能接收新的分布，而 shuffled 必须保持增长。希望很清楚。

于 2012-12-30T23:08:21.220 回答