[자료구조] js 순열/ 조합

순열 / 조합

고딩때 배웟던..

😈👿😈에러가 난다! 왜?

-> recursion 을 이해를 잘 못 햇기 때문이다.!!!

순열

--> 순서있게 뽑는것 ! > [a b c d] 있으면 그다음에는 [a c b d]
이런식으로 겹치게 하면 안됨


const pop_recusrion = function (arr) {

    var pick = Math.floor(Math.random() * arr.length)
    // console.log(arr[pick])
    //console.log(` 어디에 ${arr.indexOf(arr[pick])}`)

    var flter_arry = arr.filter((el, index) => {
        return index != arr.indexOf(arr[pick])
    })
    return ([arr[pick], flter_arry])

}


const final_aroung = function (arr) {
    var sum = 1;

    for (var i = 1; i <= arr; i++) {
        sum = sum * i;

    }
    return sum;

}

var final_arr = [];

const recursion_codewar = function (arr) {

    const arr_split = arr.split('');
    var sum = final_aroung(arr.length);
    if (sum == 2) {
        sum = sum * 4;
    }
    //console.log(arr_split)
    const inne = function (arr1, numver, i = 0) {
        if (numver == i) {
            return;
        }
        var arr = [];
        var hey = [];

        arr1.forEach((fist, index, full) => {
            if (index == 0) {
                var [pick, remain] = pop_recusrion(full);
                hey = remain;
                // console.log(`남은 친구 ${remain}`)
                arr.push(pick);
            }
            else if (index > 0) {

                var [pick, remain] = pop_recusrion(hey);
                hey = remain;
                // console.log(`남은 친구 ${remain}`)
                arr.push(pick);
            }


        });

        var push_push = (arr.toString().replace(/,/g, ''));

        if (!final_arr.includes(push_push)) {
            final_arr.push(push_push)
        }

        return inne(arr1, numver, ++i)

    }
    inne(arr_split, 30);



    console.log(final_arr.sort())
    return (final_arr)

}
recursion_codewar('abcd')

< 이렇게 하면
오류가 남

😡 이 유

랜덤으로 뽑게 되면 안나올때도 있고 나올때도 있고 .. 결국 정확한 값이 안나와서
구글링 했다.

const getCombinations = function (arr, selectNumber) {
const results = [];
if (selectNumber === 1) return arr.map((el) => [el]);
// n개중에서 1개 선택할 때(nC1), 바로 모든 배열의 원소 return

arr.forEach((fixed, index, origin) => {
  const rest = origin.slice(index + 1); 
  // 해당하는 fixed를 제외한 나머지 뒤
  const combinations = getCombinations(rest, selectNumber - 1); 
  // 나머지에 대해서 조합을 구한다.
  const attached = combinations.map((el) => [fixed, ...el]); 
  //  돌아온 조합에 떼 놓은(fixed) 값 붙이기
  results.push(...attached); 
  // 배열 spread syntax 로 모두다 push
});

return results; // 결과 담긴 results return

}

<구글링해서 나온 조합 식

😅

트리 형식으로 가는 건 알겠는데 그러면 도대체 ?
어떻게 하면 다른 수 가 나올수 있을까?
-> 해답

이런경우 기차타고 간다고 생각하면 된다.

https://nyang-in.tistory.com/212

< 여기 보면 대충 이분이 적은 것이있다.

#해석

f (selectNumber === 1) return arr.map((el) => [el]);
// n개중에서 1개 선택할 때(nC1), 바로 모든 배열의 원소 return

이말 뜻이 뭐냐? 

arr 가 
[3,4,5] 면 [3] [4] [5] 로 보낸다는 그말이다.

const combinations = getCombinations(rest, selectNumber - 1);
// 나머지에 대해서 조합을 구한다.

  combination 은 그러면  [3] [4] [5] 을 받게 되고 
  
  arr.forEach((fixed < 지금 자리!!!
  

combinations.map((el) => [fixed, ...el]);
지금 자리에서 [[3][4] [5]]
을받게 되고
지금 보고 잇는 수는를 여기에다가 다 붙이라 이말이지
[fixed, ...el]); << ..el 하면 [fix] + [3] 동일 [4][5]

만약 fix 가 지금 2 면 ?

results.push(...attached); << 이러면 지금 [2,3]-> 2.3 을 넣어라

그럼 result 은 [2,3] 이런식으로 뭉치게 되고
이 뭉친 result 를 return 으로 보낸다 이말임 ㅡㅡ 그러면 받은
result 에 또오 추가 해주면 됨
그럼 다시 이게 또 도는가 ?
아니
밑으로 갈때는 한바퀴 돌지만
위로 갈때는!!!
const combinations = getCombinations(rest, selectNumber - 1);
이 combination 친구가 받게 되니까

const attached = combinations.map((el) => [fixed, ...el]); 
  //  돌아온 조합에 떼 놓은(fixed) 값 붙이기
  results.push(...attached); 
  // 배열 spread syntax 로 모두다 push
});

여기만 돌게 됨!! 결국은

result 가 쌓이게 되고
정확한 수가 나온다 이말이다..!!!!

하루종일 대가리 싸맸는데
해설본을 봐야 이해가 되는구나..
저 블로그 센세..
아리가또 ..^^

좋은 웹페이지 즐겨찾기