조합 / 순열 / 중복 순열

요소를 한번씩 보면서 다 뽑아줘야 하기 때문에 순회는 필수이다.

순회가 필수이기 때문에 반복문으로 할 수 있지 않을까 라는 접근이 가능하다.

 

① 순서가 없는 조 = 조합(combination)

['사과', '오렌지', '망고']

3개 중 2개로 조합할 수 있는 모든 경우의 수(순서에 상관 없이)

['사과', '오렌지']

['사과', '망고']

['오렌지', '망고']

어떤 것이 앞에 있던 뒤에 있던

순서에 상관없이 똑같은 하나의 경우의 수로 본다.

⇒ 총 경우의 수는 3개

nCr 에서 최대 n의 개수만큼 r을 뽑을 수 있다.

즉, 중복을 허용하지 않기 때문에 r은 n과 같을 수는 있어도 넘을 수 없다.

r <= n

 

ex) 3개 중 2개를 뽑아서 조합을 만드는 예시(for문)

function forloop() {
  let result = [];
  let lookup = [1, 2, 3];
  
  for(let i = 0; i < 3; i++) {
    for(let j = i + 1; j < 3; j++) {
    result.push([lookup[i], lookup[j]]);
    }
  }
  return result;
}

forloop();
[[1, 2], [1, 3], [2, 3]];

i와 j의 범위가 다름.

조합은 중복이 되지 않기 때문에 순서 상관 없이 다시 겹치는 것을 쓸 일이 없다.

[1, 2] === [2, 1]은 똑같이 취급한다.

즉, 각각의 요소로 만들 수 있는 조합을 다 만든 후에는 그 요소를 다시 사용할 필요가 없고,

하나만 남은 경우에는 조합을 만들 수 없으므로 로직이 종료된다.

 

 

② 순서를 두고 일렬로 두는 것 = 순열(permutation)

['사과', '오렌지', '망고']

3개중 2개로 순서를 부여하여 조합할 수 있는 모든 경우의 수.

(순서가 부여되기 때문에 바뀌면 다른 것으로 판단한다.)

['사과', '오렌지']

['사과', '망고']

['오렌지', '망고']

['오렌지', '사과']

['망고', '사과']

['망고', '오렌지']

nCr보다 경우의 수가 2배 늘어났다는 것을 알 수 있다.

순열 또한 중복을 허용하지 않기 때문에 r은 n을 넘을 수 없다

r <= n

 

🌟 순열과 조합의 차이

조합: i = 0, j = i + 1, k = j + 1

순열: i = 0, j = 0, k = 0

 

ex) 3개 중 3개를 뽑아 순열을 만드는 예시(for 반복문)

function forloop() {
  let result = [];
  let lookup = [1, 2, 3];
  
  for(let i = 0; i < 3; i++) {
    for(let j = 0; j < 3; j++) {
      for(let k = 0; k < 3; k++) {
        if(i === j || j === k || k === i) continue;
        result.push([lookup[i], lookup[j], lookup[k]]);
      }
    }
  }
  return result;
}

 

순열과 중복순열의 다른 점

: 중복 검사. if문과 continue가 들어가있음.

 

continue: 조건문의 조건에 부합하면 실행해야 하는 코드를 무시하고 로직을 계속 반복 진행한다.

 

즉 [1, 1, 1], [1, 1, 2], [1, 1, 3] 등은 무시하고 넘어간다.

⇒ 중복이던 아니던 일단 for문은 진행시키고, 조건에 부합하는 경우 실행될 코드가 무시되고 다음으로 진행한다.

⇒ 순열은 중복되지 않은 요소만 들어갈 수 있게끔 if 조건문을 사용한다.

 

if문은 || 연산자를 사용했다.

앞을 계산해서 ture가 나오면 뒤는 계산을 안하고 바로 다음으로 넘어간다.

⇒  || 연산자를 사용하기 때문에 실행 속도가 더 빨라진다.

⇒ 시간복잡도 부분에 영향을 미치지 않는다.

(이 상황이 아니더라도 &&연산자는 시간복잡도에 영향을 미친다)

 

 

③ 중복순열:  n개 중 r개를 뽑아 요소의 중복을 허용하고 순서를 부여하여 조합할 수 있는 모든 경우의 수

순회 필수!(반복문)

['사과', '오렌지', '망고']

3(n)개 중 2(r)개로 순서를 부여하여 조합할 수 있는 모든 경우의 수

['사과', '오렌지']

['사과', '망고']

['사과', '사과']

['오렌지', '망고']

['오렌지', '사과']

['오렌지', '오렌지']

['망고', '사과']

['망고', '오렌지']

['망고', '망고']

중복을 허용하기 때문에 r(뽑는 요소의 개수)이 n(주어진 요소의 개수)보다 클 수 있다.

 

ex) 3개 중 3개를 뽑아 중복 순열을 만드는 예시(for 반복문)

