排列组合总结:将结果进行输出的实现方法

全排列输出:

解法一:


代码如下:

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

/*
   递归思想:
   取出数组第一个元素放到最后一个元素 即a[0] 和a[n]交换  然后一次递归a[n] 个元素的全排列
  1   如果数组只有一个元素 n=1 a={1} 则全排列就是{1}
  2  如果有两个元素 n=2 a={1,2} 则全排列是
       {2,1}  a[1]与a[2]交换  交换后求a[2-1]={2}的全排列  归结到 1
       {1,2}  a[2]与a[2]交换  交换后求a[2-1]={1}的全排列  归结到 1
  3  如果有三个元素 n=3  a={1,2,3} 则全排列是
     {{2,3},1}  a[1]和a[3]交换  交换后求a[3-1]={2,3} 的全排列 归结到 2
  {{1,3},2}  a[2]  a[3] 交换 交换后求 a[3-1]={1,3} 的全排列 归结到 2
  {1,2},3}   a[3]  a[3] 交换 交换后求 a[3-1]={1,2}  的全排列 归结到 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++)  //元素 进行全部循环
  {  
   //写在swap()之前,进行递归传值  出口点要传入函数
   t=a[i];a[i]=a[size];a[size]=t; 
   swap(a,size-1);
   //数组元素还原  开始是什么 现在还是什么 位置改变后 变成原来位置 
   // 便于从a[1] 到a[n] 和最后一个元素交换位置
   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>

解法二:


代码如下:

<SPAN style="COLOR: #333333">#include <stdio.h>
//思路  分别求出以1 2 3 4 5 开头 剩下数字的全排列  一直到简化为一个数字
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};  //进行递归运算的数值
 swap(a,0);  //函数调用
    return 0;
}
</SPAN>

m个数中取n个进行排列:


代码如下:

#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个数中三个数的全排列
    swap(a,b,0,5);
 return 0;
}

m个数取n个进行组合:

[10反转置换法]

算法思想:

(1)  初始化一个m个元素的数组(全部由0,1组成),将前n个初始化为1,后面的为0。这时候就可以输出第一个组合序列了。
     (2)  从前往后找,找到第一个10组合,将其反转成01,然后将这个10组合前面的所有1,全部往左边推 ,即保证其前面的1都在最左边。这时又可以输出一组组合序列了。
     (3)  重复第(2)步,知道找不到10组合位置。这时已经输出了全部的可能


代码如下:

#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;//当flag=1时,继续while循环 反之,退出循环
    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);  //输出第一个组合
 while(1)
 {
  int count=0;  //注意count位置  就他调试了半天
  //找第一个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))  //统计前面出现出现1的次数
   count++; 
  }
  for(j=0;j<i;j++)
  {
   if(j<count)  //将前面几个数全为1
   {
    *(num+j)=1;
   }
   else       //后几个数为0
   {
    *(num+j)=0;
   }
  }
  putout(num,m);
  if(check(num,m,n)!=1)
   break;
 }
 free(num);
}

int main()
{
 int m,n;//从m个数中找n个求组合
 printf("从m个数中n个数的组合:");
 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;
}

结果实例:

(0)

相关推荐

  • javascript状态栏的字符先杂乱出现再排列组合的代码

    本特效共分两步: 1.在中加入 2.把下面代码加入中 onload="JSCTimeOutID = window.setTimeout('doMessage()',500);" 例如: [Ctrl+A 全选 注:如需引入外部Js需刷新才能执行]

  • 使用php计算排列组合的方法

    前些天因为业务需要写了一段计算排列组合的代码,今天整理了一下,以备后用 复制代码 代码如下: <?php/** * 要解决的数学问题    :算出C(a,1) * C(b, 1) * ... * C(n, 1)的组合情况,其中C(n, 1)代表从n个元素里任意取一个元素 * * 要解决的实际问题样例:某年级有m个班级,每个班的人数不同,现在要从每个班里抽选一个人组成一个小组, *                       由该小组来代表该年级参加学校的某次活动,请给出所有可能的组合 *//*

  • python 排列组合之itertools

    python 2.6 引入了itertools模块,使得排列组合的实现非常简单: 复制代码 代码如下: import itertools 有序排列:e.g., 4个数内选2个排列: 复制代码 代码如下: >>> print list(itertools.permutations([1,2,3,4],2))[(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4,

  • 关于各种排列组合java算法实现方法

    一.利用二进制状态法求排列组合,此种方法比较容易懂,但是运行效率不高,小数据排列组合可以使用 复制代码 代码如下: import java.util.Arrays; //利用二进制算法进行全排列//count1:170187//count2:291656 public class test {    public static void main(String[] args) {        long start=System.currentTimeMillis();        count

  • 排列组合总结:将结果进行输出的实现方法

    全排列输出: 解法一: 复制代码 代码如下: <SPAN style="COLOR: #333333">#include <stdio.h> /*   递归思想:   取出数组第一个元素放到最后一个元素 即a[0] 和a[n]交换  然后一次递归a[n] 个元素的全排列  1   如果数组只有一个元素 n=1 a={1} 则全排列就是{1}  2  如果有两个元素 n=2 a={1,2} 则全排列是       {2,1}  a[1]与a[2]交换  交换后求a

  • 浅谈PHP的排列组合(如输入a,b,c 输出他们的全部组合)

    实例如下: <?php /*分治法--直接选择 比如说a b c 首先将a之后的字符依次与a进行交换 1 b,a,c 2 c,b,a 注意这里少了一个原始数据 a,b,c.需要把原始数据也算如排列中 3 a,b,c 然后把字符移到第二个位置,将第二个位置之后的数分别与第二个位置的数进行交换 1 b,a,c ===> 11 b,c,a 2 c,b,a ===> 21 c,a,b 3 a,b,c ===> 31 a,c,b **/ function zuhe($arr,$begin){

  • Go语言实现的排列组合问题实例(n个数中取m个)

    本文实例讲述了Go语言实现的排列组合问题.分享给大家供大家参考,具体如下: (一)组合问题 组合是一个基本的数学问题,本程序的目标是输出从n个元素中取m个的所有组合. 例如从[1,2,3]中取出2个数,一共有3中组合:[1,2],[1,3],[2,3].(组合不考虑顺序,即[1,2]和[2,1]属同一个组合) 本程序的思路(来自网上其他大神): (1)创建有n个元素数组,数组元素的值为1表示选中,为0则没选中. (2)初始化,将数组前m个元素置1,表示第一个组合为前m个数. (3)从左到右扫描数

  • Golang排列组合算法问题之全排列实现方法

    本文实例讲述了Golang排列组合算法问题之全排列实现方法.分享给大家供大家参考,具体如下: [排列组合问题] 一共N辆火车(0<N<10),每辆火车以数字1-9编号,要求以字典序排序输出火车出站的序列号. 输入: 包括N个正整数(0<N<10),范围为1到9,数字之间用空格分割,字符串首位不包含空格. 输出: 输出以字典序排序的火车出站序列号,每个编号以空格隔开,每个输出序列换行. 样例输入: 1 2 3 样例输出: 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3

  • C语言实现的排列组合问题的通用算法、解决方法

    尽管排列组合是生活中经常遇到的问题,可在程序设计时,不深入思考或者经验不足都让人无从下手.由于排列组合问题总是先取组合再排列,并且单纯的排列问题相对简单,所以本文仅对组合问题的实现进行详细讨论.以在n个数中选取m(0<m<=n)个数为例,问题可分解为: 1. 首先从n个数中选取编号最大的数,然后在剩下的n-1个数里面选取m-1个数,直到从n-(m-1)个数中选取1个数为止. 2. 从n个数中选取编号次小的一个数,继续执行1步,直到当前可选编号最大的数为m. 很明显,上述方法是一个递归的过程,也

  • Python2.7基于笛卡尔积算法实现N个数组的排列组合运算示例

    本文实例讲述了Python2.7基于笛卡尔积算法实现N个数组的排列组合运算.分享给大家供大家参考,具体如下: 说明:本人前段时间遇到的求n个数组的所有排列组合的问题,发现笛卡尔积算法可以解决,但是网上搜索的只有Java版本的实现,于是自己试着用python实现,由于新手代码不太规范. 代码:本人封装了一个类Cartesian(笛卡尔),其中封装了变量和方法: 1.变量 datagroup : 表示n个list(python 中的list与其他编程中的数组定义类似)的集合,即一个二维数组 coun

  • java数组排列组合问题汇总

    面试或笔试中,多次遇到以下4个关于排列组合的手撕算法,这里做个笔记,方法日后查阅: 1. 无重复元素的数组,求全排列: 2. 有重复元素的数组,求全排列: 3. 无重复元素的数组,求组合[子集]: 4. 有重复元素的数组,求组合: 以上四类题,可以用统一的模板实现,如下所示: /* *[组合&&排列] *把一个数组里的数组合全部列出,比如1和2列出来为1,2,12,21. *这个题目可以扩展成四个: *1.无重复数字的数组,求组合 *2.有重复数字的数组,求组合 *3.无重复数字的数组,求

  • Java实现abc字符串排列组合

    1.可重复排列:abc三个字符组成的所有长度为3的字符串,aaa,aab,aac......ccc 一共27种 利用递归的思想,第一个字符可以从abc中选择一个,三种选择,之后问题转化为abc组成长度为2的字符的情况,循环递归后可以求出所有的可能.控制好循环退出条件即可. 利用递归可以处理,不知道字符长度的情况下,即通用处理.如果知道长度,只需要利用多层循环,也可以得出结论. public class Permutation { public static void main(String[]

  • Python列表list排列组合操作示例

    本文实例讲述了Python列表list排列组合操作.分享给大家供大家参考,具体如下: 排列 例如: 输入为 ['1','2','3']和3 输出为 ['111','112','113','121','122','123','131','132','133','211','212','213','221','222','223','231','232','233','311','312','313','321','322','323','331','332','333'] 实现代码: # -*-

  • Python使用combinations实现排列组合的方法

    好久没有写博客了!昨天小牛在上海举办了牛友见面会,现场优惠还是比较大,心仪已久加上一时脑热就入手了.以为会有多么开心,其实目前最大的感受就是焦虑!担心电动车被偷,担心电池被偷,担心路上突然被交警叔叔拦下!我想,直到我的小牛真的被偷的那天,这种焦虑才会随之消失.唉,要说这样的焦虑怎么来的,我只能呵呵了:) 下面步入正题: 今天在帮我们家王博处理专利数据的时候,需要对专利数据中的城市和专利主体的合作关系数量进行统计.一项专利其写作主体可能由两个或两个以上主体参与,各个主体又分属不同或者相同的城市,对

随机推荐