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を与えるシーケンスのセット）。したがって、これを再帰的に実行できるはずです。

私は次のようにコーディングしようとしました（そして、はい、これは私の最初の言語であり、はい、私は約1週間しか勉強していないので、すべてが台無しになっていると確信しています）が、これまでのところ運がありません。再帰の核心を機能させ、すべてのオブジェクトの値を画面に表示して、行ごとにトレースできるようになれば、先に進むことができると思いますが、ロジックと構文の間では、じっとしている。

私の論理は次のとおりです。

  • 対象となる合計を表す「count」を渡すメソッドを定義します。
  • 与えられた値のシーケンスを保持する配列を作成します
  • 配列内の位置を表すインデックスを作成します（ゼロ位置を無視します）。
  • 'delta'を定義し、それを' count'の値に初期化し、配列の残りの残りのターゲット合計を表すようにします。（最初は配列に何もないため、デルタはカウントと同じです。）

次に、1から始まり、明らかに可能な最大値で終わるシーケンスの次の（最初の）値の可能性を循環します。これは「count」自体の値です。サイクル内の各値の新しいデルタを決定します。

デルタが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
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 に答える