Ruby 问各位一个关于数组的全排列的问题

mlb0903 · October 28, 2013 · Last by crdwin replied at October 29, 2013 · 3374 hits

条件:现在有这样一个数组 [[2,3],[4,5],[6,7],……],小数组中的元素个数不一定是两个元素,它的个数也是不定的。 需求:最后要得到这样一个类似这样的数组 [[2,4,6],[2,4,7],[2,5,6],[2,5,7],……] 我的后台 ruby 代码该怎么写?自己学习 ruby 时间不长,感觉有点混乱。。。

def flatten(arrys)
  if arrys.length == 1
    arrys[0].map{|v| [v]}
  else
    ret = arrys[0].inject([]) do |memo, val|
      flatten(arrys[1..-1]).each do |c|
        memo << c.insert(0, val)
      end
      memo
    end
    ret
  end
end

ret = [[2,3],[4,5],[8,9,10]].permutation.inject([]) do |memo, ps|
  memo += flatten(ps)
  memo
end

ret.each do |r|
  puts r.to_s
end

结果是

[2, 4, 8]
[2, 4, 9]
[2, 4, 10]
[2, 5, 8]
[2, 5, 9]
[2, 5, 10]
[3, 4, 8]
[3, 4, 9]
[3, 4, 10]
[3, 5, 8]
[3, 5, 9]
[3, 5, 10]
[2, 8, 4]
[2, 8, 5]
[2, 9, 4]
[2, 9, 5]
[2, 10, 4]
[2, 10, 5]
[3, 8, 4]
[3, 8, 5]
[3, 9, 4]
[3, 9, 5]
[3, 10, 4]
[3, 10, 5]
[4, 2, 8]
[4, 2, 9]
[4, 2, 10]
[4, 3, 8]
[4, 3, 9]
[4, 3, 10]
[5, 2, 8]
[5, 2, 9]
[5, 2, 10]
[5, 3, 8]
[5, 3, 9]
[5, 3, 10]
[4, 8, 2]
[4, 8, 3]
[4, 9, 2]
[4, 9, 3]
[4, 10, 2]
[4, 10, 3]
[5, 8, 2]
[5, 8, 3]
[5, 9, 2]
[5, 9, 3]
[5, 10, 2]
[5, 10, 3]
[8, 2, 4]
[8, 2, 5]
[8, 3, 4]
[8, 3, 5]
[9, 2, 4]
[9, 2, 5]
[9, 3, 4]
[9, 3, 5]
[10, 2, 4]
[10, 2, 5]
[10, 3, 4]
[10, 3, 5]
[8, 4, 2]
[8, 4, 3]
[8, 5, 2]
[8, 5, 3]
[9, 4, 2]
[9, 4, 3]
[9, 5, 2]
[9, 5, 3]
[10, 4, 2]
[10, 4, 3]
[10, 5, 2]
[10, 5, 3]

如果你不需要数组的数组本身的全排列则去掉 permutation 那一步。

大致想了下,方法可能比较笨。需要你多测试下,看是否是你想要的结果:

module ArrayDeepRecursion
  def deep_recursion
    return self if size < 2

    collect do |_|
        prefix_arr, suffix_arr = shift(2)
        result_arr = prefix_arr.zip.inject([]) { |tmp_arr, prefix| 
            tmp_arr << suffix_arr.zip.map { |suffix| (prefix + suffix).flatten } 
        }.flatten(1)
        return result_arr if size == 0

        unshift(result_arr)
        deep_recursion
    end
  end unless Array.method_defined?(:deep_recursion)
end
Array.send(:include, ArrayDeepRecursion)

测试结果:

arr = [[2,3],[4,5],[8,9,10]]
arr.deep_recursion
=> [[2, 4, 8], [2, 4, 9], [2, 4, 10], [2, 5, 8], [2, 5, 9], [2, 5, 10], [3, 4, 8], [3, 4, 9], [3, 4, 10], [3, 5, 8], [3, 5, 9], [3, 5, 10]]


arr = [[1, 2], [33, 44, 55], [66, 77, 88, 99]]
arr.deep_recursion
=> [[1, 33, 66], [1, 33, 77], [1, 33, 88], [1, 33, 99], [1, 44, 66], [1, 44, 77], [1, 44, 88], [1, 44, 99], [1, 55, 66], [1, 55, 77], [1, 55, 88], [1, 55, 99], [2, 33, 66], [2, 33, 77], [2, 33, 88], [2, 33, 99], [2, 44, 66], [2, 44, 77], [2, 44, 88], [2, 44, 99], [2, 55, 66], [2, 55, 77], [2, 55, 88], [2, 55, 99]]

没测过性能,不知道性能咋样。期待其他大牛贴上更科学的方法。 PS:会清空原数组:arr

@mlb0903 欢迎提出更好的解决方案。

@mlb0903

中间还有些异常判断没做,比如 arr = [1, 2] 时就会报错,默认你的输入数组 arr 是符合你给的规范的

#4 楼 @zfjoy520 一下是我用的方法 arr=[[],[]……] str= "arr[0]" (1..arr.length-1).each{|i| str+=".product(arr[#{i}])"} str_arr= eval(str) result_arr=[] str_arr.each do |s| resule_arr << s.flatten end

...这种东西显然不用自己实现啊…… http://ruby-doc.org/core-2.0.0/Array.html#method-i-product 你这里用的话…… a[0].product *a[1..-1]

每个 sub array join 成一个 string, string 可以直接排序

#6 楼 @Kabie 长姿势了。没通看过 ruby 的文档,平时都是按需查看。怕看了不用也记不住。呵呵

Unknow user #9 October 29, 2013

取出来的数组,每个元素的长度都是 3,[2,4,6]?不是 [2,4,6,***]?

You need to Sign in before reply, if you don't have an account, please Sign up first.