순열과 조합 (JS)

조합이란?  서로 다른 n개의 원소를 가지는 어떤집합에서 순서에 상관없이 r개의 원소를 선택하는 것이며, (즉, 선택의 순서와 상관없이 같은 원소들이 선택되었다면 같은 조합이며 다른 원소들이 선택되었다면 다른 조합이다.) 이는 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것 혹은 찾는 것과 같다. 

바로 예를 살펴보도록 하자. 4Combination3 = 4C3을 코드로 구현한다면 다음과 같은 인풋과 아웃풋을 가지게 된다.

Input: [1, 2, 3, 4] 
Output: [ [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4] ]

4C3은 4개중에 3개씩 선택할 때 나올 수 있는 모든 조합을 구한다는 말이다. 이 때, 조합의 순서는 상관이 없다. 즉 [1, 2, 3] = [3, 2, 1] 이렇게 순서가 바뀌어도 같은 구성이기 때문에 하나의 조합으로 취급한다는 이야기다.

코드로 구현해 보았을 때 

const arr = [A,B,C,D];
const n = 3;

function combination(charsArray, user_input_n) {
  let combi = []; // 조합을 추가할 배열

  const f = (prefix, charsArray) => {
    for (let i = 0; i < charsArray.length; i++) {
      combi.push(prefix + charsArray[i]);
      f(prefix + charsArray[i], charsArray.slice(i + 1));
    }
  }

  f('', charsArray);
  const result = combi.filter(x => x.length === user_input_n);
  return result;
}

console.log(combination(arr, n));

combi는 조합을 추가할 배열이다. 

f는 재귀적으로 사용되며 arr[i]와 arr[i+1]이 for문을 돌며 combi에 추가된다. 

마지막으로 combi에서 filter로 조건을 걸어 갯수가 3인 것만 result에 넣어준다. 

코드에서 f함수가 재귀적으로 처리되는 과정이 이해가 잘가질 않아서 작성하며 흐름들 따라가 보았다. 

(prefix+charsArray[i])	charsArray.slice(i+1)	combi
''	[A, B, C, D]	[A]
[A]	[B, C, D]	[AB]
[AB]	[C, D]	[ABC]
ABC]	[D]	[ABCD]
[AB]	[C, D]	[ABD]
[A]	[B, C, D]	[AC]
[AC]	[D]	[ACD]
[A]	[B, C, D]	[AD]
''	[A, B, C, D]	[B]
[B]	[C, D]	[BC]
[BC]	[D]	[BCD]
[B]	[D]	[BD]
''	[A, B, C, D]	[C]
[C]	[D]	[C,D]
''	[A, B, C, D]	[D]

 

---

순열이란? 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열(permutation)이라고 한다.

nPr = nCr × r!
조합을 구한 후, 선택하려는 수의 factorial 을 곱하면 순열을 구하는 공식이 탄생한다.

위의 조합의 예에서 확장시켜보면, [1, 2, 3, 4] 에서 3개씩 뽑아 순열을 구한다고 한다면,

[1, 2, 3] => 이 안에서 순서를 바꾸는 경우의 수 => 3! 
[1, 2, 4] => 이 안에서 순서를 바꾸는 경우의 수 => 3!
[1, 3. 4] => 이 안에서 순서를 바꾸는 경우의 수 => 3!
[2, 3, 4] => 이 안에서 순서를 바꾸는 경우의 수 => 3!

코드로 구현해 보았을 때 

const arr = [A,B,C,D];
const n = 3;

function permutation(charsArray, user_input_n) {
  let combi = []; // 조합을 추가할 배열

  const f = (prefix, charsArray) => {
    for (let i = 0; i < charsArray.length; i++) {
      combi.push(prefix + charsArray[i]);
      f(prefix + charsArray[i], charsArray.filter(char => char !== charsArray[i]));
    }
  }

  f('', charsArray);
  const result = combi.filter(x => x.length === user_input_n);
  return result;
}

console.log(permutation(arr, n));

조합을 구현한 이후에 쉽게 순열 코드를 작성 할 수 있었다. 

 f(prefix + charsArray[i], charsArray.filter(char => char !== charsArray[i])); 이 부분만 신경써줬는데 조합에서 charsArray를 slice(i+1) 값을 재귀함수에 넣어줬다면, 순열은 순서를 상관하니 prefix로 넣어주는 charsArray[i]만 빼고 넣어주면 되지 않을까하는 생각을 했다. 

 

 

참조 :

순열, 조합, 중복순열 구하기

순열과 조합