순열(permutation)과 조합(combination)

둘의 function을 간단하게 적을 것이다. 둘의 결과값에 대한 차이는, 순서의 유무로 갈린다.

순열은, per- mutate 즉, 아주 작은 부분만 변하기만해도 순열이라 친다 즉, 구성원이 같아도 순서가 살짝다르면 다른것으로 친다. 조합은 말그대로 구성원의 조합이 중요한거지, 순서와는 전혀 무관한 친구다.

 

function의 플로우 차트를 이야기하자.

1. 순열과 조합을 만들 때 필요한 것은 무엇인가?

 a. 숫자 모음(array), b. 몇 개를 뽑을 것인가 (num)

 

2. Boundary condition은?

 a. num이 1개일 때는, 본인은 본인이다

 

3. 그 다음으로 배치 해야할 것들?

 a. array를 forEach로 각 요소마다 recursive하게, 순열과 조합 행렬을 다시 실행시킨다. 단, 여기서 num은 한개를 뺀다. 이때, 본인을 제외할 것인가?(array.slice(0, i )) 말 것인가에 따라 순열인지 조합인지 모양이 다르게 나온다

 b. 본인과 b에서 구한 값을 붙인다 (attached)

 c. 이 값을 result에 붙인다

4. 주의 해야할 것들

 a. 여기서 array에 대한 것을 행할때는, 요소들 각각 행해야하기 때문에 [...   ] 을 붙여야한다.

 

순열 조합을 공부하면서 이건 자주써야겠다 라고 생각하게된건

[..array.slice(0, i), ...array.slice(i+1)]이다.  .concat으로 써도 되긴하지만.. 가독성이 더 좋은거 같아서 기억을 해야겠다

 

 

function getPermutations (arr,n){
const result =[];
if(n ===1) return arr.map((v) =>[v]);
arr.map((me, i) =>{
    const rest = [...arr.slice(0, i), ...arr.slice(i+1)];
    const permutation = getPermutations(rest, n-1);
    const attached = permutation.map((item) => [me, ...item])
    result.push(...attached);
})
return result
}

 

음.. 안보고 타이핑을 치면서, rest부분에 me를 넣었었다. 주의하자.

rest는 forEach의 i를 기준으로, permutation은, 점점 갯수를 줄여야는 recursive기에, 위의 함수의 num-1을 기준으로

result.push뒤에 array가 아닌, ...만들어간다

 

 

 

const getCombinations = (arr, num) =>{
	const result = [];
    if(num===1) return arr.map(v=>[v]);
    arr.forEach((me, i)=>{
    	const rest = arr.slice(i+1);
        const combination = getCombinations(rest, num-1);
        const attached = combination.map((item)=> [me, ...item])
        result.push(...attached)
    })
    return result
}

 

화살표 함수를 쓰다보니 뭔가 깨끗해진거 같아서 기분이좋다. =ㅁ=++ 최근에 읽은 화살표함수 정리글이 도움이 된거같다.