理解Ruby的repeated_permutation方法的源代码
我一直在用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，它使用Ruby 1.8.7，它没有repeat_permutation方法。 我需要用相同的function编写自己的方法。
所以我去了这里找到的源代码： http ： //www.ruby-doc.org/core-1.9.3/Array.html#method-i-repeated_permutation
不幸的是，我不明白他们在做什么，或者我怎么能通过编写自己的方法来解决这个问题。 我对编程很新，但却无法解决这个问题。 任何帮助理解源代码将不胜感激！
您链接的代码调用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开始每次迭代返回一个排列。 ruby版就像
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的所有排列，你可能想把它们放到数组中。
谢谢yngum！
为了扩展您的答案，我重命名了一些变量，使其更具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)