C语言实现全排列算法模板的方法

程序的主要思路是:

1.把第1个数换到最前面来(本来就在最前面),准备打印1xx,再对后两个数2和3做全排列。

2.把第2个数换到最前面来,准备打印2xx,再对后两个数1和3做全排列。

3.把第3个数换到最前面来,准备打印3xx,再对后两个数1和2做全排列。

可见这是一个递归的过程,把对整个序列做全排列的问题归结为对它的子序列做全排列的问题,注意我没有描述Base Case怎么处理,你需要自己想。你的程序要具有通用性,如果改变了N和数组a的定义(比如改成4个数的数组),其它代码不需要修改就可以做4个数的全排列(共24种排列)。

解题过程:

1.当N = 1的时候,则直接打印数列即可。

2.当N = 2的时候,设数组为[a, b]

打印a[0], a[1] (即a,b)

交换a[0],a[1]里面的内容

打印a[0],a[1]  (此时已变成了[b, a] )

3.当N = 3的时候,数组为[a, b, c]

3.1把a放在a[0] 的位置(原本也是如此,a[0] = a[0]),打印b,c的全排列(即a[1], a[2]的全排列)

3.2把b放在a[0]的位置(这时候需要交换原数组的a[0]和a[1]),然后打印a, c的全排列,打印完后再换回原来的位置,即a还是恢复到a[0],b还恢复到a[1]的位置

3.3把c放在a[0]的位置(这时候需要交换的是原数组的a[0]和a[2]),然后打印a, b的全排列,打印完后再换回原来的位置,即a还是恢复到a[0],b还恢复到a[1]的位置

至此,全排列完成

当 N = 4,5,6,……的时候,以此类推。

#include <stdio.h>

/************************************************************************/
/* 功能:实现两个整形参数值交换
/* 参数:
/*    lhs--int类型的指针,指向待交换数1的地址
/*    rhs--int类型的指针,指向待交换数2的地址
/************************************************************************/
void Swap(int *lhs, int *rhs)
{
 int t = *lhs;

 *lhs = *rhs;
 *rhs = t;
}

/************************************************************************/
/* 功能:实现全排列功能
/* 参数:
/*    source--整数数组,存放需要全排列的元素
/*    begin --查找一个排列的开始位置
/*    end  --查找一个排列的结束位置,当begin=end时,表明完成一个排列
/************************************************************************/
void FullPermutation(int source[], int begin, int end)
{
 int i;

 if (begin >= end) // 找到一个排列
 {
 for (i = 0; i < end; i++)
 {
  printf("%d", source[i]);
 }
 printf("\n");
 }
 else// 没有找完一个排列,则继续往下找下一个元素
 {
 for (i = begin; i < end; i++)
 {
  if (begin != i)
  {
  Swap(&source[begin], &source[i]); // 交换
  }

  // 递归排列剩余的从begin+1到end的元素
  FullPermutation(source, begin + 1, end);

  if (begin != i)
  {
  Swap(&source[begin], &source[i]); // 回溯时还原
  }
 }
 }
}

