专栏首页cwl_JavaC++经典算法题-排列组合

C++经典算法题-排列组合

27.Algorithm Gossip: 排列组合

说明

将一组数字、字母或符号进行排列,以得到不同的组合顺序,例如1 2 3这三个数的排列组合有:

1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1。

解法

可以使用递回将问题切割为较小的单元进行排列组合,例如1 2 3 4的排列可以分为

1 [2 3 4]、2 [1 3 4]、3 [1 2 4]、4 [1 2 3]

进行排列,这边利用旋转法,先将旋转间隔设为0,将最右边的数字旋转至最左边,并逐步增加旋转的间隔,例如:

1 2 3 4 -> 旋转1 -> 继续将右边2 3 4进行递回处理
2 1 3 4 -> 旋转1 2 变为 2 1-> 继续将右边1 3 4进行递回处理
3 1 2 4 -> 旋转1 2 3变为 3 1 2 -> 继续将右边1 2 4进行递回处理
4 1 2 3 -> 旋转1 2 3 4变为4 1 2 3 -> 继续将右边1 2 3进行递回处理

代码示例

#include <stdio.h>
#include <stdlib.h> 
#define N 4
    void perm(int*, int); int main(void) {
        int num[N+1], i;
        for(i = 1; i <= N; i++) num[i] = i;
        perm(num, 1);
        return 0;
    }

    void perm(int* num, int i) { int j, k, tmp;

        if(i < N) {
            for(j = i; j <= N; j++) { tmp = num[j];
                // 旋转该区段最右边数字至最左边
                for(k = j; k > i; k--)
                    num[k] = num[k-1]; num[i] = tmp; perm(num, i+1);
                // 还原
                for(k = i; k < j; k++) num[k] = num[k+1];
                num[j] = tmp;
            }
        }
        else {	// 显示此次排列
            for(j = 1; j <= N; j++) printf("%d ", num[j]);
            printf("\n");
        }
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PHP-作用域

    默认情况下,函数内部不能访问函数外部的变量,但在匿名函数中,可以通过use将外部变量引入匿名函数中

    cwl_java
  • Java工具集-Bean对象(BeanUtils)

    cwl_java
  • VUE-快速入门

    可以下载2.5.16版本https://github.com/vuejs/vue/archive/v2.5.16.zip

    cwl_java
  • 用Java实现JVM第七章《方法调用和返回》

    案例介绍 本章节主要用java实现;方法调用指令、返回指令、解析方法符号引用、参数传递等。实现新的指令后我们的虚拟机就可以执行稍微复杂的运算并输出结果。

    小傅哥
  • 蓝桥杯之全排列函数next_permutation()运用

    在蓝桥杯的题目中大多数都可以运用到全排列函数 充分运用可以节省很多的时间。话不多说来刷题

    用户4492257
  • 利用爬虫和树莓派3打造自己的语音天气闹钟

    前言 前不久又一次一个人在他乡过了生日,悄悄买了一台树莓派3送给自己做生日礼物。终于算是实现了大学以来一直的一个小愿望。买回来之后当然不能让他落灰,于是就利用自...

    木制robot
  • 【每周一坑】校验文件哈希

    先说个通知,给参与了码上行动的同学:又一期展示学习成果的编程擂台活动开始了,即是练手的好机会,又能得到助教的全程支持,还可以得积分赢奖金。赶紧来报名吧!从课程首...

    Crossin先生
  • 用Java实现JVM第七章《方法调用和返回》

    本章节主要用java实现;方法调用指令、返回指令、解析方法符号引用、参数传递等。实现新的指令后我们的虚拟机就可以执行稍微复杂的运算并输出结果。

    小傅哥
  • leetcode-342-Power of Four

    chenjx85
  • python中逻辑运算符“+”的特殊之处

    num = num + num 与 num += num 的区别(其他语言中这两种方式可以划等号,但是python中不可以):

    py3study

扫码关注云+社区

领取腾讯云代金券