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

发布时间：2020-12-17 02:36:17 所属栏目：百科来源：网络整理

导读：我正在尝试生成如下所示的序列集,而不是按任何特定顺序生成,但此处显示为降序.请注意,每个序列也会下降,因为我对组合感兴趣,而不是排列.我想将每个序列存储为数组..或者将序列集更好地存储为数组数组,但首先要做的事情. 6 5 1 4 2 4 1 1 3 3 3 2 1 3 1 1 1 2

我正在尝试生成如下所示的序列集,而不是按任何特定顺序生成,但此处显示为降序.请注意,每个序列也会下降,因为我对组合感兴趣,而不是排列.我想将每个序列存储为数组..或者将序列集更好地存储为数组数组,但首先要做的事情.

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时,后面的数字集合只是给出总数的序列集合换句话说,6(目标总数)-3(第一个数字)= 3(总共3个的序列集).因此,应该能够递归地执行此操作.

我尝试编码如下(是的,这是我的第一语言,是的,我只学习了大约一个星期所以我确定它全部搞砸了)但到目前为止还没有运气.我想如果我能够让递归的核心工作并将所有对象的值放到屏幕上,那么我可以逐行跟踪它,我想我可以继续前进,但是在逻辑和语法之间,我我站着不动.

我的逻辑是：

>定义一个传递’count’的方法,表示目标总数.
>创建一个数组,该数组将包含给定的值序列
>创建一个表示数组中位置的索引(忽略零位).
>定义’delta’并将其初始化为’count’的值,并使其表示数组其余部分的剩余目标总和. (因为最初数组中没有任何内容,delta与计数相同.)

然后,循环查看从1开始的序列的下一个(第一)值的可能性,并且显然以最大可能结束,这是’count’本身的值.确定循环中每个值的新增量.

如果delta为0,则完成此操作,否则将确定此新序列,该序列将给出此新增量.可能还需要将新序列附加到当前序列.

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],1,[3,3],2,[2,[1,1]]

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!