function forloop() {
  let result = [];
  let lookup = [1, 2, 3];
  
  for(let i = 0; i < 3; i++) {
    let pick1 = lookup[i];
    for(let j = 0; j < 3; j++) {
      let pick2 = lookup[j];
      for(let k = 0; k < 3; k++) {
        let pick3 = lookup[k];
        result.push([pick1, pick2, pick3]);
      }
    }
  }
  return result;
}

[1, 2, 3] 이라는 배열도 되지만

[1, 1, 1]

[1, 1, 2]

[1, 1, 3]

...

등 요소가 중복되어 들어가는 것이 가능하다.

 

→ result라는 []이 존재하는 이유는 for문을 다 돌고 push하는 것을 []안에 넣기 위함.

r개의 개수만큼 반복문을 만들어줄 수 있다.

 

‣ 반복문이 진행되는 로직

let pick1 = lookup[i]

pick1 이라는 변수에는 1이 할당된다.

i, j, k 전부 0이 먼저 들어갈 것이기 때문에 [1, 1, 1]이라는 배열이 push된다

result = [ [1, 1, 1] ]이 될 것이다.

 

위에 쓴 반복문 2개가 멈춰있는 상태에서 마지막 반복문이 돌아갈 때

[1, 1, 2]가 된다.

이 배열이 result에 push됨

result = [ [1, 1, 1], [1, 1, 2] ]

 

똑같은 방식으로

result = [ [1, 1, 1], [1, 1, 2], [1, 1, 3] ]

이 된다.

 

이 다음에는 첫번째 반복문은 멈춰있는 상태에서

두번째 반복문이 초기화되고 실행된 다음, 세번째 반복문이 다시 실행된다.

 

나머지 과정은 똑같이.

result = [ [1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 1] ]

 

 

ex)

변수로 따로 처리하지 않고 인덱스만 가져와서 그대로 반복문에 넣어 result에 push 하는 형식.

3개 중 3개를 뽑아 중복 순열을 만드는 예시(for 반복문)

function forloop() {
  let result = [];
  let lookup = [1, 2, 3];
  
  for(let i = 0; i < 3; i++) {
    for(let j = 0; j < 3; j++) {
      for(let k = 0; k < 3; k++) {
        result.push([lookup[i], lookup[j], lookup[k]]);
      }
    }
  }
  return result;
}

 

ex) 3개 중 2개를 뽑아 중복 순열을 만드는 예시(for 반복문)

for문이 2개가 되었음.

n개 중 r개를 뽑는다 가정할 때, 반복문의 개수는 r개이다.

function forloop() {
  let result = [];
  let lookup = [1, 2, 3];
  
  for(let i = 0; i < 3; i++) {
    let pick1 = lookup[i];
    for(let j = 0; j < 3; j++) {
      let pick2 = lookup[j];
        result.push([pick1, pick2]);
    }
  }
  return result;
}

 

n개의 요소 중에 r개

r개만큼 중첩되는 반복문이라면 r개가 11개면 11중 for문을 사용해야할까?

⇒ 위와 같은 식으로 추상화가 되면 for문으로 쓸 수 없게 될 것이다.

⇒ r이 커질수록 재귀함수를 사용할 수 있다면 유연하게 대처 가능하다.

ex) 피보나치 함수

 

ex) 3개 중 3개를 뽑아 중복 순열을 만드는 예시(재귀반복)

‣ 중심 로직은 for문 한번으로 쓴다.

‣ for문 3개를 count로 한번에 쓰고 탈출 조건인 if문이 있다.

‣ 재귀를 시킬 수 있는 코드가 있다.

 

⇒ count는 재귀함수를 몇번이나 재귀시킬수 있는지에 대한 count

⇒ bucket은 탈출 조건 안에서 result.push(bucket)을 함으로써 일회용으로 사용되고 버려짐.

=== 재귀호출을 쓰는 것은 결국 반복문을 3번 돌리는 것과 똑같다.

 

실행하고자 하는 내용 === recursive case

멈추고 결과반환 === base case

 

재귀에서 push를 안쓰고 concat을 쓰는 이유

concat을 쓰면 배열과 배열을 합치는 것이기 때문에 배열의 형태로 나올 수 있다.
push = [[]]

concat = []

 

 

ex) n개 중 n개를 뽑아 중복 순열을 만드는 예시(재귀반복)

let result = [];
let lookup = [1, 2, 3, 4, 5, 6, 7, 8];

function recursion(count, bucket) {
  if(count === 0) {
    result.push(bucket);
    return;
  }
  for(let i = 0; i < lookup.length; i++) {
    const pick = lookup[i];
    recursion(count - 1, bucket.concat(pick));
  }
}
recursion(lookup.length, []);

 

 

Pick Or Not

// 조합, 순열, 중복순열의 base code

const elements = ['가', '나', '다', '라'];

const pickOrNot = (idx, basket) => {
  // debugger 돌려보기!
  if(idx === elements.length) {
    console.log(basket);
    return;
  }
  pickOrNot(idx + 1, basket.concat(elements[idx]));
  pickOrNot(idx + 1, basket);
};

pickOrNot(0, []);