자바스크립트 예제: 순열 및 중복순열 (어떠한 문자를 조합해서 나올 수 있는 가능한 모든 경우 나열하기)

서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것을 n개에서 r개를 택하는 순열이라고 하고, 여기서 중복을 허용하면 그것을 중복 수열이라고 합니다.

재귀함수를 이용해서 다음과 같이 나타낼 수 있습니다.

스택플로 출처 바로가기

 

중복 순열 (Permutation of Repetition)

중복순열의 구현이 약간 더 쉽습니다.

const cases = ["A", "B", "C"]

const permuteRepl = (array, n, eachElements, outArr) => {

    // 재귀 종료문
    if (array.length == n) {
        outArr.push(JSON.parse(JSON.stringify(array))) // 깊은 복사
        return
    }

    for (let el of eachElements) {
        array.push(el)
        permuteRepl(array, n, eachElements, outArr)
        array.pop()
    }

}
permuteRepl([], cases.length, cases, outArr)
console.log(outArr.map(_ => _.join("")))

원리는 저도 모르고 인터넷에서 보니까 이렇게 하면 된다고 하길래 가져다 썼습니다. n**r 만큼 경우의 수가 나오므로 여기서는 3**3=27 가지 경우가 나오고 재귀함수를 사용하므로 경우가 너무 크면 에러가 발생할 수도 있습니다.

 

순열 (Permutation)

순열(중복 허용안함)은 약간 복잡합니다.

참고로 splice() 메서드는 배열의 기존 요소를 삭제 또는 교체하거나 새 요소를 추가하여 배열의 내용을 변경합니다. (MDN 링크)

const outArr2 = []
const permute = (array, eachElements, outArr) => {
    let chr
    
    for(let i = 0; i < eachElements.length; i++) {
        chr = eachElements.splice(i, 1)[0] // i위치에서 1만큼 제거한 배열의 0번 요소 
        array.push(chr)
        
        if(eachElements.length == 0) {
            outArr.push(array.slice())   
        }
        
        permute(array, eachElements, outArr)
        eachElements.splice(i, 0, chr) // i 위치에서 0만큼 제거(=아무것도 안함)한 뒤 chr을 i 위치에 삽입
        array.pop()
    }
    return
    
}

permute([], cases, outArr2)
console.log(outArr2.map(_ => _.join("")))

순열 공식에 의하면 n = 3, r =3 이므로 6이 나옵니다.