尝试使用递归在 Ruby 中创建一个方法到 return 数组的所有可能组合（不是像 combination/permutation 这样的内置方法）

Question

我正在学习 Ruby 并且想创建一种方法 returns 使用递归对数组进行所有可能的组合，而不使用组合或排列等内置方法。具体来说，我想将以下 Javascript 代码转换为类似于 Ruby 的代码：

const combinations = (elements) => {
  if (elements.length === 0) return [ [] ];
  const firstEl = elements[0]
  const rest = elements.slice(1);

  const combsWithoutFirst = combinations(rest);
  const combsWithFirst = [];

  combsWithoutFirst.forEach(comb => {
    const combWithFirst = [...comb, firstEl];
    combsWithFirst.push(combWithFirst);
  });

  return [ ...combsWithoutFirst, ...combsWithFirst ];
}

我对编程还很陌生，我仍在努力了解递归，如果有任何帮助，我们将不胜感激！

上面的代码来自这个 youtube 视频：https://www.youtube.com/watch?v=NA2Oj9xqaZQ

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。

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

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]]
-----------------------------------------------------------------

尝试使用递归在 Ruby 中创建一个方法到 return 数组的所有可能组合（不是像 combination/permutation 这样的内置方法）

Trying to create a method in Ruby to return all possible combinations of an array using recursion (not built in methods like combination/permutation)

ruby

recursion