Lean Software Development

"린 소프트웨어 개발". 출판사 : 인사이트
예약 판매때 주문해서 이제야 다 읽었다.
(삼색볼펜 학습법? 에 의하면 이제야 1/3 읽은 거지만...)

폭포수 모델이 달이 아닌 달을 가리키는 손가락을 본것에서 비롯된 잘못된 해석이었다면,
이 책은 손가락이 아니라 달을 보게 하는 책인것 같다.

next_permutation

C++ STL을 보면 next_permutation이란 알고리즘(?)이 있다.

int A[] = {1,2,3};
int N = sizeof(A) / sizeof(int);
next_permutaion(a, N)

이렇게 하고 나면 A에는 {1,3,2}가 저장되는데, {1,2,3}으로 만들수 있는 조합 중 다음번 조합을 구하는 함수이다.
그런데, 세자리 숫자로 표현할수 있는 모든 수를 구하는데는 문제가 있다.
예를 들어 {1,2,3} 다음 수로 {1,2,4}를 원할때는 next_permutation을 사용하기는 무리가 있다.
그래서... 비슷한거 하나 만들어 버렸다.
C로... :-)

얼마전에 배운 TDD도 살짝 도입하고... cgreen이라는 Test framework도 사용하고... ㅋㅋ
코드는 정리되는대로...

#include
#include

#include "cgreen/cgreen.h"

#define FALSE 0
#define TRUE 1

void PrintArray(int *start, int *end)
{
while(start != end) {
printf("%d ", *start);
start++;
}
printf("\n");
}

/**
* [start, end]에 num이 있는지 검사.
* 있으면 TRUE, 없으면 FALSE를 return한다.
*/
int is_exist(int *start, int *end, int num)
{
while(start <= end) {
if(num == *start) return TRUE;
start++;
}

return FALSE;
}

/**
* [start, end]를 검색해서 중복되지 않고 end에 사용할수 있는
* 숫자를 return한다.
*
* 예를 들어 [0,1,2]면 *num은 3을 가진다.
*/
int guess_number(int *start, int *end, int *num)
{
int i = 0;
int try = *end;

for(i = *end; i < 10; i++) {
if(is_exist(start, end, i) == FALSE) {
*num = i;
return TRUE;
}
}

return FALSE;
}

/**
* [start, end)에 저장되어 있는 조합 다음의 조합을 구한다.
* 가능한 조합이 있으면 TRUE, 없으면 FALSE를 return하고
* 결과는 [start, end)에 저장된다.
*
* Ex)
* int A[4] = {1,2,4,6};
* next_perm(A, A+4)
* ==>
* A는 {1,2,4,7}이 저장된다.
*/
int next_perm(int *start, int *end)
{
int *adj_ptr = end-1;
int num = 0;

while(adj_ptr >= start && adj_ptr < end) {
/*
* start ~ adj_ptr까지 검색결과 마지막 자리에 넣을 숫자가
* 있는지 검사.
* 있으면 adj_ptr에 그 숫자를 넣고,
* 없으면 adj_ptr을 앞으로 이동하여 다시 검사한다.
*/
if(guess_number(start, adj_ptr, &num) == TRUE) {
*adj_ptr = num;
adj_ptr++;
if(adj_ptr == end) {
return TRUE;
}
}
else {
*adj_ptr = -1;
adj_ptr--;
}
}

return FALSE;
}

void test_is_exist()
{
int A[4] = {1,2,3,4};

assert_equal(is_exist(A, A+4, 4), 1);
assert_equal(is_exist(A, A+4, 3), 1);
assert_equal(is_exist(A, A+4, 1), 1);
assert_equal(is_exist(A, A+4, 0), 0);
}

void test_guess_number()
{
{
int A[4] = {1,2,0,4};
int result;

assert_equal(guess_number(A, A+3, &result), 1);
assert_equal(result, 5);
}

{
int B[4] = {1,2,3,9};
int result = 0;
assert_equal(guess_number(B, B+3, &result), 0);
assert_equal(result, 0);
}
}

void test_perm()
{
int A[4] = {1, 2, 3, 4};

assert_true(next_perm(A, A+4));
}

int main(int argc, char *argv[])
{
if(argc == 2 && strcmp(argv[1], "-test") == 0) {
TestSuite *suite = create_test_suite();
add_test(suite, test_is_exist);
add_test(suite, test_guess_number);
add_test(suite, test_perm);
run_test_suite(suite, create_text_reporter());

return 0;
}

int A[] = {0, 9, 8};
int N = sizeof(A) / sizeof(int);

printf("inital value...\n");
PrintArray(A, A+N);
printf("next permutation is...\n");
next_perm(A, A+N);
PrintArray(A, A+N);

/*
while(next_perm(A, A+N)) {
PrintArray(A, A+N);
}
*/
}