生成对象数组重复排列的过滤子集（给定长度 k）

Question

我是 Ruby 的新手。我需要根据长度生成对象的所有组合。

例如array = [obj1, obj2, obj3]、length = 2，则组合为：

[
  [obj1, obj1],
  [obj1, obj2],
  [obj1, obj3],
  # ...
  [obj3, obj3]
]

我知道我可以使用 repeated_permutation 方法来解决这个问题，但我还需要能够过滤一些排列。例如，要过滤掉 2 个相同对象一个接一个的排列，即像这样 [obj1, obj1].

Answer 1

通过您执行 "filtering" 的街区。因此，要删除那些具有相同元素的元素，您可以使用：

a = [1,2,3]
a.repeated_permutation(2).reject { |permutation| permutation.uniq.one? }
#=> [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

Answer 2

如果您只需要删除属于同一对象的任何对，您可以简单地使用 permutation 方法。

arr = [1,2,3]
arr.permutation(2).to_a

#=>  [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

Answer 3

给定一个任意输入数组：

a = [1, 2, 3, 3, 4]

如果您只希望生成独特的排列，那么您可以简单地做：

a.uniq.permutation(2)

（如果您知道初始数组包含唯一元素，则不需要 uniq！）

但是，作为更通用的解决方案，您必须这样做：

a.repeated_permutation(2).reject { |permutation| ** FILTER RULE GOES HERE ** }

因此，例如，如果您希望过滤所有没有两个连续重复值的结果，那么您可以这样做：

a.repeated_permutation(2).reject do |permutation|
  permutation.each_cons(2).any? {|x, y| x == y}
end

把这个发挥到极致，这里有一个通用的方法：

def filtered_permutations(array, length)
  array.repeated_permutation(length).reject{|permutation| yield(permutation)}
end

# Or, if you prefer:

def filtered_permutations(array, length, &block)
  array.repeated_permutation(length).reject(&block)
end

# Usage:

a = [1, 2, 3, 3, 4]

filtered_permutations(a, 2) {|permutation| permutation.each_cons(2).any? {|x, y| x == y} }

# Or, if you prefer:
filtered_permutations(a, 2) {|permutation| permutation.each_cons(2).any? {|consecutive| consecutive.uniq.one?} }

生成对象数组重复排列的过滤子集（给定长度 k）

Generate a filtered subset of repeated permutations of an array of objects (with given length k)

ruby

algorithm

permutation