排列.txt

排列问题 M个1,N个0的排列(高效率版) 排列数为:c(m+n,n) 对n个0,m个1,我的想法是这样的: 每个排列可以分三段: 全0列,全1列, 子问题列 设各段长:r,s,t .子问

// 自己写着玩的一个产生排列、组合序列的小程序 ^_^
#include <stdio.h>
#include <math.h>

int arr[]={1,2,3,4,5};
#define LEN (sizeof(arr)/sizeof(*arr))

int arr2[LEN]; // only used by combination()

int count1=0;  // counter for combination sequential.
int count2=0;  // counter for permutation sequential.

void combination(int* p,int len, int n, int pos)
{
        int i;

        if(pos==n)
        {
                for(i=0; i<pos; i++) printf("%d",arr2[i]);
                printf("\n");
                count1++;
                return;
        }

        //if the final sequential contains *p
        arr2[pos]=*p;
        combination(p+1,len-1,n,pos+1);

        //if the final sequential doesn't contain *p
        if(len-1>=n-pos) combination(p+1,len-1,n,pos);
}
void permutation(int *p, int len, int n, int pos)
{
        int i;
        int t;

        if(pos==n)
        {
                //here we know  p-n=arr;
                for(i=-n; i<0; i++) printf("%d",p[i]);
                printf("\n");
                count2++;
                return;
        }

        //The strategy is swapping all the numbers in a sequential 1-by-1
        // to the leading portion of arr.
        for(i=0; i<len; i++)
        {
                t=p[0]; p[0]=p[i]; p[i]=t;
                permutation(p+1,len-1,n,pos+1);
                t=p[0]; p[0]=p[i]; p[i]=t;
        }
}
int main(int argc, char* argv[])
{
        int m1=LEN, m2=LEN, n=3;

        combination(arr,m1,n,0);        //C(5,3)
        printf("C(%d,%d)=%d\n\n",m1,n,count1);

        permutation(arr,m2,n,0);        //P(5,3)
        printf("P(%d,%d)=%d\n\n",m2,n,count2);

        return 0;
}
/*
  the output is as follows:
123
124
125
134
135
145
234
235
245
345
C(5,3)=10
123
124
125
132
134
135
143
142
145
153
154
152
213
214
215
231
234
235
243
241
245
253
254
251
321
324
325
312
314
315
341
342
345
351
354
352
423
421
425
432
431
435
413
412
415
453
451
452
523
524
521
532
534
531
543
542
541
513
514
512
P(5,3)=60
*/