4

我正在尝试生成如下所示的序列集，不是以任何特别的顺序，但这里显示为降序。请注意，每个序列也会下降，因为我对组合感兴趣，而不是排列。我想将每个序列存储为一个数组..或者将序列集存储为一个数组数组更可取，但首先要做的是。

6                   
5   1               
4   2               
4   1   1           
3   3               
3   2   1           
3   1   1   1       
2   2   2           
2   2   1   1       
2   1   1   1   1   
1   1   1   1   1   1

现在我只是专注于生成这些集合，并且我正在尝试以递归方式进行。本质上..这些都是数字序列，当组合将给出一些总数时..在这种情况下为 6。但请注意，当第一个数字为 3 时，随后的数字集只是给出总数的序列集3. 换句话说，6（目标总数）- 3（第一个数字）= 3（总共为 3 的序列集）。因此，应该能够递归地做到这一点。

我尝试编写如下代码（是的，这是我的第一语言，是的，我只学习了大约一个星期，所以我确信这一切都搞砸了）但到目前为止还没有运气。我想如果我可以让递归的核心工作并将所有对象的值放到屏幕上以便我可以逐行跟踪它，我想我可以继续前进，但是在逻辑和语法之间，我'我处于静止状态。

我的逻辑是：

  • 定义一个传递代表目标总数的“计数”的方法。
  • 创建一个数组，该数组将保存给定的值序列
  • 创建一个表示数组中位置的索引（忽略零位置）。
  • 定义'delta'并将其初始化为'count'的值，并让它代表数组其余部分的剩余目标总和。（由于最初数组中没有任何内容，因此增量与计数相同。）

然后，循环遍历序列的下一个（第一个）值的可能性，从 1 开始，显然以最大值结束，即“count”本身的值。确定循环中每个值的新增量。

如果 delta 为 0，那么您就完成了，否则确定这个新序列将给出这个新的 delta。可能还需要将新序列附加到当前序列。

i=0

    def seq(count)
        cvc=Array.new  # array to hold the number values
        i=i+1  # position index for the array
        puts 'i is ' + i.to_s
        delta=count 
        puts ' delta is ' + delta.to_s

        for value in 1..delta do  # value represents the number value
                cvc[i]=value
                puts 'cvc[i] is ' + cvc[i].to_s
                delta = delta-cvc.sum
                puts 'new delta is '+ delta.to_s
            if delta >1  then count=delta
                    seq(count)
            end
        end
    end
4

1 回答 1

6

这是一个解决方案：

def expand(n, max = n)
  return [[]] if n == 0
  [max, n].min.downto(1).flat_map do |i|
    expand(n-i, i).map{|rest| [i, *rest]}
  end
end

expand(6) # => [[6], [5, 1], [4, 2], [4, 1, 1], [3, 3], [3, 2, 1], [3, 1, 1, 1], [2, 2, 2], [2, 2, 1, 1], [2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]]
于 2012-06-04T23:43:33.217 回答