2

我一直在用 Ruby 构建一个智能的 Mastermind 游戏。在我的游戏中，如果您选择让计算机扮演代码破解者的角色，计算机就会有根据地猜测代码制作者的代码是什么。

作为我算法的一部分，计算机首先查看所有可能的代码的整个列表。

例如，如果有 6 种颜色可供选择（红橙蓝绿紫黄）并且代码由 4 种颜色组成（允许重复），那么要查看所有可能的代码，您可以这样做：

valid_colors = %w(red orange blue green purple yellow)
all_possible_codes = valid_colors.repeated_permutation(4).to_a

并且all_possible_codes将是一个数组，其中填充了代表每个可能代码的数组。然后，当计算机从每个猜测中获得反馈时，它会从该列表中删除代码。

然而，接下来我要做的事情需要我使用 JRuby 1.6.6，它使用没有repeated_permutation方法的 Ruby 1.8.7。我需要编写具有相同功能的自己的方法。

所以我去了这里找到的源代码：http ://www.ruby-doc.org/core-1.9.3/Array.html#method-i-repeated_permutation

不幸的是，我不明白他们在做什么，也不明白如何通过编写自己的方法来解决这个问题。我对编程很陌生，无法弄清楚这一点。任何有助于理解源代码的帮助将不胜感激！

4

2 回答 2

2

您链接的代码调用 rpermute0 完成大部分工作，Array.c 中 rpermute0 的源代码是

static void
rpermute0(long n, long r, long *p, long index, VALUE values)
{
    long i, j;
    for (i = 0; i < n; i++) {
    p[index] = i;
    if (index < r-1) {              /* if not done yet */
        rpermute0(n, r, p, index+1, values); /* recurse */
    }
    else {
        /* We have a complete permutation of array indexes */
        /* Build a ruby array of the corresponding values */
        /* And yield it to the associated block */
        VALUE result = rb_ary_new2(r);
        VALUE *result_array = RARRAY_PTR(result);
        const VALUE *values_array = RARRAY_PTR(values);

        for (j = 0; j < r; j++) result_array[j] = values_array[p[j]];
        ARY_SET_LEN(result, r);
        rb_yield(result);
        if (RBASIC(values)->klass) {
        rb_raise(rb_eRuntimeError, "repeated permute reentered");
        }
    }
    }
}

基本上是蛮力，从 0 开始，每次迭代返回一个排列。红宝石版本类似于

require 'pp'

def rpermute(numRepeat, pArray, index, originArray)
  0.upto(originArray.length-1) do |i|
    pArray[index] = i
    if index < numRepeat-1
      rpermute(numRepeat, pArray, index+1, originArray)
    else
      result = Array.new
      0.upto(numRepeat-1) do |j|
        result[j] = originArray[pArray[j]]
      end
     pp result
    end
  end
end

originArray1 = [1,2,3,4,5]
originArray2 = ['a','b','c','d','e']
pArray = []

rpermute(4, pArray, 0, originArray1)
rpermute(4, pArray, 0, originArray2)

我测试了上面的代码，它打印出所有长度为 4 的排列，你可能想把它们放入数组中。

于 2012-08-28T15:54:23.100 回答
0

谢谢英格姆！

只是为了扩展您的答案，我重命名了一些变量以使其更具 Ruby 风格、更清晰、更具描述性和明确性。我还改变了一些东西，所以方法的返回值就是答案，一个包含每个可能排列的数组。

def repeated_permutations(original_array, length_of_each_permutation, list_of_permutations, index_positions, index)
    0.upto(original_array.length - 1) do |index1|
        index_positions[index] = index1
        if index < length_of_each_permutation - 1
            repeated_permutations(original_array, length_of_each_permutation, list_of_permutations, index_positions, index + 1)
        else
            permutation = Array.new
            0.upto(length_of_each_permutation - 1) do |index2|
                permutation[index2] = original_array[index_positions[index2]]
            end 
            list_of_permutations.push(permutation)
        end
    end
    list_of_permutations
end

我不喜欢命名它index_positions，但想不出更好的名字。上述方法将返回一个数组，其中填充了所有可能排列的数组，并允许重复。

实施：

valid_colors = %w(red orange blue green purple yellow) repeated_permutations(valid_colors, 4, [], [], 0)

于 2012-08-28T20:02:12.697 回答