递归求解排列和组合

/*类循环排列*/
Input:
3 2
Output:
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

#include <stdio.h>

#define MAX 10

int rcd[MAX];
int n, m; //n位数，有0-m-1数字构成

void loop_permutation(int l)
{
    int i;
    if(l == n)
    {
        for(i=0; i<n; i++)
        {
            printf("%d", rcd[i]);
            if(i < l-1)
            {
                printf(" ");
            }
        }
        printf("n");
        return ;
    }
    for(i=0; i<m; i++)
    {
        rcd[l] = i;
        loop_permutation(l+1);
    }
}

int main()
{
    while(scanf("%d %d", &n, &m) == 2)
    {
        loop_permutation(0);
    }
    return 0;
}

--------------------------------------------------

/*全排列*/
Input:
3
1 2 3
Output:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

#include <stdio.h>
#include <stdlib.h>

#define MAX 10

int rcd[MAX];
int used[MAX];
int num[MAX];
int n;

void full_permutation(int l)
{
    int i;
    if(l == n)
    {
        for(i=0; i<n; i++)
        {
            printf("%d", rcd[i]);
            if(i < n-1)
            {
                printf(" ");
            }
        }
        printf("n");
        return ;
    }
    for(i=0; i<n; i++)
    {
        if(!used[i])
        {
            used[i] = 1;
            rcd[l] = num[i];
            full_permutation(l+1);
            used[i] = 0;
        }
    }
}

int main()
{
    int i;
    while(scanf("%d", &n) != EOF)
    {
        for(i=0; i<n; i++)
        {
            scanf("%d", &num[i]);
        }
        memset(used, 0, sizeof(used));
        full_permutation(0);
    }
    return 0;
}

--------------------------------------------------

/*不重复全排列*/
Input:
3
1 1 2
Output:
1 1 2
1 2 1
2 1 1
 

#include <stdio.h>
#include <stdlib.h>

#define MAX 10

int rcd[MAX];
int used[MAX];
int num[MAX]; //存放互不相同的m个数
int n, m; //n个数，互不相同有m个

void unrepeat_full_permutation(int l)
{
    int i;
    if(l == n)
    {
        for(i=0; i<n; i++)
        {
            printf("%d", rcd[i]);
            if(i < n-1)
            {
                printf(" ");
            }
        }
        printf("n");
        return ;
    }
    for(i=0; i<n; i++)
    {
        if(used[i] > 0)
        {
            used[i]--;
            rcd[l] = num[i];
            unrepeat_full_permutation(l+1);
            used[i]++;
        }
    }
}

int main()
{
    int i, j, val;
    while(scanf("%d", &n) != EOF)
    {
        m = 0;
        memset(used, 0, sizeof(used));
        for(i=0; i<n; i++)
        {
            scanf("%d", &val);
            for(j=0; j<m; j++)
            {
                if(num[j] == val)
                {
                    used[j]++;
                    break;
                }
            }
            if(j == m)
            {
                num[m] = val;
                used[m++] = 1;
            }
        }
        unrepeat_full_permutation(0);
    }
}

--------------------------------------------------

/*组合*/
Input:
4 3
1 2 3 4
Output:
1 2 3
1 2 4
1 3 4
2 3 4
 

#include <stdio.h>

#define MAX 10

int rcd[MAX];
int num[MAX];
int n, m; //从n个数中选m个数

void select_combination(int l, int z)
{
    int i;
    if(l == m) //已选m个数
    {
        for(i=0; i<m; i++)
        {
            printf("%d", rcd[i]);
            if(i < m-1)
            {
                printf(" ");
            }
        }
        printf("n");
        return ;
    }
    for(i=z; i<n; i++) //上次为num[z-1],此次从num[z]开始
    {
        rcd[l] = num[i];
        select_combination(l+1, i+1); //i+
    }
}

int main()
{
    int i;
    while(scanf("%d %d", &n, &m) != EOF)
    {
        for(i=0; i<n; i++)
        {
            scanf("%d", &num[i]);
        }
        select_combination(0, 0);
    }
    return 0;
}

--------------------------------------------------

/*全组合*/
Input:
3
1 2 3
Output:
1
1 2
1 2 3
1 3
2
2 3
3
 

#include <stdio.h>

#define MAX 10

int rcd[MAX];
int num[MAX];
int n;

void full_combination(int l, int z)
{
    int i;
    for(i=0; i<l; i++)
    {
        printf("%d", rcd[i]);
        if(i < l-1)
        {
            printf(" ");
        }
    }
    printf("n");
    for(i=z; i<n; i++) //i=
    {
        rcd[l] = num[i];
        full_combination(l+1, i+1);
    }
}

int main()
{
    int i;
    while(scanf("%d", &n) != EOF)
    {
        for(i=0; i<n; i++)
        {
            scanf("%d", &num[i]);
        }
        full_combination(0, 0);
    }
    return 0;
}

--------------------------------------------------

/*不重复组合*/
Input:
3
1 1 3
Output:
1
1 1
1 1 3
1 3
3

#include <stdio.h>
#include <stdlib.h>

#define MAX 10

int rcd[MAX];
int num[MAX];
int used[MAX];
int n, m; //n个数中有m个不同的数

void unrepeat_combination(int l, int z)
{
    int i;
    for(i=0; i<l; i++)
    {
        printf("%d", rcd[i]);
        if(i < l-1)
        {
            printf(" ");
        }
    }
    printf("n");
    for(i=z; i<m; i++)
    {
        if(used[i] > 0)
        {
            used[i]--;
            rcd[l] = num[i];
            unrepeat_combination(l+1, i); //l+
            used[i]++;
        }
    }
}

int main()
{
    int i, j, val;
    while(scanf("%d", &n) != EOF)
    {
        m = 0;
        memset(used, 0, sizeof(used));
        for(i=0; i<n; i++)
        {
            scanf("%d", &val);
            for(j=0; j<m; j++)
            {
                if(num[j] == val)
                {
                    used[j]++;
                    break;
                }
            }
            if(j == m)
            {
                num[m] = val;
                used[m++] = 1;
            }
        }
        unrepeat_combination(0, 0);
    }
    return 0;
}

2011-05-12 18:23  发表于百度空间，今搬至CU。