尝试在 Ruby 中创建一个方法，以使用递归返回数组的所有可能组合（不是内置的组合/排列等方法）

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

这个问题似乎与帮助中心中定义的范围内的编程无关。

2 年前已关闭。

Answer 1

您可以按如下方式进行操作。

def recurse(first, *rest)
  return [[first], rest] if rest.empty?
  recurse(*rest).flat_map { |a| [a, [first] + a] }
end

​arr = [1,2,3,4,5]

a = recurse(*arr)
  #=> [[5], [1, 5], [2, 5], [1, 2, 5], [3, 5], [1, 3, 5], [2, 3, 5],
  #    [1, 2, 3, 5], [4, 5], [1, 4, 5], [2, 4, 5], [1, 2, 4, 5], [3, 4, 5],
  #    [1, 3, 4, 5], [2, 3, 4, 5], [1, 2, 3, 4, 5], [], [1], [2], [1, 2],
  #    [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4], [1, 2, 4],
  #    [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]

a.sort
  #=> [[],
  #    [1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5],
  #    [1, 2, 3, 5], [1, 2, 4], [1, 2, 4, 5], [1, 2, 5], [1, 3],
  #    [1, 3, 4], [1, 3, 4, 5], [1, 3, 5], [1, 4], [1, 4, 5], [1, 5],
  #    [2], [2, 3], [2, 3, 4], [2, 3, 4, 5], [2, 3, 5], [2, 4], [2, 4, 5], [2, 5],
  #    [3], [3, 4], [3, 4, 5], [3, 5],
  #    [4], [4, 5],
  #    [5]]

请参阅Enumerable#flat_map。

---

---

理解递归的最佳方法是在代码中添加一些 put 语句，并在视觉上分隔方法的每个实例。这可以在这里完成，如下所示。

INDENT = 6
def indent; $col += INDENT; end
def undent; $col -= INDENT; end
def pu(s); puts "#{" "*$col}#{s}"; end 
def puhline; pu('-'*(65-$col)); end

def recurse(first, *rest)
  indent
  puhline    
  pu "recurse called with arguments first = #{first}, rest = #{rest}"
  if rest.empty?
    c =  [[first], rest]
    pu "returning #{c}"
    puhline    
    undent
    return c
  end  
  pu "calling recurse(#{rest})"
  a = recurse(*rest)
  pu "#{a} is returned"
  b = a.flat_map { |a| [a, [first] + a] }
  pu "returning a.flat_map { |a| [a, [#{first}] + a] } = #{b}"
  puhline    
  undent
  b
end

$col = -INDENT
recurse(1,2,3,4)

显示以下内容。请注意，该方法的每个实例执行的计算在下面垂直对齐。

-----------------------------------------------------------------
recurse called with arguments first = 1, rest = [2, 3, 4]
calling recurse([2, 3, 4])
      -----------------------------------------------------------
      recurse called with arguments first = 2, rest = [3, 4]
      calling recurse([3, 4])
            -----------------------------------------------------
            recurse called with arguments first = 3, rest = [4]
            calling recurse([4])
                  -----------------------------------------------
                  recurse called with arguments first = 4, rest = []
                  returning [[4], []]
                  -----------------------------------------------
            a = [[4], []] is returned
            returning a.flat_map { |a| [a, [3] + a] } = [[4], [3, 4], [], [3]]
            -----------------------------------------------------
      a = [[4], [3, 4], [], [3]] is returned
      returning a.flat_map { |a| [a, [2] + a] } = [[4], [2, 4], [3, 4], [2, 3, 4], [], [2], [3], [2, 3]]
      -----------------------------------------------------------
a = [[4], [2, 4], [3, 4], [2, 3, 4], [], [2], [3], [2, 3]] is returned
returning a.flat_map { |a| [a, [1] + a] } = [[4], [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4], [], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
-----------------------------------------------------------------