[JavaScript]コンビネーション、シーケンス、再帰(再帰)


プログラマメニューの更新の問題に答えようとします.
コンビネーションを使用して問題を解決すべきだと知っていますが、コンビネーションを実現するコードを生成することはできません.
ソース:コードテスト練習-メニュー更新|プログラマー

1.組み合わせ(組み合わせ)


再帰関数を使用して実装できます.
再帰関数は見苦しい
ゆっくり読むとわかるけど、実現させてもらえたら、できない気がする.
ブログ検索により,組合せとソートの実現方法を理解した.ありがとう!

基本的な考え方

시작
  1을 선택(고정)하고 -> 나머지 [2, 3, 4] 중에서 2개씩 조합을 구한다.
  [1, 2, 3] [1, 2, 4] [1, 3, 4]
  2를 선택(고정)하고 -> 나머지 [3, 4] 중에서 2개씩 조합을 구한다.
  [2, 3, 4]
  3을 선택(고정)하고 -> 나머지 [4] 중에서 2개씩 조합을 구한다. 
  [] 
  4을 선택(고정)하고 -> 나머지 [] 중에서 2개씩 조합을 구한다.
  []
종료
上記の一連のプロセスにより、すべての組合せを見つけることができる.
入力された入力シーケンスが長くなるかどうかにかかわらず、組み合わせる必要がある要素が増加します.
アレイの最初から1つ1つ固定して、残りのアレイを組み合わせて、貼り付けるだけでいいです...
再帰関数を使用するには、繰り返し続けること(組み合わせを求めるコード)を明確にし、入力したパラメータ(私以外)を変更するだけです.

再帰関数の実装


19615;再帰終了条件:1つを選択した場合、すべての配列の要素を選択して返します.
2▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼\9660
3固定(固定)値の残りの配列について,組合せを求める.このとき,1つの選択の数を減らす.
4則は、生成された結果に固定された値を加算し、返される配列に展開構文を使用して並べ替え、返されます.
5▼▼▼2 C 3、1 C 2など選択した個数が多ければ多いほど空の配列が返されるので、上記の例では3と4を選択すると空の配列が返され、最終結果値には含まれません.
 const getCombinations = function (arr, selectNumber) {
    const results = [];
    if (selectNumber === 1) return arr.map((el) => [el]); 
    // n개중에서 1개 선택할 때(nC1), 바로 모든 배열의 원소 return

    arr.forEach((fixed, index, origin) => {
      const rest = origin.slice(index + 1); 
      // 해당하는 fixed를 제외한 나머지 뒤
      const combinations = getCombinations(rest, selectNumber - 1); 
      // 나머지에 대해서 조합을 구한다.
      const attached = combinations.map((el) => [fixed, ...el]); 
      //  돌아온 조합에 떼 놓은(fixed) 값 붙이기
      results.push(...attached); 
      // 배열 spread syntax 로 모두다 push
    });

    return results; // 결과 담긴 results return
};

2.配列(置換)


順番が大切です.
fixedも同様に返されますが、結合する残りの配列の設定が異なる場合は、上記の組合せ実装を参照して簡単に実現できます.
function permutation(arr, selectNum) {
  let result = [];
  if (selectNum === 1) return arr.map((v) => [v]);

  arr.forEach((v, idx, arr) => {
    const fixer = v;
    const restArr = arr.filter((_, index) => index !== idx);
    const permuationArr = permutation(restArr, selectNum - 1);
    const combineFixer = permuationArr.map((v) => [fixer, ...v]);
    result.push(...combineFixer);
  });
  return result;
};

3.問題を解く

function solution(orders, course) {
  var answer = [];
  var orderBox = [];

  function combination(arr, selectNum) {
    const result = [];
    if (selectNum === 1) return arr.map((v) => [v]);
    arr.forEach((v, idx, arr) => {
      const fixed = v;
      const restArr = arr.slice(idx + 1);
      const combinationArr = combination(restArr, selectNum - 1);
      const combineFix = combinationArr.map((v) => [fixed, ...v]);
      result.push(...combineFix);
    });
    return result;
  }

  course.forEach(course => {
    orders.forEach(order => {
      const food = combination(order.split(''), course).map(order => {

        return order.sort().join('');
      })

      orderBox.push(...food);
    })

    const candidate = orderBox.reduce((acc, cur) => {
      acc[cur] = (acc[cur] || 0) + 1;
      return acc;
    }, {});

    let maxOrderFood = [];
    let maxOrder = 0;
    for (let key in candidate) {
      if (maxOrder < candidate[key]) {
        maxOrderFood = [key];
        maxOrder = candidate[key];
      } else if (maxOrder === candidate[key]) {
        maxOrderFood.push(key);
      }
    }

    if (maxOrder >= 2) answer.push(...maxOrderFood);

    orderBox = [];
  })

  answer.sort();
  return answer;
}
  • 再帰関数の学習に適したブログ
    Chapter 1. 回帰:概念と基本例-生涯学習ブログ:Today I Learned‐🌙
  • ソース:[JS]シーケンス、組み合わせと繰り返しシーケンスを求める
    JavaScriptを使用してシーケンスと組合せアルゴリズムを実装します。再帰、JavaScript Array Methods|byダンスの開発者|Medium
    JavaScriptによるシーケンスと組合せアルゴリズムの実装