-1

それぞれが integer である 8 つの項目を含む 2 つの配列が等しいかどうかをテストする必要があります1..7。問題は、私が気にかけているのは価値そのものではなく、価値のパターンだということです。たとえば、次のようになります。

eq? [ 1,2,3,4, 5,6,7,1 ], [ 1,2,3,4, 7,6,5,1 ] # => true
eq? [ 1,1,2,2, 3,3,4,4 ], [ 3,3,2,2, 1,1,4,4 ] # => true
eq? [ 1,1,1,1, 2,2,2,2 ], [ 1,1,1,2, 1,2,2,2 ] # => false
eq? [ 1,2,1,3, 4,4,5,6 ], [ 7,5,7,6, 2,2,3,4 ] # => true

! 例を編集したため、最初の引数はすでに標準化されています

注: 配列の真ん中のスペースは読みやすくするためのものです。

そして、私はこれを何百万回も行う必要があります。そこで、以下の方法を思いつきました。

# this method "standardizes" permutation 2 before comparing to permutation1 which is assumed to already be standardized
def eq? permutation1, permutation2
  next_val = 0
  key = Hash.new { |h,k| h[k] = next_val+=1 }
  permutation1 == permutation2.map { |i| key[i] }
end

permutation1 はいくつかの値の 1 つになるため、テスト前に一度標準化できますが、各 permutation2 は一意になります。

しかし、これは遅すぎます！おそらく同じ方法で、ハッシュをキーとして使用しないようにすることで、この問題にアプローチするより良い方法はありますか? それともまったく異なるアプローチですか？

EDIT：もう少し明確にするために、元の各数値が一意の新しい数値にマップされるように、1つの配列の各数値または数値のサブセットを置き換えることができる場合、2つの配列は等しいとみなされます（つまり、1 => 3、3 => 4, 4 => 2, 2 => 1 など)、2 つの配列は実際には同一になります。したがって、重要なのは値 (数字と同じくらい簡単に 7 つの異なる色または単語である可能性があります) ではなく、値のパターンではありません。

EDIT2: 3 桁の配列に適用される原則は、次のことを意味します。

[1,1,1] は、すべての項目が同じである任意の配列に一致します。

[1,2,3] は、すべての項目が異なる任意の配列に一致します。

[1,1,2] は、最初の 2 つの項目が同じで 3 番目の項目が異なる任意の配列に一致します。

[1,2,1] は、最初の配列が同じで、3 番目の配列が 2 番目の配列と一致しない任意の配列に一致します。

[1,2,2] は、2 番目と 3 番目が同じで 1 番目が異なる任意の配列に一致します。

任意の 3 つのアイテムの配列は、これら 5 つのいずれかに一致します。

4

2 に答える 2

4 
def eq? a, b
  (0...a.length).group_by{|i| a[i]}.values ==
  (0...b.length).group_by{|i| b[i]}.values
end

eq?([1,2,3,4,5,6,7,1], [1,2,3,4,7,6,5,1]) # => true
eq?([1,1,2,2,3,3,4,4], [3,3,2,2,1,1,4,4]) # => true
eq?([1,1,1,1,2,2,2,2], [1,1,1,2,1,2,2,2]) # => false
eq?([1,2,1,3,4,4,5,6], [7,5,7,6,2,2,3,4]) # => true
于 2013-04-24T11:44:49.073 に答える