ruby – 大型套装的独特排列

发布时间：2020-12-17 04:00:58 所属栏目：百科来源：网络整理

导读：我正试图找到一种方法来为y长度的x值生成唯一的排列.我想要做的是： [0,1].unique_permutations(15)# = [[0,0],# [0,1],1,# ... massive snip# [1,# [1,# ... massive snip# [0, 要清楚,我知道这是可能的： [0,1].permutation.count# = 720[0,1].permutation

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

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

要清楚,我知道这是可能的：

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

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

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

我能找到的最近的东西是this answer for python,但遗憾的是我不知道python并且无法弄清楚如何将它移植到Ruby.

我确定这类问题还有其他算法,但我真的很想把它保存在Ruby中.

解决方法

你正在寻找的是一组自身的n-ary笛卡尔乘积(在你的例子中,n = 15超过set [0,1].)这与你后面引用的#permutation列表不同.题.

此列表的大小随n呈指数增长.除了微小的n之外,实际实现它是不切实际的.你可以改用发电机(原谅我生锈的ruby)：

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,1]
[0,1]
[1,0]
[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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!