//排列组合问题
//没有考虑重复元素删除
#include <stdio.h>

#include <stdlib.h>

//从n个元素的数组a中，取m个元素的组合

bool zuhe(char a[],int n,int m)

{//p[x]=y 取到的第x个元素，是a中的第y个元素

    int index,i,*p;



    p=(int*)malloc(sizeof(int)*m);

    if(p==NULL)

    {

        return false;

    }

    index=0;

    p[index]=0;//取第一个元素

    while(true)

    {

        if(p[index]>=n)

        {//取到底了，回退

            if(index==0)

            {//各种情况取完了，不能再回退了

                break;

            }

            index--;//回退到前一个

            p[index]++;//替换元素

        }

        else if(index==m-1)

        {//取够了，输出

            for(i=0;i<m;i++)

            {

                printf("%c",a[p[i]]);

            }

            printf("\n");

            p[index]++; //替换元素

        }

        else

        {//多取一个元素

            index++;

            p[index]=p[index-1]+1;

        }



    }

    free(p);

    return true;

}

//对n个元素的数组a，进行全排列

bool pailie(char a[],int n)

{//p[x]=y 取到的第x个元素，是a中的第y个元素

    int i,j,temp,*p;



    p=(int*)malloc(sizeof(int)*n);

    if(p==NULL)

    {

        return false;

    }

    for(i=0;i<n;i++)

    {//初始排列

        p[i]=i;

    }

    while(true)

    {//循环m=n!次

        //输出一种排列情况

        for(i=0;i<n;i++)

        {

            printf("%c",a[p[i]]);

        }

        printf("\n");

        //从后向前查找，看有没有后面的数大于前面的数的情况，若有则停在后一个数的位置。

        for(i=n-1;i>0 && p[i]<p[i-1];i--);



        //若没有后面的数大于前面的数的情况，说明已经到了最后一个排列，返回

        if(i==0) break;



        //从后查到i，查找大于p[i - 1]的最小的数，记入j

        for(j=n-1;j>i && p[j]<p[i-1];j--);



        //交换p[i-1]和p[j]

        temp=p[i-1];p[i-1]=p[j];p[j]=temp;



        //倒置p[i]到p[n-1]

        for(i=i,j=n-1;i<j;i++,j--)

        {//交换p[c]和p[d]

            temp=p[i];p[i]=p[j];p[j]=temp;

        }

    }

    free(p);

    return true;

}

int main()

{

    char a[]="1111";



    zuhe(a,4,2);//组合

    pailie(a,3);//排列

    return 0;

}