The Next Higher Permutation 재귀(Recursive)

The Next Higher Permutation 재귀형으로 트리형식으로 모든 경우의 수를 구하는 알고리즘입니다.

The Next Higher Permutation으로 모든 경우의 수를 구한 후 나온 경우의 수를 n, n+1 를 각각 x, y좌표로

최단 경로를 확인 하는 소스에요.(추가로 정렬 + 최단거리하는데 걸리는 시간도 확인 할 수 있어요.)

학교에서 알고리즘 과제 제출용으로 한개씩 구글링 + 수정한 소스를 올릴게요.

#include "stdafx.h"

#include <stdio.h>

#include <time.h>

#include <stdlib.h>

#include <math.h>

int nNumItemCnt = 0;

int g_Array[100];

void init();

int generateNextHigherPermutationItem();

void printItem();

void Exchange_Sort(int index_i);

//! 거리

double calc(float n[],float nGo[]);

//! 처음이 제일 작은 거리 숫자 다음이 7개 번호 나열

double g_dMinRange = 10000;

int g_nMinRange[100];

/* Function to swap values at two pointers */

void swap (int *x, int *y)

{

    char temp;

    temp = *x;

    *x = *y;

    *y = temp;

}

 

void permute(int *a, int i, int n)

{

   int j;

   if (i == n)

   {

  

  //! 현재의 거리

  double dRange = 0.0;

  for(int nA = 0 ; nA < nNumItemCnt; nA ++)

  {

  printf("%5d", a[nA]);

  float fXy[2] = {0,0};

  float fXyGo[2] = {0,0};

  fXy[0] = g_Array[i];

  fXy[1] = g_Array[i + 1];

  fXyGo[0] = g_Array[i + 1];

  fXyGo[1] = g_Array[i + 2];

  dRange += calc(fXy, fXyGo);

  }

    printf("\t%lf", dRange);

    printf("\n");

  if(dRange < g_dMinRange)

  {

  g_dMinRange = dRange;

  for (int i = 0; i < nNumItemCnt; i++) 

  {

  g_nMinRange[i] = g_Array[i];

  }

  }

  

   }

   else

   {

        for (j = i; j <= n; j++)

       {

          swap((a+i), (a+j));

          permute(a, i+1, n);

          swap((a+i), (a+j)); //backtrack

       }

   }

}

 

void init() 

{

for (int i = 0; i < 100; i++) 

{

g_Array[i] = i+1;

g_nMinRange[i] = 1000;

}

g_dMinRange = 10000;

}

/* Driver program to test above functions */

int main()

{

while (1)

{

printf("몇개의 숫자를 Permutation-재귀 하시겠습니까");

scanf_s("%d", &nNumItemCnt);

printf("Cnt : %5d \n", nNumItemCnt);

if(nNumItemCnt > 100)

{

printf("끝!");

break;

}

clock_t start, finish;

start = clock();

double time_total = 0.0;

init();

permute(g_Array, 0, nNumItemCnt  -1);

finish = clock();

for(int i = 0; i < nNumItemCnt; i++)

{

printf("%5d", g_nMinRange[i]);

}

printf("\t 최소 거리 : %lf", g_dMinRange);

printf("\n");

time_total = ((double)(finish - start) / CLOCKS_PER_SEC);

printf("걸린 시간 : %lf \n\n", time_total);

//getchar();

}

   return 0;

}

double calc(float n[],float nGo[])

{

int nX1 = n[0];

int nY1 = n[1];

int nX2 = nGo[0];

int nY2 = nGo[1];

return sqrt((double)(pow(double(nX2 - nX1), 2) + pow(double(nY2 - nY1), 2)));

}

혹시 복사가 안되면 말해주세요(아직 처음이라 잘 몰라요 ㅠ)

visual studio 2012에서 코딩해습니다.

The Next Higher Permutation

The Next Higher Permutation c code

The Next Higher Permutation example

The Next Higher Permutation 재귀 

The Next Higher Permutation Recursive