경우의 수

경우의 수 구하기

순열 : n개의 카드 중에서 r개를 뽑아 순서를 정해 나열할 수 있는 경우를 말한다. 중복 가능

중복순열 : n개의 카드 중에서 r개를 뽑아 순서를 정해 나열할 수 있는 경우를 말한다. 중복 불가능

조합 : n개의 카드 중에서 r개를 뽑아 순서에 상관없이 나열할 수 있는 경우를 말한다. 중복 가능

중복조합 : n개의 카드 중에서 r개를 뽑아 순서에 상관없이 나열할 수 있는 경우를 말한다. 중복 불가능

순열

#include <stdio.h>

int arrTotal[10]; 

int arrData[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};

void swap(int *i, int *j)

{

    int temp = *i;

    *i = *j;

    *j = temp;

}

/*arrTotal[]에서 q개 출력*/

void process(int q)

{

    for(int i = q-1; i>= 0; i--)

    {

            printf("%d ", arrTotal[i]);

     }

    printf("\n");

}

 /*arrData[]에서 앞에서부터 n개의 숫자 중 r개를 선택해서 순열을 출력하는 함수. q는 출력 시 출력 갯수 지정*/

void Perm(int n, int r, int q)

{

    if(r == 0)

    {

        process(q);

        return;

    }

    for(int i = n-1; i>=0; i--)

    {

        swap(&arrData[i], &arrData[n-1]);        //n-1을 모든 index와 swap해서 다양한 순서를 만든다.

        arrTotal[r-1] = arrData[n-1];    //T의 뒤에서부터 결과값 저장

        Perm(n-1, r-1, q);                    //다음  index로 진행

        swap(&arrData[i], &arrData[n-1]);

    }

}

int main(void)

{

    Perm(4, 3, 3); 

    return 0;

}

조합

int arrTotal[10]; //nPr을 이루는 각각의 경우를 저장

int arrData[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};

void process(int q){

    for(int i = q-1; i>= 0; i--){

            printf("%d ", arrTotal[i]);

    }

    printf("\n");

}

/*arrData[]에서 앞에서부터 n개의 숫자 중 r개를 선택해서 조합을 출력하는 함수. q는 출력 시 출력 갯수 지정*/

void Johap(int n, int r, int q){

    if(r == 0){

        process(q);

        return;

    }else if(n<r){

        return;

    }

    else {  //loop이 아님

        arrTotal[r-1] = arrData[n-1];

        Johap(n-1, r-1, q);              //n-1Cr-1: 현재 아이템을 선택한 경우

        Johap(n-1, r, q);                 //n-1Cr: 현재 아이템을 선택하지 않은 경우

    }

}

int main(void){

    Johap(4, 3, 3);

    return 0;

}