2

Ruby でインテリジェントな首謀者ゲームを構築しています。私のゲームでは、コンピューターにコード ブレーカーの役割を果たすオプションを選択すると、コンピューターはコード作成者のコードが何であるかを知識に基づいて推測します。

私のアルゴリズムの一部として、コンピューターは最初にすべての可能なコードのリスト全体を調べます。

たとえば、選択できる 6 色 (赤、オレンジ、青、緑、紫、黄) があり、コードが 4 色 (繰り返しが許可されている) で構成されている場合、可能なすべてのコードを表示するには、次のようにします。

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

そしてall_possible_codes、可能なすべてのコードを表す配列で満たされた配列になります。コンピューターは、それぞれの推測からフィードバックを取得するときに、このリストからコードを削除します。

repeated_permutationしかし、次の作業では、メソッドを持たない Ruby 1.8.7 を使用する JRuby 1.6.6 を使用する必要があります。同じ機能を持つ独自のメソッドを作成する必要があります。

だから私はここにあるソースコードに行きました: 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");
        }
    }
    }
}

基本的に、反復ごとに 1 つの順列を返す 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 のすべての順列が出力されました。それらを配列に入れたいと思うかもしれません。

于 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 に答える