1からnまでの整数を高々1回ずつ用いて作られるm個の数の組のうち，和 がちょうどkになるような組のリストによって構成されたリストを返す関 数 kadai1(n, m, k)を作りたいです．

Question

前提・実現したいこと

Javascriptで，1からnまでの整数を高々1回ずつ用いて作られるm個の数の組のうち，和がちょうどkになるような組のリストによって構成されたリストを返す関数 kadai1(n, m, k)を作りたいです．
これらの組のうち，順番を入れ替えたとき同じになる組は同じものとして，辞書順で一番若いもの，すなわち小さい数から順に大きくなるように並べたものを用いること.さらに 組は辞書順で若いほうから順に並べること．

該当のソースコード

function kadai1(n,m,k){
    var ans = []
    function kadai11(nn,mm,kk){
        if(mm===0&&kk===0)ans=nn
        puts(nn +" "+ mm + " " + kk)
        if(nn==n)return ans
        for(var i=1;i<n+1;i++){
            kadai11(nn+i,mm-1,kk-i)
        }
        
    }
    //kadai11(1,m,k)
    kadai11(1,3,10)
}
kadai1(5,3,10)

試したこと

kadai11(nn, mm, kk)を「nn以上のmm個の数を用いてちょうど和kkを作る」 と定義して，kadai11(*,0,0)となったときにansに１つの解として代入していくように目指しました．

Comments

[y_waiwai]

提示のコードではどういう動作になるんでしょうか。
そしてそれをどういうふうにしたいってことなんでしょう

[jun68ykt]

何らか具体的な n, m, k の入力値に対して、kadai1 が返す期待値の具体例を挙げて頂きたいです。

[Q3fdxrGzWzu0u5n]

掲示のコードでは再帰が終わらず，ansに解が追加されません．
ansにかいを追加して行って，最終的にそれを出力したいです．

具体的な例としては以下のものがあります．
kadai1(5, 3, 10) = [[1,4,5], [2,3,5]]
kadai1(10, 4, 12) = [[1,2,3,6], [1,2,4,5]]

[Lhankor_Mhy]

puts の定義を教えてください。

再帰でやるなら、nn+i が違うだろうなあ……という気がしました。Set あたりを使うのがいいのでは。
あと、kk-i が負数でも呼んでしまうように見えます。

[jun68ykt]

> 具体的な例としては以下のものがあります．
> kadai1(5, 3, 10) = [[1,4,5], [2,3,5]]
> kadai1(10, 4, 12) = [[1,2,3,6], [1,2,4,5]]

具体例ありがとうございます。回答しました。参考になれば幸いです。

Answer 1

kadai11(nn, mm, kk)を「nn以上のmm個の数を用いてちょうど和kkを作る」 と定義して，kadai11(*,0,0)となったときにansに１つの解として代入していくように目指しました．

こういった方針で行くのであれば、今までに使った数を記録しておく必要があります。そのための変数listを追加して、条件を整理すると

function kadai1(n,m,k){
    var ans = []
    function kadai11(list,nn,mm,kk){
        if(mm===0) {
            if (kk === 0) ans.push(list)
            return
        }
        for(var i=nn;i<n+1;i++){
            kadai11(list.concat([i]), i+1,mm-1,kk-i)
        }
    }
    kadai11([],1,m,k)
    return ans
}
console.log(kadai1(5,3,10)) //=> [ [ 1, 4, 5 ], [ 2, 3, 5 ] ]

こんな感じになります。listの使い方と、今の条件との違いが肝なのでよく見比べてほしいと思います。特にどんなパラメーター(もちろん不正なパラメーターは除く)でも無限ループに陥らないようになってるかというのは、重要な観点なので、特に注意して見て欲しいです。

Answer 2

こんにちは
ベストアンサー決定後に失礼します。

lodash.combinations を使います。

const kadai1 = (n, m, k) =>
  _.combinations([...Array(n)].map((_x, i) => i+1), m)
   .filter(ary => k === ary.reduce((s, x) => s + x));

• 動作確認用CodePen: https://codepen.io/jun68ykt/pen/Bajzgpp?editors=0011

もうひとつ。先日、このご質問 への回答を考える途上で、べき集合を得るコードを作成したのですが、これを利用しました。

const kadai1 = (n, m, k) => 
  powerSet(n, true)
    .map(ary => ary.map(i => i+1))
    .filter(ary => 
      ary.length === m && 
      ary.reduce((s, x) => s + x) === k
    );

• 動作確認用CodePen: https://codepen.io/jun68ykt/pen/NWxrZxp?editors=0011

ただし、べき集合を作るので m より要素数の多い組み合わせも生成されてしまうため、無駄が多いです。

Answer 3

こういうこと？
（ごめんなさい。力量が無くて１行にできなかった）

const A = (n, m, k)=>
  [...Array(n**m).keys()].reduce ((b, c)=>{
    let p=[...Array(m).keys()].map((_,l)=>(l=[...Array(n).keys()].map(_=>++_)[c%n],c=(c/n)|0,l));
    return p.reduce((a,b)=>a+b)===k?[...b,p]:b;
  }, []).reverse();


console.log( A (5,3,10));

Comments

[kei344]

reduce の5番以降の引数が無いのでそれを使うのは邪道ですか？
[0].reduce ((b, c,d,e,p)=>(p=1),p)

[退会済みユーザー]

楽しめるのであれば「あり」だと思います。

[退会済みユーザー]

おかげさまで1行になりました。
const A = (n, m, k)=>[...Array(n**m).keys()].reduce((b,c,d,e,p=[...Array(m).keys()].map((_,l)=>(l=[...Array(n).keys()].map(_=>++_)[c%n],c=(c/n)|0,l)))=p.reduce((a,b)=>a+b)===k?[...b,p]:b, []).reverse();