Silverback9

오늘은~^^*

Lexicographic Order Algorithm 사전식 배열 알고리즘을 코드로 만들어 보는 날이예요~^^*

햇살이 맑아 감사한 아침이기도 하네요~^^* 네~^^*

통통 튀는 아침 햇살에 마음도 몸도 슬슬 부지런해지는데요~^^*

부드러운 재즈 선율에 맞추어 아침을 누리고 계셔요~^^*

코딩 공부 정리해서 돌아올게요~^^* 쓩~^^*

네~^^*

먼저~^^*

하나. value 수치값 배열을 만들어 보겠습니다~^^*

var vals = [ 0. 1, 2 ];

둘. 함수 SWAP()도 미리 만들어 준비해 놓을까요~^^*

function(a, i , j) {
  var temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

셋. 자신의 다음 수보다 작고, 순열에서 가장 멀리 있는 수의 순번을 나타내는 largestI를 준비해 보겠습니다~^^*

(1) 순열 속 모든 수가 자신의 다음 수보다 작지 않은 경우, 즉 순열의 마지막 경우에 해당할 경우 (‘경우’라는 말이 많이 나오네요~~^^*), 다시 말해서 “0” “1,0” “2,1,0” “3,2,1,0” “4,3,2,1,0”…등의 경우, 아무런 작업을 하지 않고 종료하면 좋을 것 같습니다.

(2) 그래서, largestI는 순열에 존재하지 않는, 그러나 순열의 첫번째 요소보다 순서상 바로 앞에 있는 그 어떤 것을 지칭할 수 있도록 해 보겠습니다.

(3) 순열의 첫번째 요소는 vals[0]가 되기 때문에, 0보다 한 발짝 앞에 있는 수, 즉 -1을 largestI로 설정해 보겠습니다.

(4) 그러면, 존재하지는 않지만 순서상 vals[0]보다 앞에 있는 그 어떤 것인 vals[-1]을 가리킬 수 있게 될 것 같아요~^^*

var largestI = -1;

넷. 순열 vals[] 속 수들을 처음부터 마지막 바로 앞의 수까지 순차적으로 진행하며, 자신 vals[i]가 자신의 다음 수 vals[i+1]보다 작은 경우, 변수 largestI에 이 수 vals[i]의 인덱스인 i를 저장하겠습니다.

for(var i = 0; i < vals.length -1; i++) {
  if(vals[i] < vals[i+1]){
    largestI = i;
  }
} 

다섯. 자신이 다음 수보다 작은 경우가 없는 경우(예를 들어 4,3,2,1,0), 순열의 마지막 경우에 해당하므로 아무런 작업을 하지 않고 프로그램을 종료하겠습니다.

if(leargestI == -1) {
  noloop();
  console.log('finished');
}

<셋.넷.다섯. 총정리 코드> 세 단계를 한 눈에 훑어 볼게요~^^*

var largestI = -1;

for(var i = 0; i < vals.length -1; i++) {
  if(vals[i] < vals[i+1]){
    largestI = i;
  }
} 

if(leargestI == -1) {
  noloop();
  console.log('finished');
}

여섯. vals[largestI]보다 작으며, 순열에서 가장 멀리 있는 수의 순번을 나타내는 largestJ를 준비해 보겠습니다. largestJ도 존재하지는 않지만 순열의 첫 번째 수보다 한 발짝 앞에 있는 수를 가리킬 수 있도록 하겠습니다.

var largestJ = -1;

일곱. 순열 vals[] 속 수들을 처음부터 끝까지 순차적으로 진행하며, vals[largestI]보다 자신 vals[j]가 큰 경우, 변수 largestJ에 이 수 vals[j]의 인덱스인 j를 저장하겠습니다.

for(var i = 0; i < vals.length; i++) {
  if( vals[largestI] < vals[j] ){
    largestJ = j;
  }
} 

<여섯.일곱. 총정리 코드> 두 단계를 한 눈에 훑어 볼게요^^*

var largestJ = -1;
for(var i = 0; i < vals.length; i++) {
  if(vals[largestI] < vals[j]){
    largestJ = j;
  }
} 

여덟. vals[largestI]와 vals[largestJ]를 맞바꾸어 볼게요~^^* SWAP~~^^*

swap(vals, largestI, largestJ);

아홉. 맞바꿈이 일어난 위치 largestI 이후의 나머지 순열 부분의 순서를 거꾸로 하겠습니다. REVERSE!!!

(1) 순열 vals[]에서, vals[largestI]를 기준으로 앞뒤를 자른 후, 뒷부분을 변수endArray에 저장해 보겠습니다.

(2) 이때, 함수 splice()를 사용해 보겠습니다.

(i) 배열의 index는 0부터 시작하기 때문에, vals[0]에서 vals[largestI]까지의 요소의 총 갯수는 <largestI + 1>이 되겠지요? (예를 들어, 0,1,2의 총 갯수는 3개,즉 <2+1>이지요?)

(ii) splice(largestI+1)라는 표현은, “배열 속 앞에서부터 largestI+1개만 남겨두고, 그 뒷부분은 잘라낸다 “는 의미가 된다고 해요.

(iii) 잘려진 뒷부분을 새로운 배열로 삼아서 변수 endArray에 저장하겠습니다~^^*

(iv) 원래 배열 vals[]는 vals[0]부터 vals[largestI]까지만 남아있게 되고~^^*

(v) 새로운 배열 endArray[]에는 원래의 vals[largest+1]가 endArray[0]가 되겠네요^^*

var endArray = vals.splice(largestI + 1);

(3) 이제, endArray[]의 순서를 거꾸로 만들겠습니다. 함수 reverse()를 사용해 보겠습니다^^* 함수 reverse()를 사용하면 복사본을 생성하지 않고, 원본 배열 endArray자체의 순서가 바뀌게 됩니다.

endArray.reverse();

(4) vals[0]부터 vals[largestI]까지만 남은 배열vals[] 끝부분에 순서가 거꾸로된 배열 endArray[]를 붙여보겠습니다. 함수 concat()을 사용해 보겠습니다.

vals = vals.concat(endArray);

<<(1)(2)(3)(4) 총 정리 코드>> 아홉번째 단계를 한 눈에 훑어 보겠습니다~^^*

var endArray = vals.splice(largestI + 1);
endArray.reverse();
vals = vals.concat(endArray);

열. 이제 순열을 문자열로 표현하여 시각화 해 보겠습니다. 큼직한 글자로~^^*

  background(0);
  textSize(64);
  var s = '';
  for (var i = 0; i < vals.length; i++) {
    s += vals[i];
  }
  fill(255);
  text(s, 20, height / 2);

와우!!! Lexicographic Order Algorithm 코드 작업을 마무리 한 것 같은데요!!!

우리 전체 코드를 한 번 같이 살펴 볼까요~~^^*

var vals = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

function setup() {
  createCanvas(400, 400);
}

function draw() {
  console.log(vals);
 
  var largestI = -1;
  for (var i = 0; i < vals.length - 1; i++) {
    if (vals[i] < vals[i + 1]) {
      largestI = i;
    }
  }
  //STEP 1. P[i]가 P[i+1]보다 작은 경우 중 가장 큰 i를 찾으라. 
  // => 자신의 다음 수보다 작은 수 중에서, 순열에서 가장 멀리 놓여있는 수를 찾으라.

  if (largestI == -1) {
    noLoop();
    console.log('finished');
  }
  //(만약 그런 i가 없다면, 순열 P는 가장 마지막 경우가 된다.)

  var largestJ = -1;
  for (var j = 0; j < vals.length; j++) {
    if (vals[largestI] < vals[j]) {
      largestJ = j;
    }
  }
  //STEP 2. P[i]가 P[j]보다 작은 경우 중 가장 큰 j를 찾아라. 
  //=> P[i]보다 큰 수 중에서, 순열에서 가장 멀리 놓여있는 수를 찾으라. 
  
  swap(vals, largestI, largestJ);
  //STEP 3. P[i]와 P[j]를 맞바꾸라.
 
  var endArray = vals.splice(largestI + 1);
  endArray.reverse();
  vals = vals.concat(endArray);
  //STEP 4. P[i]와 P[j]를 맞바꾸라.

  background(0);
  textSize(64);
  var s = '';
  for (var i = 0; i < vals.length; i++) {
    s += vals[i];
  }
  fill(255);
  text(s, 20, height / 2);
}

function swap(a, i, j) {
  var temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

이제 0,1,2,3,4,5,6,7,8,9가 lexicographic order algorithm 사전식 배열 알고리즘에 의해 위치가 바뀌어 가는 과정을 구경해 보러 저와 함께 가보시죠~^^*

오늘 저와 함께 lexicographic order algorithm 사전식 배열 알고리즘을 코드로 구현해 주셔서 감사합니다~^^*

내일부터는 우리~~^^* 이 알고리즘을 바탕으로 Travelling Salesman Problem을 해결하는 코드 공부를 또 시작해 볼까요~^^*

도전 after 도전! 와우! 짜릿한데요!

오늘의 만남에서 받은 기쁨에 대한 감사를

내일의 만남에게 기쁨으로 선물하는

따뜻한 연쇄작용 아름다운 파도가

큰 선물을 앞으로 앞으로 전달해요!

어머! Lexicographic Order Algorithm은

Pay it Forward 정신을 담고 있나봐요!

오늘도 반가운 만남 기쁨 나누는 보람찬 하루 보내시기 바래요~^^*

이윽고, 깊은 밤이 되면~^^*

기쁨과 감사와 뿌듯함으로 가슴 통통 두드리며 코~^^*하시구요~^^*

네~^^* 꿈은 이루어 집니다~^^*