在Ruby中生成唯一的排序分区 [英] Generating unique sorted partitions in Ruby

问题描述

我正在尝试生成如下所示的序列集，虽然顺序没有特别说明，但此处显示为降序序列。请注意，每个序列也会下降，因为我对组合感兴趣，而不是排列。我想将每个序列存储为一个数组。或者最好将序列集存储为一个数组数组，但首先要注意的是。

I'm trying to generate the set of sequences as shown below, not in any particularly order, but here its shown as a descending sequence. Note that each sequence also descends as I'm interested in combinations, not permutations. I'd like to store each sequence as an array..or the set of sequences as an array of arrays more preferably, but first things first.

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的序列集）。因此，应该能够递归地做到这一点。

Right now I am simply focusing on generating these sets and I'm trying to do it recursively. Essentially..these are all the sequences of numbers when combines will give some total..in this case 6. But notice how when the first number is 3, the set of numbers which follows is simply the set of sequences that gives a total of 3. In other words 6(target total) - 3 (first number) = 3 (set of sequences that give total of 3). Thus, should be able to do this recursively.

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

I tried to code as follows (and yes, this is my first language and yes, I've only been studying for about a week so I'm sure its all screwed up) but so far no luck. I think if I can just get the very core of the recursion working and put the values of all the objects to the screen so I can trace it line by line, I think I can move ahead, but between the logic and the syntax, I'm at a stand still.

我的逻辑是：

• 定义a传递 count（代表目标总数）的方法。


• 创建一个将保留给定值序列的数组


• 创建一个表示数组中位置的索引（忽略零位置） 。


• 定义'delta'并将其初始化为'count'的值，并使其代表其余数组的剩余目标总和。 （因为数组最初没有任何内容，所以增量与计数相同。）

• define a method that passes 'count' representing the total being targeted.
• create an array which is going to hold a given sequence of values
• create an index which represents the position in the array (ignoring zero position).
• define 'delta' and initialize it to the value of 'count' and have it represent the remaining target sum of the rest of the array. (since there is nothing in the array initially, the delta is the same as the count.)

然后，循环选择序列的next（first）值，从1开始并以最大可能值结束，即 count本身的值。为循环中的每个值确定新的增量。

Then, cycle through the possibilities for the next(first) value of the sequence starting from 1 and ending, obviously, with the maximum possible, which is the value of 'count' itself. Determine the new delta for each value in the cycle.

如果增量为0，则说明已完成，否则请确定将赋予此新增量的新序列。可能也需要将新序列附加到当前序列上。

If the delta is 0, you are done otherwise determine this new sequence which will give this new delta. Likely need to append the new sequence to the current sequence as well.

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

推荐答案

这是一个解决方案：

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

这篇关于在Ruby中生成唯一的排序分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！