중복순열(DFS 깊이우선탐색)

맨 아래에 다듬은 수정 코드 업데이트(배열 주어졌을때랑 안주어졌을때랑 조금 달라서 같은 느낌으로 통일시킴)

1부터 n까지의 숫자중

m개를 중복순열한다면

function permutationWithRepetition(n, m) {
  let arr = new Array(m).fill(0);
  // let arr = Array.from({ length: m }, () => 0); // 이렇게 해도 됨
  let answer = [];

  function DFS(L) {
    if (L === m) {
      answer.push(arr.slice());
    } else {
      for (let i = 1; i <= n; i++) {
        arr[L] = i;
        DFS(L + 1);
      }
    }
  }
  DFS(0);
  return answer;
}

console.log(permutationWithRepetition(3, 3));
//결과
[
  [ 1, 1, 1 ], [ 1, 1, 2 ], [ 1, 1, 3 ],   
  [ 1, 2, 1 ], [ 1, 2, 2 ], [ 1, 2, 3 ],   
  [ 1, 3, 1 ], [ 1, 3, 2 ], [ 1, 3, 3 ],   
  [ 2, 1, 1 ], [ 2, 1, 2 ], [ 2, 1, 3 ],   
  [ 2, 2, 1 ], [ 2, 2, 2 ], [ 2, 2, 3 ],   
  [ 2, 3, 1 ], [ 2, 3, 2 ], [ 2, 3, 3 ],   
  [ 3, 1, 1 ], [ 3, 1, 2 ], [ 3, 1, 3 ],   
  [ 3, 2, 1 ], [ 3, 2, 2 ], [ 3, 2, 3 ],   
  [ 3, 3, 1 ], [ 3, 3, 2 ], [ 3, 3, 3 ]    
]

재귀를 사용해서

DFS(0) 일때 arr[0] = 1

DFS(1) 일때 arr[1] = 1

DFS(2) 일때 arr[2] = 1

DFS(3) 일때  L===m 이므로 얕은 복사를 이용해서 [1,1,1]이 answer로 push되고 이런식으로 반복된다

 

 

예를들어 배열이 주어졌다면

let arr = ["rock", "scissors", "paper"];
function rockScissorsPaper(arr, n) {
  let answer = [];
  function DFS(L, S) {
    if (L === 0) {
      answer.push(S);
      return;
    }
    for (let i = 0; i < arr.length; i++) {
      DFS(L - 1, S.concat(arr[i])); //이건 중복 순열
      // if (!S.includes(box[i])) DFS(L - 1, S.concat(box[i])); //이건 순열
    }
  }
  DFS(n, []);
  return answer;
}

console.log(rockScissorsPaper(arr,3))
//결과
[
  [ 'rock', 'rock', 'rock' ],
  [ 'rock', 'rock', 'scissors' ],
  [ 'rock', 'rock', 'paper' ],
  [ 'rock', 'scissors', 'rock' ],
  [ 'rock', 'scissors', 'scissors' ],      
  [ 'rock', 'scissors', 'paper' ],
  [ 'rock', 'paper', 'rock' ],
  [ 'rock', 'paper', 'scissors' ],
  [ 'rock', 'paper', 'paper' ],
  [ 'scissors', 'rock', 'rock' ],
  [ 'scissors', 'rock', 'scissors' ],      
  [ 'scissors', 'rock', 'paper' ],
  [ 'scissors', 'scissors', 'rock' ],      
  [ 'scissors', 'scissors', 'scissors' ],  
  [ 'scissors', 'scissors', 'paper' ],     
  [ 'scissors', 'paper', 'rock' ],
  [ 'scissors', 'paper', 'scissors' ],     
  [ 'scissors', 'paper', 'paper' ],        
  [ 'paper', 'rock', 'rock' ],
  [ 'paper', 'rock', 'scissors' ],
  [ 'paper', 'rock', 'paper' ],
  [ 'paper', 'scissors', 'rock' ],
  [ 'paper', 'scissors', 'scissors' ],     
  [ 'paper', 'scissors', 'paper' ],        
  [ 'paper', 'paper', 'rock' ],
  [ 'paper', 'paper', 'scissors' ],        
  [ 'paper', 'paper', 'paper' ]
]

DFS(L - 1, S.concat(arr[i]));  이부분 push가 아닌 concat을 해준 이유는

push는 추가된 후 배열의 length값이 반환되기 때문이다.

 

수정된 코드

숫자 일떄

function solution(n) {
  let result = []
  let N = n
  function DFS(n, tempArr) {
    if (n === 0) return result.push(tempArr)
    else {
      for (let i = 1; i <= N; i++) {
        DFS(n - 1, tempArr.concat(i)) // 중복순열
        // if (!tempArr.includes(i)) DFS(n - 1, tempArr.concat(i)); // 순열
      }
    }
  }
  DFS(n, [])
  return result
}

배열 주어 졌을 때

let arr = ['rock', 'scissors', 'paper']

function solution2(arr, n) {
  let result = []
  function DFS(n, tempArr) {
    if (n === 0) return result.push(tempArr)
    for (let i = 0; i < arr.length; i++) {
      DFS(n - 1, tempArr.concat(arr[i])) // 중복 순열
      // if (!tempArr.includes(arr[i])) DFS(n - 1, tempArr.concat(arr[i])); // 순열
    }
  }
  DFS(n, [])
  return result
}

concat(i) 대신에 concat(arr[i])로 바뀌고 for문이 0부터 시작한것만 변경됐다