순열과 조합

조합

조합이란?

서로 다른 n개의 원소를 가지는 어떤 집합에서 순서에 상관없이 r개의 원소를 선택하는 것

조합은 선택의 순서와 상관없이 같은 원소들이 선택되었다면 같은 조합이다.

코드

let list = ["a","b","c","d","e"]
let num = 3;

function combinations(list,num){
	let result = []
    if(num ===1 ) return list.map(el=>[el])

    list.forEach((e,i,origin)=>{ 
      // e는 첫번째 문자
      // rest는 첫번째 문자를 선택하고 남은 배열 속 문자
      const rest = origin.slice(i+1) 
      // rest를 재쉬함수로 돌린 것 
      const combination = combinations(rest,num -1)
      // 처음 고른 문자와 나머지들은 함침
      const merge = combination.map((word)=>[e,...word])
      // 넣어줌
      // result.push(...merge)
      result = [...result , ...merge]
    })
    return result
}

console.log(combinations(list,num))

결과

순열

순열이란 서로 다른 n개 중에서 r개를 선택하여 배열하는 경우

순열과 조합의 차이
순서를 생각하냐 안하냐의 차이
순열은 뽑은 것들이 순서가 다르다면 다른 것으로 취급
조합은 순서가 다르더라도 내용이 같으면 같은 것으로 취급

코드

function permutations(list,num){
  let result = []
  if(num === 1 )return list.map(el=>[el])

  list.forEach((e,i,origin)=>{
    let rest = [...origin.slice(0,i),...origin.slice(i +1)] //조합과의 차이점 
    let permutation = permutations(rest, num -1)
    let merge = permutation.map(word=>[e,...word])
    result = [...result,...merge]
  })
  return result
}

결과

조합과의 차이점

//조합
const rest = origin.slice(i+1) 


//순열
let rest = [...origin.slice(0,i),...origin.slice(i +1)]

조합은 선택된 문자를 빼고 나머지를 보내주는 것
순열은 선택된 문자를 빼고 모든 나머지 문자를 보내주는 것

이유

조합은 순서가 상관이 있고 => 순서가 같으면 서로 같은 조합
순열은 상관이 없다 => 순서가 다르면 서로 다른 조합