くりかえしくみたてアルゴリズム

4939 ワード
JavaScript くりかえしくみたて アルゴリズム#アルゴリズム# テキストリンク

この文章では,再帰的に重複する組合せを実現する方法を紹介した.
組み合わせは順序を問わず、繰り返しが許されないすべての数列を組み合わせと呼ぶ.
重複コンビネーションとは、コンビネーション内で重複が許可されることを意味します.
我々が知っている組合せでは,{1,2,3}から2つを抽出すれば,合計3つを得ることができる.
しかし、重複組合せは重複が許されるので、再び引いたカードを引くことができます.
すなわち,{1,1},{1,2},{2,2},{2,3},{3である.
混同すべきではないのは、重複グループのマージが{1,2}を抽出してから{2,1}を抽出できることを意味するのではなく、このように抽出したカードを抽出することができることである.
インプリメンテーションコード
const MAX = 4;

const combinationWithRepetition = () => {
  const arr = [1, 2, 3, 4]; // 조합에 사용되는 배열
  const selected = [];

  dfs(0, 0, arr, selected);
};

const dfs = (idx, cnt, arr, selected) => {
  if (cnt === 3) {
    console.log(selected.join(" "));

    return;
  }

  for (let i = idx; i < MAX; i++) {
    selected[cnt] = arr[i]; // Select[Cnt] = Arr[i]는 Cnt번째 뽑은 카드는 Arr[i]를 뜻한다.
    dfs(i, cnt + 1, arr, selected);
  }
};

combinationWithRepetition();
BOJ|10430号
√「ascii変換Strin