-1

我需要测试两个数组是否相等，每个数组包含 8 个整数项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 将是少数几个值之一，因此可以在测试之前标准化一次，而每个 permutation2 都是唯一的。

但这太慢了！有没有更好的方法来解决这个问题，也许使用相同的方法但避免使用散列作为键？还是完全不同的方法？

编辑：为了澄清一点，如果您可以替换 ONE 数组中的每个数字或数字的子集，则应将两个数组视为相等，以便每个原始数字映射到一个唯一的新数字（即 1 => 3、3 => 4, 4 => 2, 2 => 1 等），然后这两个数组实际上是相同的。因此，重要的不是值（它们可以是七种不同的颜色或单词，就像数字一样容易），而是值的模式。

EDIT2：应用于 3 位数组的原理意味着：

[1,1,1] 匹配所有项目都相同的任何数组，

[1,2,3] 匹配所有项目不同的任何数组，

[1,1,2] 匹配任何前两项相同而第三项不同的数组，

[1,2,1] 匹配第一个相同且第三个但不是第二个的任何数组，

[1,2,2] 匹配第二个和第三个相同但第一个不同的任何数组，

任何三项数组都将匹配这 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 回答
1

您可以通过这种方式重新制定匹配算法：

如果两个排列具有相同数量的元素并且它们每个元素的表示对象相等，则认为它们相等。表示的对象（或值）是一组唯一对象中的一个，这些对象按其出现的顺序分配给原始排列元素。对于两种排列，唯一对象的集合是相同的。

示例：您从 2 组 8 个整数 (1..8) 开始并比较 8 种颜色的两个排列。

for each color in both permuations
  find the color in their associated set, use the index in the set as representation
  if not found insert in the next free place and use this place's index as representation
  if representation1 != representation2 return false
continue with next element
return true

主要问题是插入一个排列元素，然后很快找到它。这就是您必须创建哈希映射的原因。如果您有固定（和少量）数量的元素，则一种可能的优化是使用两个固定长度的排列数组，它们可以在每个条目中保存一个排列元素。使用这些数组中的索引作为表示的对象。您需要线性搜索来查找数组中的排列，但是只有一小部分（如提到的 8 个）这就像在循环中比较 8 个指针/整数，这应该非常快，当然不会慢于哈希图查找。但是您保存了中间对象的创建。

但是，我自己并没有对此进行任何验证。

于 2013-04-25T12:04:06.257 回答