快捷導(dǎo)航

排列組合總結(jié):將結(jié)果進(jìn)行輸出的實(shí)現(xiàn)方法

更新時(shí)間：2013年05月08日 16:21:14 作者：

本篇文章關(guān)于排列組合的總結(jié)，對(duì)結(jié)果進(jìn)行輸出做了介紹。需要的朋友參考下

全排列輸出：

解法一:

<SPAN style="COLOR: #333333">#include <stdio.h>

/*
   遞歸思想：
   取出數(shù)組第一個(gè)元素放到最后一個(gè)元素即a[0] 和a[n]交換然后一次遞歸a[n] 個(gè)元素的全排列
1   如果數(shù)組只有一個(gè)元素 n=1 a={1} 則全排列就是{1}
2 如果有兩個(gè)元素 n=2 a={1,2} 則全排列是
       {2,1} a[1]與a[2]交換交換后求a[2-1]={2}的全排列歸結(jié)到 1
       {1,2} a[2]與a[2]交換交換后求a[2-1]={1}的全排列歸結(jié)到 1
3 如果有三個(gè)元素 n=3 a={1,2,3} 則全排列是
     {{2,3},1} a[1]和a[3]交換交換后求a[3-1]={2,3} 的全排列歸結(jié)到 2
{{1,3},2} a[2] a[3] 交換交換后求 a[3-1]={1,3} 的全排列歸結(jié)到 2
{1,2},3}   a[3] a[3] 交換交換后求 a[3-1]={1,2} 的全排列歸結(jié)到 2
*/
void swap(int a[],int size)
{
int i,t;
if(size==0)
{
  for(i=0;i<5;i++)
  {
   printf("%c ",a[i]);
  }
  printf("\n");
  return;
}
else
{
  for(i=0;i<=size;i++) //元素進(jìn)行全部循環(huán)
  {
   //寫在swap()之前，進(jìn)行遞歸傳值出口點(diǎn)要傳入函數(shù)
   t=a[i];a[i]=a[size];a[size]=t;
   swap(a,size-1);
   //數(shù)組元素還原開始是什么現(xiàn)在還是什么位置改變后變成原來(lái)位置
   // 便于從a[1] 到a[n] 和最后一個(gè)元素交換位置
   t=a[i];a[i]=a[size];a[size]=t;

}
}
}
int main()
{
int a[5],i;
for(i=0;i<5;i++)
{
a[i]=97+i;
}
swap(a,4);
//printf("\n%d",m);
return 0;
}</SPAN>

解法二：

復(fù)制代碼代碼如下:

<SPAN style="COLOR: #333333">#include <stdio.h>
//思路分別求出以1 2 3 4 5 開頭剩下數(shù)字的全排列一直到簡(jiǎn)化為一個(gè)數(shù)字
void swap(int a[],int k)
{
int i,m,t=0;
if(k==5)
{
  for(i=0;i<5;i++)
  {
   printf("%d ",a[i]);
  }
  //k++;
  printf("\n");
}
for(i=k;i<5;i++)
{
  {m=a[k];a[k]=a[i];a[i]=m;}
  swap(a,k+1);
  {m=a[k];a[k]=a[i];a[i]=m;}
}
}

int main()
{
int a[5]={1,2,3,4,5}; //進(jìn)行遞歸運(yùn)算的數(shù)值
swap(a,0); //函數(shù)調(diào)用
return 0;
}
</SPAN>

m個(gè)數(shù)中取n個(gè)進(jìn)行排列：

復(fù)制代碼代碼如下:

#include <stdio.h>
void swap(int a[],int b[],int i,int size)
{
int k,j,temp;
if(i==3)
{
   for(k=0;k<3;k++)
   {
    printf("%d ",b[k]);
   }
   printf("\n");
  return;
}
else
{
  for(j=0;j<size;j++)
  {
   b[i]=a[j];
   temp=a[j];a[j]=a[size-1];a[size-1]=temp;
   swap(a,b,i+1,size-1);
   temp=a[j];a[j]=a[size-1];a[size-1]=temp;
  }
}
}

int main()
{
int a[5]={1,2,3,4,5},b[3];//求5個(gè)數(shù)中三個(gè)數(shù)的全排列
swap(a,b,0,5);
return 0;
}

m個(gè)數(shù)取n個(gè)進(jìn)行組合：

[10反轉(zhuǎn)置換法]

算法思想：

     (1) 初始化一個(gè)m個(gè)元素的數(shù)組（全部由0，1組成），將前n個(gè)初始化為1，后面的為0。這時(shí)候就可以輸出第一個(gè)組合序列了。
     (2) 從前往后找，找到第一個(gè)10組合，將其反轉(zhuǎn)成01，然后將這個(gè)10組合前面的所有1，全部往左邊推，即保證其前面的1都在最左邊。這時(shí)又可以輸出一組組合序列了。
     (3) 重復(fù)第(2)步，知道找不到10組合位置。這時(shí)已經(jīng)輸出了全部的可能

復(fù)制代碼代碼如下:

#include <stdio.h>
#include <stdlib.h>
void putout(int * num,int m)
{
int i;
for(i=0;i<m;i++)
{
if(*(num+i))
printf("%d ",i+1);

}
printf("\n");
}

int check(int *num,int m,int n)
{
int flag=1,i;//當(dāng)flag=1時(shí)，繼續(xù)while循環(huán) 反之，退出循環(huán)
    for(i=0;i<m-n;i++)
{
  if(*(num+i))
  {
          return 1;
  }
}
return 0;
}

void choseNum(int *num,int m,int n)
{
int i,j;
    putout(num,m); //輸出第一個(gè)組合
while(1)
{
  int count=0; //注意count位置就他調(diào)試了半天
  //找第一個(gè)1 0組合
  for(i=0;i<m-1;i++)
  {
   if(*(num+i)==1&&*(num+i+1)==0)
   {
    *(num+i)=0;
    *(num+i+1)=1;
    break;
   }
   if(*(num+i)) //統(tǒng)計(jì)前面出現(xiàn)出現(xiàn)1的次數(shù)
   count++;
  }
  for(j=0;j<i;j++)
  {
   if(j<count) //將前面幾個(gè)數(shù)全為1
   {
    *(num+j)=1;
   }
   else       //后幾個(gè)數(shù)為0
   {
    *(num+j)=0;
   }
  }
  putout(num,m);
  if(check(num,m,n)!=1)
   break;
}
free(num);
}

int main()
{
int m,n;//從m個(gè)數(shù)中找n個(gè)求組合
printf("從m個(gè)數(shù)中n個(gè)數(shù)的組合：");
scanf("%d %d",&m,&n);
    int *num,i;
//int count;
num=(int *)malloc(sizeof(int)*m);
for(i=0;i<m;i++)
{
  if(i<n)
   *(num+i)=1;
  else
   *(num+i)=0;
}
choseNum(num,m,n);
    return 0;
}