[LeetCode] 46. Permutations 순열 (Javascript)

https://leetcode.com/problems/permutations/

var permute = function(nums) {
  return nums.reduce(
    function(list, element) {
      var newlist = [];

      list.forEach(function(seq) {
        for (var i = seq.length; i >= 0; i--) {
          var newseq = [].concat(seq);
          newseq.splice(i, 0, element);
          newlist.push(newseq);
        }
      });
      return newlist;
    },
    [[]]
  );
};

 

순열 이해하기가 왜이렇게 어려운지..

 

요약하면, 반복을 돌며 값을 고정해나가는 방식이다.

[1, 2]이 있다고 하면, 배열 길이만큼 반복을 돌면서 인덱스마다 다음 값을 삽입한다.

그러면 [1, 2, 3] [1, 3, 2] [3, 1, 2]이 될 것이다. (깔끔한 정렬을 위해 인덱스는 역순으로 돌림)

 

위 동작을 위해 [1, 2]와 [2, 1]을 만들기 위해서는 [1]에 인덱스마다 2를 집어넣으면 된다.

 

[1]을 만들기 위해서는 []에 인덱스마다 1을 집어넣으면 된다.

 

이런 동작을 반복하면 된다.

---

주어진 배열이 [1, 2, 3]일 때 reduce 진행 순서에 따라 값의 변화를 보자.

 

reduce 1회차 (list = [[]], element = 1)

list의 아이템(seq)이 [] 하나기때문에 forEach는 한번만 돌게 된다.

seq	[]
newseq.splice	[1] // 0번째 인덱스에 element = 1을 추가
forEach의 리턴값 newlist	[[1]]

 

reduce 2회차 (list = [[1]], element = 2)

list의 아이템 seq는 여전히 하나라서 forEach는 한번만 돌지만, seq의 length가 1이기 때문에 for문은 두번 돈다.

seq	[1]
1번째 for문 newseq.splice	[1, 2] // 1번째 인덱스에 element = 2를 추가
newlist	[[1, 2]]
2번째 for문 newseq.splice	[2, 1] // 0번째 인덱스에 element = 2를 추가
newlist (forEach의 리턴값)	[[1, 2], [2, 1]]

 

reduce 3회차 (list = [[1, 2], [2, 1]] , element = 3)

seq가 두개이므로 forEach 두번, 각 forEach마다 for문이 세번씩 돈다. 

1번째 forEach문 seq	[1, 2]
1번째 for문 newseq.splice	[1, 2, 3] // 2번째 인덱스에 element = 3을 추가
newlist	[[1, 2, 3]]
2번째 for문 newseq.splice	[1, 3, 2] // 1번째 인덱스에 element = 3을 추가
newlist	[[1, 2, 3], [1, 3, 2]]
3번째 for문 newseq.splice	[3, 1, 2] // 0번째 인덱스에 element = 3을 추가
newlist	[[1, 2, 3], [1, 3, 2], [3, 1, 2]]
2번째 forEach문 seq	[2, 1]
1번째 for문 newseq.splice	[2, 1, 3] // 2번째 인덱스에 element = 3을 추가
newlist	[[1, 2, 3], [1, 3, 2], [3, 1, 2], [2, 1, 3]]
1번째 for문 newseq.splice	[2, 3, 1] // 2번째 인덱스에 element = 3을 추가
newlist	[[1, 2, 3], [1, 3, 2], [3, 1, 2], [2, 1, 3], [2, 3, 1]]
1번째 for문 newseq.splice	[3, 2, 1] // 2번째 인덱스에 element = 3을 추가
newlist	[[1, 2, 3], [1, 3, 2], [3, 1, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1]]

 

최종적인 반환값은 [[1, 2, 3], [1, 3, 2], [3, 1, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1]] 이 된다.