4

我正在尝试找到一种方法来为 y 长度的 x 值生成唯一排列。我想要做的是：

[0,1].unique_permutations(15)
# => [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
#     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
#     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
#     ... massive snip
#     [1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1],
#     [1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1],
#     ... massive snip
#     [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
#     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],

需要明确的是，我知道这是可能的：

[0, 0, 0, 1, 1, 1].permutation.count
# => 720
[0, 0, 0, 1, 1, 1].permutation.to_a.uniq.count
# => 20

但这与我正在寻找的并不完全相同，并且对于长列表而言，性能变得不切实际：

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1].permutation.count
# => 479001600 (after a long wait...)
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1].permutation.to_a.uniq.count
# => 1 (didn't actually run this - answer is obvious)

我能找到的最接近的是python 的这个答案，但遗憾的是我不知道 python 并且不能完全弄清楚如何将它移植到 Ruby。

我确信还有其他算法可以解决这类问题，但我真的很想把它保留在 Ruby 中。

4

4 回答 4

8

您正在寻找的是n集合与自身的 -ary 笛卡尔积（在您的示例中具有n = 15过度集[0, 1]。）这与#permutation您稍后在问题中引用的列表不同。

此列表的大小随 呈指数增长n。对于所有人n来说，实际上实现它是不切实际的。您可以改用生成器（请原谅我生锈的红宝石）：

class Array
  def cartesian_power(n)
    current = [0] * n
    last = [size - 1] * n

    loop do
      yield current.reverse.collect { |i| self[i] }
      break if current == last

      (0...n).each do |index|
        current[index] += 1
        current[index] %= size

        break if current[index] > 0
      end
    end
  end
end

然后：

>> [0, 1].cartesian_power(3) { |l| puts l.inspect }
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]
=> nil

>> %w{a b c}.cartesian_power(2) { |l| puts l.inspect }
["a", "a"]
["a", "b"]
["a", "c"]
["b", "a"]
["b", "b"]
["b", "c"]
["c", "a"]
["c", "b"]
["c", "c"]
=> nil
于 2013-04-01T03:37:58.510 回答
2

这里有一个想法——对于这个[0,1]集合，你可以从二进制的 0 开始计数，然后简单地插入前导零，直到你有一个长度为 15 的字符串。

n = 15
max = ('1' * n).to_i(2)

(0..max).map do |i|
  i.to_s(2).rjust(n).gsub(" ","0")
end

这个结果几乎是瞬间返回排列后的字符串；将它们转换为整数数组（添加.split('').map(&:to_i)到块中）需要一两秒钟。

这不是一个包罗万象的解决方案（它假定源数组的每个元素至少出现n一次），但它适用于您的示例。它也应该可以转换为其他数字基数（我认为您可以在 Ruby 中达到基数 36）。

编辑：好吧，由于它们的大小，其他数字基础可能效果不佳。但是它们应该让您知道您正在寻找多少独特的排列；例如，长度为 15 的 3 个元素 = 14,348,906，4 个元素是 1,073,741,823（也许更熟悉数学的人可以证实这一点）。

于 2013-04-01T03:17:06.550 回答
2

递归解决方案可能如下所示（伪代码，因为我的 Ruby 不是很好）：

unique_permutations(n,values) {
    if (n == 0) {
        return EmptyList
    } else {
        lst = unique_permutations(n-1,values)
        newList = EmptyList
        for i in values {
            for j in lst {
                newList.append(prependElementToList(i,j))
            }
        }
        return newList
    }
 }

然后可以调用unique_permutations(15,[0,1])

于 2013-04-01T03:29:17.247 回答
-1

对于任何仍然在此绊脚石的人。从 ruby​​ 1.9.2 开始，Array#repeated_permutations也是如此。

1.9.2-p320 :056 > 

puts %w(a b c).repeated_permutation(2).map(&:inspect)
["a", "a"]
["a", "b"]
["a", "c"]
["b", "a"]
["b", "b"]
["b", "c"]
["c", "a"]
["c", "b"]
["c", "c"]
 => nil 
1.9.2-p320 :057 >
于 2015-01-16T22:02:34.220 回答