Permutation

m개의 main dish 와 n개의 side dish 가 있다.
main dish 와 side dish 는 중복선택 불가하다고 할 때, main dish 와 side dish 로 가능한 모든 조합을 구해보자.

예를 들어, 2개의 main dish와 3개의 side dish가 있다면,
경우의 수는 3x2 = 6 이고, 모든 경우의 수는
{(m1, s1), (m2, s2)}
{(m1, s1), (m2, s3)}
{(m1, s2), (m2, s1)}
{(m1, s2), (m2, s3)}
{(m1, s3), (m2, s1)}
{(m1, s3), (m2, s2)}
for (int m1=s1; m1<=s3; m1++)
    for (int m2=s1; m2<=s3; m2++)
        if (m1==m2) continue;
        printf("(m1, %d), (m2, %d)", m1, m2)

3개의 main dish와 3개의 side dish가 있다면, 3x2x1 = 6가지 경우이며,
{(m1, s1), (m2, s2), (m3, s3)}
{(m1, s1), (m2, s3), (m3, s2)}
{(m1, s2), (m2, s1), (m3, s3)}
{(m1, s2), (m2, s3), (m3, s1)}
{(m1, s3), (m2, s1), (m3, s2)}
{(m1, s3), (m2, s2), (m3, s1)}
for (int m1=s1; m1<=s3; m1++)
    for (int m2=s1; m2<=s3; m2++)
        if (m1==m2) continue;
        for (int m3=s1; m3<=s3; m3++)
            if (m3==m1 || m3==m2) continue;
            printf("(m1, %d), (m2, %d), (m3, %d)", m1, m2, m3)

for loop 로 구현하면 m,n 값에 맞게 일일이 iterator 변수를 추가해주어야 하는 문제가 있음.
main dish2는 main dish1과 조합을 이루지 않은 side dish 중 한 개,
main dish3은 main dish1, main dish2와 조합을 이루지 않은 side dish 중 한 개 이므로
재귀로 구현해보면, 아래와 같음. (좀 더 간결하게 되려나)

#include <stdio.h>

void select(int id, int selected[3])
{
    if (id == 2) {
        int temp;
        for (int iter = 0; iter < 3; iter++) {
            if (selected[iter] == -1) {
                temp = iter;
                break;
            }
        }
        selected[temp] = id;
        for (int iter = 0; iter < 3; iter++) {
            printf("(%d %d) ", iter, selected[iter]);
        }
        printf("\n");
        selected[temp] = -1;
        return;
    }
    for (int iter = 0; iter < 3; iter++) {
        if (selected[iter] == -1) {
            selected[iter] = id;
            select(id+1, selected);
            selected[iter] = -1;
        }
    }
}

int main()
{
    int selected[3] = {-1, -1, -1};
    select(0, selected);
    return 0;
}

printf 부분 대신 다른 로직을 넣으면 permutation 경우의 수마다 특정 처리를 하는게 가능해보임. 예를 들면, main dish + side dish 조합 중 가장 가격이 싼 경우를 구할 때, printf 대신에 lowest_total_price 를 갱신하도록 하면 됨.

일단 코드를 좀 더 간결하게 하는 게 필요함.
또한 재귀 깊이가 어느 정도까지 가능한 지도 업데이트 할 것.