ruby - 在 Ruby 中生成唯一的排序分区

Question

我正在尝试生成如下所示的序列集，没有任何特定的顺序，但这里显示为降序。请注意，每个序列也会下降，因为我对组合感兴趣，而不是排列。我想将每个序列存储为一个数组......或者更优选地将序列集存储为一个数组数组，但首先是第一件事。

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

Answer 1

这是一个解决方案:

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