【蓝桥杯】Java实现之全排列

举报
随性. 发表于 2022/04/25 16:03:22 2022/04/25
【摘要】 蓝桥杯---Java大学C组---个人赛日常刷题【day21】

全排列:

大家在学习Java的时候肯定遇到过很多用全排列解决的问题,但一开始根本不知道什么是全排列,做题做多了以后才能慢慢知道什么是全排列。

废话不多说,直接举例说明:
(1) 第一个记录
(2) 剩下的所有元素
所有记录的全排列就是所有可能出现在第一个位置的记录与剩下所有元素的全排列

以【1,2,3】位例子:全排列有

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]
共位6种,这是一个简单的排列组合的问题。
1,2,3的全排列可以看作是
   1,[2,3的全排列]
      [2,3]的全排列又可以看作是
         2,[3的全排列]—————对应123
         3,[2的全排列]—————对应132
   2,[1,3的全排列]
      [1,3]的全排列又可以看作是
         1,[3的全排列]—————对应213
         3,[1的全排列]—————对应231
   3,[1,2的全排列]
      [1,2]的全排列又可以看作是
         1,[2的全排列]—————对应312
         2,[1的全排列]—————对应321
这样来看,很明显这就是一个递归的思路。

完整代码:

package 全排列;

import java.lang.reflect.Array;
import java.util.Arrays;

public class example {

	public static void main(String[] args) {
		perm(new int[] {1,2,3},0,2);

	}
	public static void perm(int[] array,int start,int end) {
		if (start==end) {
			System.out.println(Arrays.toString(array));
		}else {
			for (int i = start; i <=end; i++) {
				//1,2,3的全排列这块相当于将其中一个提了出来。下次递归从start+1开始
				swap(array,start,i);
				perm(array,start+1,end);
				//这块是复原数组,为了保证下次另外的同级递归使用数组不会出错
				//这块可以通过树来理解,每次回退一步操作,交换回去
				swap(array,start,i);
			}
		}
	}

	public static void swap(int[] array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
}
perm接收三个参数,数组array,起始位置start,终止位置end,意思就是完成array数组从start到end之间记录的全排列。
分两个步骤:
(1)确定第一位的字符
数组array从start到end的所有记录都可以出现在第一个位置,所以直接一个for循环,考虑了这所有的情况。在for循环中,swap方法就是交换i和start位置的数,保证当前i指向的记录出现在第一个位置,也就是start指向的位置
(2)剩下的记录继续做全排列
这个就是一个递归函数的调用,只需要修改起始位置,也就是start+1,因为start的位置已经放了记录,所以只需要继续做从start+1到end的全排列即可
递归的终止条件就是当start==end,也就是只有一个记录需要做全排列,也就是到了最后一个记录,这就是全排列的一种情况,输入本次的记录,也就是数组arr即可。

全排列解释完毕了,来实际应用一下。


题目:图书排列

题目描述:将编号为1~10的10本书排放在书架上,要求编号相邻的书不能放在相邻的位置。
请计算一共有多少种不同的排列方案。

注意,需要提交的是一个整数,不要填写任何多余的内容。

解题思路:这个题目有很多解法,这里只说明用全排列怎么解决,先求出全排列,也就是所有的排列方案,然后去掉不满足条件的情况,也就是编号相邻的书不能相邻这一条件。

完整代码如下:

public class BookSort {

    public static void main(String[] args) {
        int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        fullSort(arr, 0, arr.length - 1);
        System.out.println(res);
    }

    static int res = 0;

    static void fullSort(int[] arr, int start, int end) {
        // 递归终止条件
        if (start == end) {
            // 求出了全排列的一种情况,然后检查是否满足条件
            if (check(arr))
                res++;
            return;
        }
        for (int i = start; i <= end; i++) {
            swap(arr, start, i);
            fullSort(arr, start + 1, end);
            swap(arr, start, i);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    static boolean check(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (Math.abs(arr[i] - arr[i - 1]) == 1)
                return false;
        }
        return true;
    }

}
全排列的代码和上面的代码一样,不同的地方就是在找到全排列的一种情况时,要检查是否满足条件,也就是check方法。

运行结果:479306

💯写在最后

                   让我一起蓝桥我来啦!

蓝桥.jpg

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。