欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

排列组合实现

程序员文章站 2022-03-03 11:24:12
...

思想:

排列:首先从(N)个中取一个数,再在剩余的一次次取一个数,每取一个数就把这位标记为取过了,以免下次再取。取够K个数之后,把K个数输出,展示结果(所以需要提前有一个数组来存放结果)。然后再取寻找别的第K个数,依次在不断寻找别的第(K-1),(K-2),,,,,个数。取完一个数把标记位设为未取过。

void  pailie(int a[],int N,int K,int level)//(K==N)时为全排列
{
    if (level>=K)
    { 
        for (int j = 0; j < level; j++)
            printf("%d ", result[j]);
        printf("\n");
        return;
    }
    for (int i = 0; i < N; i++)
    {
        if (flag[i] == false)//该位未取过
        {
            flag[i] = true;
            result[level++] = a[i];//取出修改标记位
            pailie(a, N, K , level);//在未被使用过的里面再选择一个
            level--;//重新取别的位
            flag[i] = false;
        }
    }
}

组合:组合与排列不同的是:不分顺序。我们可以假设一直是从前往后选数,那么前面作为开头的数,后面就不可以再作为开头。比如:A,B,C,D。当我第一次选择第一个数为A的话,把以A为头的数选完之后,下一次选第一个数决不能是A。所以需要有一个变量来控制所选择的第一个数(下面的程序为Index)。然后再在第一个数(比如选择A)之后的数中挑选接下来的数。选择接下来的数与上面排列类似。

void  zuhe(int a[], int N, int K,int index,int deep)
{
    if (deep >= K)
    {
        for (int i = 0; i < K; i++)
        {
            printf("%d ", result[i]);
        }
        printf("\n");
        return;
    }
    for (int i = index; i <N; i++)
    {
        result[deep] = a[i];
        deep++;
        zuhe(a, N, K, index + 1, deep);
        deep--;
        index++;
    }
}

程序如下:

#include <stdio.h>
#include <stdlib.h>
int array[10];//判别是否取过
int result[10];//存结果
int sumpailie(int N,int K)//排列数
{
    if(K==1)
        return N;
    return sumpailie(N-1,K-1)*N;

}
int sumzuhe(int N, int K)//组合数
{
    if(K==0)
        return 1;
    if(N==K)
        return 1;
    return sumzuhe(N-1,K-1)+sumzuhe(N-1,K);

}
void  pailie(int a[],int N,int K,int level)
{
    //(K==N)时为全排列  level记录取了多少个数
    int i,j;
    if(level>=K)//取够了就输出
    {
        for(j=0;j<level;j++)
        {
            printf("%d ",result[j]);
        }
        printf("\n");
        return ;
    }
    for(i=0;i<N;i++)
    {
        if(array[i]==0)//为0则表示没取
        {
            array[i]=1;//标记为取过
            result[level]=a[i];//取出修改标志位
            level++;
            pailie(a,N,K,level);//在未使用的里面在选择一个
            level--;//重新取别的位
            array[i]=0;
        }
    }
}
void zuhe(int a[],int N,int K ,int index,int level)//数组A[],index为第一个取的位,evel记录取的位数
{
    int i,j;
    if(level>=K)
    {
        for(j=0;j<level;j++)
        {
            printf("%d ",result[j]);
        }
        printf("\n");
        return ;
    }
    for(i=index;i<N;i++)
    {
        result[level]=a[i];
        level++;
        zuhe(a,N,K,index+1,level);
        level--;
        index++;
    }
}
void main()
{
    int a[5] = { 1,2,3,4,5};
    printf("排列结果数(5,3):\n");
    printf("%d ", sumpailie(5, 3));
    printf("\n");
    printf("排列结果(5,3):\n");
    pailie(a, 5, 3, 0);
    printf("全排列结果:\n");
    pailie(a, 5, 5, 0);

    printf("组合结果数(5,3):\n");
    printf("%d ", sumzuhe(5, 3));
    printf("\n");
	printf("组合结果(5,3):\n");
    zuhe(a, 5, 3, 0, 0);
    printf("\n");
}