The Next Higher Permutation 반복(iterater)
The Next Higher Permutation 반복형으로 트리형식으로 모든 경우의 수를 구하는 알고리즘입니다.
이전 글인 재귀형과 같은 결과가 나와요 재귀형에 비해 약간 지저분한 느낌이 없지않게 있지만... 결과는 나오니까요..!
큰 도움이 안되더라도 참고하듯 봐주세요...
#include "stdafx.h"
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>
int nNumItemCnt = 0;
int g_Array[100];
int num_of_test = 0;
int rand_seed = 0;
void initialize();
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] = {10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000};
void main()
{
bool bFlag = false;
while (1)
{
printf("몇개의 숫자를 Permutation-iterator하시겠습니까");
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;
int check = 1;
initialize();
while (check == 1)
{
printItem();
check = generateNextHigherPermutationItem();
}
finish = clock();
for(int i = 0; i < nNumItemCnt; i++)
{
printf("%5d", g_nMinRange[i]);
}
printf("\n최소 거리 : %lf", g_dMinRange);
printf("\n");
time_total = ((double)(finish - start) / CLOCKS_PER_SEC);
printf("걸린 시간 : %lf \n\n", time_total);
}
}
void initialize()
{
for (int i = 0; i < 100; i++)
{
g_Array[i] = i+1;
g_nMinRange[i] = 1000;
}
g_dMinRange = 10000;
}
int generateNextHigherPermutationItem()
{
int index_i, index_j;
int min, temp;
int check = 0;
for (int i = nNumItemCnt - 2; i >= 0; i--)
{
if (g_Array[i] < g_Array[i + 1]) {
index_i = i;
check = 1;
break;
}
}
if(check == 1)
{
min = nNumItemCnt + 1;
for (int j = nNumItemCnt - 1; j > index_i; j--)
{
if (g_Array[j] > g_Array[index_i] && g_Array[j] < min)
{
min = g_Array[j];
index_j = j;
//강제 break(맨 앞자리가 1까지만 하기위해)
//if(min == 2)
// return 0;
}
}
temp = g_Array[index_i];
g_Array[index_i] = g_Array[index_j];
g_Array[index_j] = temp;
Exchange_Sort(index_i);
}
return check;
}
void printItem()
{
//! 현재의 거리
double dRange = 0.0;
for (int i = 0; i < nNumItemCnt; i++)
{
//! 그냥 가지고 있는곳을 출력하는곳
printf("%5d", g_Array[i]);
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];
}
}
}
void Exchange_Sort(int index_i) {
int smallest;
int temp;
for (int i = index_i + 1; i < nNumItemCnt - 1; i++)
{
smallest = i;
for (int j = i + 1; j < nNumItemCnt; j++)
{
if (g_Array[j] < g_Array[smallest])
{
smallest = j;
}
temp = g_Array[i];
g_Array[i] = g_Array[smallest];
g_Array[smallest] = temp;
}
}
}
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 iterater