[순열과 조합] 순열과 조합 알고리즘

순열 Permutation

#include <stdio.h>
 
#define N 4
#define R 3
 
int number[10]; 
int data[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
 
void swap(int *first, int *second) {
    int temp = *first;
    *first = *second;
    *second = temp;
}
 
void print(int n)
{
    for (int i = n - 1; i >= 0; i--) {
        printf("%d ", number[i]);
    }
    printf("\n");
}
 
void permutation(int n, int r, int q) 
{
    if (r == 0) {
        print(q);
        return;
    }
 
    for (int i = n - 1; i >= 0; i--) {
        swap(&data[i], &data[n - 1]);
        number[r - 1] = data[n - 1];    
        permutation(n - 1, r - 1, q);
        swap(&data[i], &data[n - 1]);
    }
}
 
int main(void) 
{
    permutation(N, R, 3);
 
    return 0;
}

조합 Combination

#include  <stdio.h>
 
#define N 4
#define R 3
 
int number[10];
int data[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
 
void print(int n) 
{
    for (int i = n - 1; i >= 0; i--) {
        printf("%d ", number[i]);
    }
    printf("\n");
}
 
void combination(int n, int r, int q) 
{
    if (r == 0) {
        print(q);
        return;
    }
    else if (n < r) {
        return;
    }
    else {  
        number[r - 1] = data[n - 1];
        combination(n - 1, r - 1, q);  
        combination(n - 1, r, q);    
    }
}
 
int main(void) 
{
    combination(N, R, 3);
 
    return 0;
}

중복 조합

#include <stdio.h>
 
#define N 4
#define R 3
 
int number[10];
int data[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
 
void print(int n)
{
    for (int i = 0; i < n; i++) {
        printf("%d ", number[i]);
    }
    printf("\n");
}
 
void comb(int n, int r, int q)
{
    int i;
    if (r == q) {
        print(q);
        return;
    }
 
    for (i = 0; i < n; i++) {
        number[r] = data[i];
        comb(n, r + 1, q);
    }
}
 
int main()
{
    comb(N, 0, R);
 
    return 0;
}