int main()
{
 int source[30];
 int i, count;

 scanf("%d", &count);

 // 初始化数组
 for (i = 0; i < count; i++)
 {
 source[i] = i + 1;
 }

 FullPermutation(source, 0, count);

 return 0;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • 使用C语言解决字符串全排列问题

    问题 输入一个字符串,打印出该字符串中字符的所有排列.例如输入字符串abc,则输出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba 思路 这是典型的递归求解问题,递归算法有四个特性: 必须有可达到的终止条件,否则程序陷入死循环 子问题在规模上比原问题小 子问题可通过再次递归调用求解 子问题的解应能组合成整个问题的解 对于字符串的排列问题: 如果能生成n-1个元素的全排列,就能生成n个元素的全排列.对于只有一个元素的集合,可以直接生成全排列.所以全排列的递归终

  • C语言实现全排列算法模板的方法

    程序的主要思路是: 1.把第1个数换到最前面来(本来就在最前面),准备打印1xx,再对后两个数2和3做全排列. 2.把第2个数换到最前面来,准备打印2xx,再对后两个数1和3做全排列. 3.把第3个数换到最前面来,准备打印3xx,再对后两个数1和2做全排列. 可见这是一个递归的过程,把对整个序列做全排列的问题归结为对它的子序列做全排列的问题,注意我没有描述Base Case怎么处理,你需要自己想.你的程序要具有通用性,如果改变了N和数组a的定义(比如改成4个数的数组),其它代码不需要修改就可以做

  • js实现字符全排列算法的简单方法

    实例如下: <!doctype html> <html lang="en"> <head> <meta charset="UTF-8"> <title>字符全排列</title> </head> <body> <script> function charsMap(o){ o = (o+"").replace(/(\w)(?=\w*\1)/g

  • 深入全排列算法及其实现方法

    全排列在很多程序都有应用,是一个很常见的算法,常规的算法是一种递归的算法,这种算法的得到基于以下的分析思路.  给定一个具有n个元素的集合(n>=1),要求输出这个集合中元素的所有可能的排列.一.递归实现例如,如果集合是{a,b,c},那么这个集合中元素的所有排列是{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)},显然,给定n个元素共有n!种不同的排列,如果给定集合是{a,b,c,d},可以用下面给出的简单算法产生其所有排列,即集合(a,b,c,

  • Go语言通过Luhn算法验证信用卡卡号是否有效的方法

    本文实例讲述了Go语言通过Luhn算法验证信用卡卡号是否有效的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: package main import (     "fmt"     "strings" ) const input = `49927398716 49927398717 1234567812345678 1234567812345670` var t = [...]int{0, 2, 4, 6, 8, 1, 3, 5, 7, 9}

  • 使用C++实现全排列算法的方法详解

    复制代码 代码如下: <P>不论是哪种全排列生成算法,都遵循着"原排列"→"原中介数"→"新中介数"→"新排列"的过程.</P><P>其中中介数依据算法的不同会的到递增进位制数和递减进位制数.</P><P>关于排列和中介数的一一对应性的证明我们不做讨论,这里仅仅给出了排列和中介数的详细映射方法.</P> · 递增进位制和递减进位制数  所谓递增进位制和递减

  • C语言基本排序算法之插入排序与直接选择排序实现方法

    本文实例讲述了C语言基本排序算法之插入排序与直接选择排序实现方法.分享给大家供大家参考,具体如下: 声明待排序元素类型 /*-------------------------- typedef.h 方便修改待排序元素类型 -------------------------------------*/ #ifndef TYPEDEF_H #define TYPEDEF_H typedef int T; #endif 插入排序: /*---------------------------------

  • 全排列算法的非递归实现与递归实现的方法(C++)

    (一)非递归全排列算法基本思想是:    1.找到所有排列中最小的一个排列P.    2.找到刚刚好比P大比其它都小的排列Q,    3.循环执行第二步,直到找到一个最大的排列,算法结束.下面用数学的方法描述:给定已知序列 P =  A1A2A3An ( Ai!=Aj , (1<=i<=n  , 1<=j<=n, i != j  ) )找到P的一个最小排列Pmin = P1P2P3Pn  有  Pi > P(i-1) (1 < i <= n)从Pmin开始,总是目

  • 全排列算法-递归与字典序的实现方法(Java)

    全排列算法-递归与字典序的实现方法(Java) 全排列: 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列.当m=n时所有的排列情况叫全排列. 例如: 1 .2 .3三个元素的全排列为: {1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}. ------------------------------------------------------ 解法1(递归) 如下图:要对1.2.3.4进行

  • C语言基于回溯算法解决八皇后问题的方法

    本文实例讲述了C语言基于回溯算法解决八皇后问题的方法.分享给大家供大家参考,具体如下: 问题描述: 八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例:在8X8格的国际象棋棋盘上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 问题求解: 采用回溯算法,即从第一行开始,依次探查可以放置皇后的位置,若找到,则放置皇后,开始探查下一行:若该行没有位置可以放置皇后,则回溯至上一行,清除该行放置皇后的信息,从该行原本放置皇后的下一个位置开始探查可

  • C语言基于贪心算法解决装箱问题的方法

    本文实例讲述了C语言基于贪心算法解决装箱问题的方法.分享给大家供大家参考,具体如下: 问题描述: 有一些箱子,容量为V,同时有n个物品,每个物品有一个体积(小于等于箱子容量),要求将物品全部装入箱子中,使占用的箱子数尽量少. 贪心算法中要求每一步的解都是当前步骤中的最优解.原问题的解可以通过一系列局部最优的选择来达到,这种选择并不依赖于子问题的解. 算法思想: 1.数据结构 要求求解箱子数目,也就是说不能确定会占用多少个箱子,因此采用链表的形式来存储箱子及其信息. 同时,每个箱子中物品的数目也无

随机推荐