순열

getPermutation

const getPermutation = arr => {
    if(arr.length === 1) return [arr]
    
    const permutation = []
    
    arr.forEach((picked, i) => {
        const others = [...arr.slice(0,i), ...arr.slice(i+1)]

        getPermutation(others).forEach(smallerPermutation => {
            permutation.push([picked].concat(smallerPermutation))
        })
    })
                
    return permutation
}

위 로직은 아래 사진처럼 동작합니다.

arr4 ([a,b,c,d])의 순열을 구하는 문제는

a를 고르고, 나머지인 bcd의 순열의 각 집합에 a를 합쳐준 것들과

bcd의 순열을 구하는 문제는

앞에서 b를 고르고, 나머지인 cd의 순열의 각 집합에 b를 합쳐준 것들과

c를 고르고, 나머지인 ad의 순열의 ....

d를 고르고, ...

b를 고르고, 나머지인 acd 순열의 각 집합에 b를 합쳐준 것들과

c를 고르고, ...

d를 고르고, ... 를 합쳐준 것들을 모두 원소로 갖는 배열입니다.

이를 일반화하면,

arr의 permutation은

arr를 순회하며

순회하는 원소 picked와

나머지 원소들의 순열을 조합한 것들의 묶음이 됩니다.

const permutation = arr => {
	const permutation = []

	arr.forEach(picked => { // 하나의 원소를 고른 후
		 const others = [...arr.slice(0,i), ...arr.slice(i+1)]

		 // 나머지의 순열의 각 집합을
      permutation(others).forEach(smallerPermutation => {
					// 합쳐준 것들
          permutation.push([picked].concat(smallerPermutation))
      })
	})
}