PS를 할때 머리 속으로 조합이나 순열을 사용하면 되겠다고 느껴도
막상 구현하는건 그렇게 쉽지 않은 경우가 있다.
한번 구현해보자.
순열과 조합의 차이점은 순열은 순서가 존재하고 조합은 그렇지 않다는 것이다.
A,B,C로 조합을 한다면 A,B,C,AB,AC,ABC가 있지만,
순열을 만들면 A,B,C,AB,BA,AC,CA,BC,CB,ABC,ACB,ABC,BAC,BCA,CAB,CBA가 나오게 된다.(순서를 고려하므로)
조합을 구현하는 아이디어는 이렇다.
function combination(arr,num){
if(num==1){
return arr.map((i)=>i)
}
let result = [];
for(let i = 0 ; i < arr.length -1; i++){
let fixed = arr[i];
let rest = arr.slice(i+1);
let combinationRest = combination(rest,num-1);
let attached = combinationRest.map((i)=>[fixed, ..i]);
result.push(attached);
}
return result;
}A,B,C의 배열로 조합을 구성하고, num은 1, 이 함수를 F라고 가정하자
F(ABC)는 A를 고정하고, F(BC)를 다시 실행한다.
그러면 F(BC)는 B를 고정시키고 F(C)를 실행한다.
F(C)는 num이 1이니 [c]를 리턴한다.
F(BC)는 이것을 가지고 리턴받은 C를 가지고 B,C를 만들고 B,C를 결과에 추가한다.
F(ABC)에서는 [B,C]를 받고 map을 통해서 AB, AC를 만들고 결과에 추가한다.
그러면 AB, AC, BC라는 조합을 만들수 있다!
순열도 비슷하다.
function combination(arr,num){
if(num==1){
return arr.map((i)=>i)
}
let result = [];
for(let i = 0 ; i < arr.length -1; i++){
let fixed = arr[i];
let rest = [..arr.slice(0,i), ...arr.slice(i+1)];
let combinationRest = combination(rest,num-1);
let attached = combinationRest.map((i)=>[fixed, ..i]);
result.push(attached);
}
return result;
}차이로는 rest가 i 이후가 아니라 i를 제외한 나머지 전부를 의미한다.
F(ABC)에서 A를 고정하는 경우는 위의 조합과 같고 B의 케이스를 보자.
B를 고정하는 경우 rest는 AC가 되고
F(AC)에서 A 고정후 F(C)에서 C를 리턴하고 이를 받은 F(AC)에서 다시 AC를 리턴한다.
그러면 F(ABC)에서 고정한 B와 리턴받은 AC 배열을 통해서 BA, BC을 생성한다.
C를 고정한 이후도 동일하고 결과적으로 AB,AC,BA,BC,CA,CB가 생성된다.
