과제로 서로 다른 5개의 수를 가진 배열의 정렬을 위한 Decision Tree를 그려야 했다. 하지만 손으로 그리는게 너무 귀찮은 나머지 코드로 작성해버렸다. 작성언어는 Javascript(ES6)이며, 정렬이 잘 되는지 보기 위한 테스트 코드도 포함되어 있다.
아래 단색의 긴 코드가 너무 보기 힘들 수 있으므로, 사진 파일도 첨부했다.
compare = (list, num) => {
return (list[parseInt(num / 10) - 1] < list[(num % 10) - 1]);
};
f = (list) => {
if (compare(list, 12)) {
if (compare(list, 34)) {
if (compare(list, 25)) {
// 1/2/5, 3/4
if (compare(list, 35)) {
// (1/2)3/5, 3/4
if (compare(list, 23)) {
// 1/2/3/54
if (compare(list, 45)) {
return "1/2/3/4/5";
} else {
return "1/2/3/5/4";
}
} else {
// 13/2/5, 3/4
if (compare(list, 24)) {
// 13/2/45
if (compare(list, 13)) {
if (compare(list, 45)) {
return "1/3/2/4/5";
} else {
return "1/3/2/5/4";
}
} else {
if (compare(list, 45)) {
return "3/1/2/4/5";
} else {
return "3/1/2/5/4";
}
}
} else {
// 1(3/4)/2/5
if (compare(list, 13)) {
return "1/3/4/2/5";
} else {
if (compare(list, 14)) {
return "3/1/4/2/5";
} else {
return "3/4/1/2/5";
}
}
}
}
} else {
return "1/2/5/3/4";
}
} else {
// 15/2, 3/4
if (compare(list, 32)) {
// 153/2, 3/4
if (compare(list, 53)) {
// 1(5/3)/2, 3/4
if (compare(list, 15)) {
// 1/5/3/24
if (compare(list, 24)) {
return "1/5/3/2/4";
} else {
return "1/5/3/4/2";
}
} else {
// 5/13/2, 3/4
if (compare(list, 13)) {
// 5/1/3/24
if (compare(list, 24)) {
return "5/1/3/2/4";
} else {
return "5/1/3/4/2";
}
} else {
// 5/3/(1/2)4
if (compare(list, 24)) {
return "5/3/1/2/4";
} else {
// 5/3/14/2
if (compare(list, 14)) {
return "5/3/1/4/2";
} else {
return "5/3/4/1/2";
}
}
}
}
} else {
// (3/5)1/2, 3/4
if (compare(list, 13)) {
// 1/3/(5/2)4
if (compare(list, 24)) {
return "1/3/5/2/4";
} else {
// 1/3/45/2
if (compare(list, 45)) {
return "1/3/4/5/2";
} else {
return "1/3/5/4/2";
}
}
} else {
// 3/(15/2)4
if (compare(list, 15)) {
// 3/(1/5/2)4
if (compare(list, 45)) {
// 3/14/5/2
if (compare(list, 14)) {
return "3/1/4/5/2";
} else {
return "3/4/1/5/2";
}
} else {
// 3/1/5/24
if (compare(list, 24)) {
return "3/1/5/2/4";
} else {
return "3/1/5/4/2";
}
}
} else {
// 3/(5/1/2)4
if (compare(list, 14)) {
// 3/5/1/24
if (compare(list, 24)) {
return "3/5/1/2/4";
} else {
return "3/5/1/4/2";
}
} else {
// 3/45/1/2
if (compare(list, 45)) {
return "3/4/5/1/2";
} else {
return "3/5/4/1/2";
}
}
}
}
}
} else {
// 15/2/3/4
if (compare(list, 15)) {
return "1/5/2/3/4";
} else {
return "5/1/2/3/4";
}
}
}
} else {
if (compare(list, 25)) {
// 1/2/5, 4/3
if (compare(list, 42)) {
// 14/2/5, 4/3
if (compare(list, 32)) {
// 14/2, 4/3/2/5
if (compare(list, 14)) {
return "1/4/3/2/5";
} else {
// 4/13/2/5
if (compare(list, 13)) {
return "4/1/3/2/5";
} else {
return "4/3/1/2/5";
}
}
} else {
// 14/2/35
if (compare(list, 14)) {
// 1/4/2/35
if (compare(list, 35)) {
return "1/4/2/3/5";
} else {
return "1/4/2/5/3";
}
} else {
// 4/1/2/35
if (compare(list, 35)) {
return "4/1/2/3/5";
} else {
return "4/1/2/5/3";
}
}
}
} else {
// 1/2/5(4/3)
if (compare(list, 35)) {
return "1/2/4/3/5";
} else {
// 1/2/54/3
if (compare(list, 45)) {
return "1/2/4/5/3";
} else {
return "1/2/5/4/3";
}
}
}
} else {
// 15/2, 4/3
if (compare(list, 42)) {
// 154/2, 4/3
if (compare(list, 15)) {
// (1/5)4/2, 4/3
if (compare(list, 45)) {
// 14/5/2, 4/3
if (compare(list, 35)) {
// 1(4/3)/5/2
if (compare(list, 14)) {
return "1/4/3/5/2";
} else {
// 4/13/5/2
if (compare(list, 13)) {
return "4/1/3/5/2";
} else {
return "4/3/1/5/2";
}
}
} else {
// 14/5/23
if (compare(list, 14)) {
// 1/4/5/23
if (compare(list, 23)) {
return "1/4/5/2/3";
} else {
return "1/4/5/3/2";
}
} else {
// 4/1/5/23
if (compare(list, 23)) {
return "4/1/5/2/3";
} else {
return "4/1/5/3/2";
}
}
}
} else {
// 1/5/4/23
if (compare(list, 23)) {
return "1/5/4/2/3";
} else {
return "1/5/4/3/2";
}
}
} else {
// (5/1)4/2, 4/3
if (compare(list, 14)) {
// 5/1/4/23
if (compare(list, 23)) {
return "5/1/4/2/3";
} else {
return "5/1/4/3/2";
}
} else {
// 54/1/2, 4/3
if (compare(list, 45)) {
// 4/(5/1/2)3
if (compare(list, 13)) {
// 4/5/1/23
if (compare(list, 23)) {
return "4/5/1/2/3";
} else {
return "4/5/1/3/2";
}
} else {
// 4/35/1/2
if (compare(list, 35)) {
return "4/3/5/1/2";
} else {
return "4/5/3/1/2";
}
}
} else {
// 5/4/(1/2)3
if (compare(list, 23)) {
return "5/4/1/2/3";
} else {
// 5/4/13/2
if (compare(list, 13)) {
return "5/4/1/3/2";
} else {
return "5/4/3/1/2";
}
}
}
}
}
} else {
// 15/2/4/3
if (compare(list, 15)) {
return "1/5/2/4/3";
} else {
return "5/1/2/4/3";
}
}
}
}
} else {
if (compare(list, 34)) {
if (compare(list, 15)) {
// 2/1/5, 3/4
if (compare(list, 35)) {
// (2/1)3/5, 3/4
if (compare(list, 13)) {
// 2/1/3/54
if (compare(list, 45)) {
return "2/1/3/4/5";
} else {
return "2/1/3/5/4";
}
} else {
// 23/1/5, 3/4
if (compare(list, 23)) {
// 2/3/(1/5)4
if (compare(list, 45)) {
// 2/3/14/5
if (compare(list, 14)) {
return "2/3/1/4/5";
} else {
return "2/3/4/1/5";
}
} else {
return "2/3/1/5/4";
}
} else {
// 3/(2/1/5)4
if (compare(list, 14)) {
if (compare(list, 45)) {
return "3/2/1/4/5";
} else {
return "3/2/1/5/4";
}
} else {
if (compare(list, 24)) {
return "3/2/4/1/5";
} else {
return "3/4/2/1/5";
}
}
}
}
} else {
return "2/1/5/3/4";
}
} else {
// 25/1, 3/4
if (compare(list, 25)) {
// 2/5/1, 3/4
if (compare(list, 35)) {
// 23/5/1, 3/4
if (compare(list, 23)) {
if (compare(list, 45)) {
return "2/3/4/5/1";
} else {
// 2/3/5/14
if (compare(list, 14)) {
return "2/3/5/1/4";
} else {
return "2/3/5/4/1";
}
}
} else {
// 3/2/5/1, 3/4
if (compare(list, 45)) {
// 3/24/5/1
if (compare(list, 24)) {
return "3/2/4/5/1";
} else {
return "3/4/2/5/1";
}
} else {
// 3/2/5/14
if (compare(list, 14)) {
return "3/2/5/1/4";
} else {
return "3/2/5/4/1";
}
}
}
} else {
// 2/5/13, 3/4
if (compare(list, 13)) {
return "2/5/1/3/4";
} else {
if (compare(list, 14)) {
return "2/5/3/1/4";
} else {
return "2/5/3/4/1";
}
}
}
} else {
// 5/2/1, 3/4
if (compare(list, 23)) {
// 5/2/13, 3/4
if (compare(list, 13)) {
return "5/2/1/3/4";
} else {
if (compare(list, 14)) {
return "5/2/3/1/4";
} else {
return "5/2/3/4/1";
}
}
} else {
// 53/2/1, 3/4
if (compare(list, 35)) {
// 3/(5/2/1)4
if (compare(list, 24)) {
// 3/5/2/14
if (compare(list, 14)) {
return "3/5/2/1/4";
} else {
return "3/5/2/4/1";
}
} else {
// 3/45/2/1
if (compare(list, 45)) {
return "3/4/5/2/1";
} else {
return "3/5/4/2/1";
}
}
} else {
// 5/3/(2/1)4
if (compare(list, 14)) {
return "5/3/2/1/4";
} else {
if (compare(list, 24)) {
return "5/3/2/4/1";
} else {
return "5/3/4/2/1";
}
}
}
}
}
}
} else {
if (compare(list, 15)) {
// 2/1/5, 4/3
if (compare(list, 45)) {
// (2/1)4/5, 4/3
if (compare(list, 24)) {
// 2/14/5, 4/3
if (compare(list, 14)) {
// 2/1/4/35
if (compare(list, 35)) {
return "2/1/4/3/5";
} else {
return "2/1/4/5/3";
}
} else {
// 2/4/(1/5)3
if (compare(list, 35)) {
// 2/4/13/5
if (compare(list, 13)) {
return "2/4/1/3/5";
} else {
return "2/4/3/1/5";
}
} else {
return "2/4/1/5/3";
}
}
} else {
// 4/(2/1/5)3
if (compare(list, 13)) {
// 4/2/1/35
if (compare(list, 35)) {
return "4/2/1/3/5";
} else {
return "4/2/1/5/3";
}
} else {
// 4/23/1/5
if (compare(list, 23)) {
return "4/2/3/1/5";
} else {
return "4/3/2/1/5";
}
}
}
} else {
return "2/1/5/4/3";
}
} else {
// 25/1, 4/3
if (compare(list, 41)) {
// 254/1, 4/3
if (compare(list, 25)) {
// (2/5)4/1, 4/3
if (compare(list, 45)) {
// 24/5/1, 4/3
if (compare(list, 24)) {
// 2/4/(5/1)3
if (compare(list, 13)) {
return "2/4/5/1/3";
} else {
// 2/4/53/1
if (compare(list, 35)) {
return "2/4/3/5/1";
} else {
return "2/4/5/3/1";
}
}
} else {
// 4/(2/5/1)3
if (compare(list, 35)) {
// 4/23/5/1
if (compare(list, 23)) {
return "4/2/3/5/1";
} else {
return "4/3/2/5/1";
}
} else {
// 4/2/5/13
if (compare(list, 13)) {
return "4/2/5/1/3";
} else {
return "4/2/5/3/1";
}
}
}
} else {
// 2/5/4/13
if (compare(list, 13)) {
return "2/5/4/1/3";
} else {
return "2/5/4/3/1";
}
}
} else {
// (5/2)4/1, 4/3
if (compare(list, 45)) {
// 4/(5/2/1)3
if (compare(list, 23)) {
// 4/5/2/13
if (compare(list, 13)) {
return "4/5/2/1/3";
} else {
return "4/5/2/3/1";
}
} else {
// 4/35/2/1
if (compare(list, 35)) {
return "4/3/5/2/1";
} else {
return "4/5/3/2/1";
}
}
} else {
// 5/24/1, 4/3
if (compare(list, 24)) {
// 5/2/4/13
if (compare(list, 13)) {
return "5/2/4/1/3";
} else {
return "5/2/4/3/1";
}
} else {
// 5/4/(2/1)3
if (compare(list, 13)) {
return "5/4/2/1/3";
} else {
// 5/4/23/1
if (compare(list, 23)) {
return "5/4/2/3/1";
} else {
return "5/4/3/2/1";
}
}
}
}
}
} else {
// 25/1/4/3
if (compare(list, 25)) {
return "2/5/1/4/3";
} else {
return "5/2/1/4/3";
}
}
}
}
}
};
sort = (list) => {
let result_f = f(list).split("/");
let return_list = [];
let i;
for (i = 0; i < 5; i++)
return_list[i] = list[result_f[i] - 1];
return return_list;
};
let expected_result, sorted;
let i, j, k, s, t, r;
for (i = 0; i < 5; i++) {
for (j = 0; j < 5; j++) {
if (j == i) continue;
for (k = 0; k < 5; k++) {
if (k == i || k == j) continue;
for (s = 0; s < 5; s++) {
if (s == i || s == j || s == k) continue;
for (t = 0; t < 5; t++) {
if (t == i || t == j || t == k || t == s) continue;
console.log(i+"/"+j+"/"+k+"/"+s+"/"+t+": ");
sorted = sort([i, j, k, s, t]);
for (r = 0; r < 5; r++)
if (sorted[r] != r)
{
console.log(`fail. sorted = ${sorted}`);
break;
}
if (r == 5)
console.log(`success.`);
}
}
}
}
}