경우의 수 구하기(순열,중복순열,조합,중복조합) JS

1. 순열(nPr)

서로 다른 n개의 원소 중 m개를 순서에 맞게(=순서가 다르면 다른 것으로 취급) 선택 후 나열

 

반복문 구현

반복문으로 구현하는 경우 for문의 수가 n만큼 반복하게 된다. n이 작다면 상관없지만, 큰 경우에는 for문을 많이 사용하기 때문에 비효율적이다.

function permutationLoop(list) {
  const result = [];
  
  for(let i=0; i<list.length; i++) {
    for(let j=0; j<list.length; j++) {
      for(let k=0; k<list.length; k++) {
        // ...m번 반복
        if(i == j || j == k || k == i || ...) continue;
        result.push([list[i],list[j],list[k],...]);
      }
    }
  }
  
  return result;
}

 

재귀 구현

재귀로 구현하는 경우 반복하는 횟수를 제한하기 위한 조건문만 추가하면 한 번의 반복문을 사용해 효율적인 코드를 작성할 수 있다.

// 방법1
function permutationRecursion(list,m) {
  if(m === 1) return list.map(el=>[el]);
  
  const result = [];
  
  list.forEach((fixed,i,origin)=>{
    const rest = [...origin.slice(0,i),...origin.slice(i+1)];
    const permutations = permutationRecursion(rest,m-1);
    const attached = permutations.map(el=>[fixed,...el]);
    
    result.push(...attached);
  });
  
  return result;
}

// 방법2
function permutationRecursion2(list,m) {
  const result = [];
  
  function recursion(items,rest) {
    if(items.length === m) {
      result.push(items);
      return;
    }
    
    for(let i=0; i<rest.length; i++) {
      const temp = rest.slice(); // 새로운 rest를 만들기 위한 복사
      
      temp.splice(i,1); // 선택 된 것을 뺀 나머지(새로운 rest)
      recursion([...items, rest[i]],temp);
    }
  }
  
  recursion([],list);
  return result;
}

 

2. 중복 순열

서로 다른 n개의 원소 중 m개를 중복을 허용하며 순서에 맞게 선택 후 나열

 

반복문 구현

순열을 구했던 방법에서 중복을 제거하기 위해 들어갔던 조건문을 지우면 끝이다.

function permutationWithRepetitionLoop(list) {
  const result = [];
  
  for(let i=0; i<list.length; i++) {
    for(let j=0; j<list.length; j++) {
      for(let k=0; k<list.length; k++) {
        // ...m번 반복
        result.push([list[i],list[j],list[k],...]);
      }
    }
  }
  
  return result;
}

 

재귀 구현

중복이 가능하기에 기존에 사용하던 리스트를 사용해 해결할 수 있다.

// 방법1
function permutationWithRepetitionRecursion(list,m) {
  if(m === 1) return list.map(el=>[el]);
  
  const result = [];
  
  list.forEach((fixed,i,origin)=>{
    const permutations = permutationRecursion(origin,m-1);
    const attached = permutations.map(el=>[fixed,...el]);
    
    result.push(...attached);
  });
  
  return result;
}

// 방법2
function permutationWithRepetitionRecursion2(list,m) {
  const result = [];
  
  function recursion(items) {
    if(items.length === m) {
      result.push(items);
      return;
    }
    
    for(let i=0; i<list.length; i++) {
      recursion([...items, list[i]]);
    }
  }
  
  recursion([],list);
  return result;
}

 

3. 조합(nCm)

서로 다른 n개의 원소 중 m개를 순서에 상관없이(=순서가 바뀌어도 같은 것으로 취급) 선택 후 나열

 

반복문 구현

순열과 비슷한 형태이지만 순서에 상관없기 위해서 다음 반복문의 시작이 이전 반복문의 시작보다 +1 되어 있다.

function combinationLoop(list) {
  const result = [];

  for (let i = 0; i < list.length; i++) {
    for (let j = i + 1; j < list.length; j++) {
      for (let k = j + 1; k < list.length; k++) {
      	// ...m번 반복
        result.push([list[i], list[j], list[k],...]);
      }
    }
  }
  return result;
}

 

재귀 구현

// 방법1
function combinationRecursion1(list, m) {
  if(m === 1) return list.map(el=>[el]);
  
  const result = [];
  
  list.forEach((fixed,i,origin)=>{
    const rest = origin.slice(i+1);
    const combinations = combinationRecursion1(rest,m-1);
    const attached = combinations.map(el=>[fixed,...el]);
    
    result.push(...attached);
  });
  
  return result;
}

// 방법2
function combinationRecursion2(list, m) {
  const result = [];
  
  function recursion(items,index) {
    if(items.length === m) {
      result.push(items);
      return;
    }
    
    for(let i=index; i<list.length; i++) {
      recursion([...items, list[i]], i+1);
    }
  }
  
  recursion([],0);
  
  return result;
}

 

4. 중복 조합(nHm = n+m-1Cm)

서로 다른 n개의 원소 중 m개를 중복을 허용하며 순서에 상관없이 선택 후 나열

 

반복문 구현

조합과 같은 형태이지만, 다음 반복문에서 +1을 해주지 않고 처음부터 시작한다는 차이가 있다.

function combinationWithRepetitionLoop(list,m) {
  const result = [];
  
  for(i=0; i<list.length; i++) {
    for(j=i; j<list.length; j++) {
      // ...m번 반복
      result.push([list[i],list[j],...]);
    }
  }
  
  return result;
}

 

재귀 구현

조합에서 본인을 빼기위해 사용했던 i+1에서 +1을 제거해 본인을 포함시킨다.

// 방법1
function combinationWithRepetitionRecursion(list,m) {
  if(m === 1) return list.map(el=>[el]);
  
  const result = [];
  
  list.forEach((fixed,i,origin)=>{
    const rest = origin.slice(i)
    const combinations = combinationRecursion1(rest,m-1);
    const attached = combinations.map(el=>[fixed,...el]);
    
    result.push(...attached);
  });
  
  return result;
}

// 방법2
function combinationWithRepetitionRecursion2(list, m) {
  const result = [];
  
  function recursion(items,index) {
    if(items.length === m) {
      result.push(items);
      return;
    }
    
    for(let i=index; i<list.length; i++) {
      recursion([...items, list[i]], i);
    }
  }
  
  recursion([],0);
  
  return result;
}

 

 

참고

https://mine-it-record.tistory.com/508

https://bttrthn-ystrdy.tistory.com/68