조합
- 개념
- 조합이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 없음)- 중복 선택x
- nCr
- 중복 선택x
- 계산
- 코드1
다음은 3개의 다른 요소를 뽑는 코드이다. (수가 정해져있을 때)
function solution(arr) {
let tmp=[];
for(let i=0; i<arr.length-2; i++){
for(let j=i+1; j<arr.length-1; j++){
for(let k=j+1; k<arr.length; k++){
tmp.push([arr[i], arr[j], arr[k]]);
}
}
}
return tmp;
}
let arr=['a', 'b', 'c', 'd', 'e'];
console.log(solution(arr));
- 결과
[
[ 'a', 'b', 'c' ],
[ 'a', 'b', 'd' ],
[ 'a', 'b', 'e' ],
[ 'a', 'c', 'd' ],
[ 'a', 'c', 'e' ],
[ 'a', 'd', 'e' ],
[ 'b', 'c', 'd' ],
[ 'b', 'c', 'e' ],
[ 'b', 'd', 'e' ],
[ 'c', 'd', 'e' ]
]- 코드2) dfs (시작지점을 dfs에 넘겨서, 중복되지 않도록 만들어준다)
https://velog.io/@rladpwl0512/8-14-%EC%A1%B0%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0
function solution(n, r) {
let answer=[];
let tmp=Array.from({length:r}, ()=>0);
function DFS(v, s){
if(v===r){
answer.push(tmp.slice());
}
else{
for(let i=s; i<=n; i++){
tmp[v]=i;
DFS(v+1, i+1);
}
}
}
DFS(0, 1);
return answer;
}
console.log(solution(4, 2)); //4C2(1~4 중 2개 뽑음)- 코드3) 조합의 경우수(메모이제이션)
https://velog.io/@rladpwl0512/8-12-%EC%A1%B0%ED%95%A9%EC%9D%98-%EA%B2%BD%EC%9A%B0%EC%88%98%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98
중복 조합
- 개념
중복 조합이란 중복 가능한 n개중에서 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 없음) - 계산
순열
-
개념
- 순열이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미한다. (순서 상관 있음)
- 중복 선택x
- nPr
- 순열은 뽑은 다음에 순서를 생각해야 하지만, 조합은 뽑기만 해도 된다.
-
계산
-
코드
https://velog.io/@rladpwl0512/8-10-%EC%88%9C%EC%97%B4-%EA%B5%AC%ED%95%98%EA%B8%B0
뽑는 수를 저장하는 tmp배열과, 중복이 안되기 때문에 뽑았는지 확인하는 ch배열이 필요하다.
function solution(m, arr){
let answer=[];
n=arr.length;
let ch=Array.from({length:n}, ()=>0); //사용했는지 체크하는 배열(중복 방지!)
let tmp=Array.from({length:m}, ()=>0); //뽑은것 넣는 배열
function DFS(L){
if(L===m){
answer.push(tmp.slice()); //깊은복사
}
else{
for(let i=0; i<n; i++){
//ch[i]가 0일때(중복되지 않을 때) 사용 가능
if(ch[i]===0){
ch[i]=1; //사용하면 1으로 바꿈
tmp[L]=arr[i];
DFS(L+1);
ch[i]=0; //백해서 다시 돌아오는 지점에서는 0으로 초기화시켜줌
}
}
}
}
DFS(0);
return answer;
}
let arr=[3, 6, 9];
console.log(solution(2, arr));중복 순열
- 개념
중복 순열이란 중복 가능한 n개중에서 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 있음) - 계산
https://velog.io/@rladpwl0512/8-8-%EC%A4%91%EB%B3%B5%EC%88%9C%EC%97%B4-%EA%B5%AC%ED%95%98%EA%B8%B0
- 코드 (n중 m개 뽑는다고 할 때, 길이가 m인 tmp 만들어주기🍯)
function solution(n, m){
let answer=[];
let tmp=Array.from({length:m}, ()=>0); //길이가 m인 배열 0으로 초기화해서 생성
function DFS(L){
if(L===m){
answer.push(tmp.slice()); //slice는 깊은복사(깊은복사 안하면 마지막갚으로 모두 push됨)
}
else{
for(let i=1; i<=n; i++){
tmp[L]=i; //넣고 (대입하는 것! 따로 빽할때 처리해줄 필요 없다)
DFS(L+1); //다음 레벨로 넘어감
}
}
}
DFS(0);
return answer;
}
console.log(solution(3, 2));참고 자료
내가 짱이다 😎 매일 조금씩 성장하기🌱