首页 / 算法 / 全排列算法及解决数字搭积木问题
全排列算法及解决数字搭积木问题
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了全排列算法及解决数字搭积木问题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2878字，纯文字阅读大概需要5分钟。
内容图文
如果你是做这道题不会，那么你可以看这道题的解题思路，如果你是不太理解全排列算法，那么你可以通过这个题来理解。
题目描述：
小明最近喜欢搭数字积木。一共有10块积木，每个积木上有一个数字，0~9。
搭积木规则：
每个积木放到其它两个积木的上面，并且一定比下面的两个积木数字小。
最后搭成4层的金字塔形，必须用完所有的积木。
下面是两种合格的搭法：
请你计算这样的搭法一共有多少种？
分析
一共有10个数字，要我们把所有可行的排列方式都求出来，一时没什么思路，索性就全排列了，把所有排列的情况都求出来，然后在把每种情况都判断一下，是不是就可以得到答案了。
所以全排列怎么写成了第一大问题了。
全排列
对于这个问题来说，我们把金字塔当成一个int数组，那么就为 全排列这个数组{0,1,2,3,4,5,6,7,8,9}。
太长了，想不明白呀，所以来看比较少的呗。
对于{0,1}全排列，就是把0抽出来，1做全排列，对于{0,1,2},就是：
- 把0抽出来，把1,2做全排列，
- 把1抽出来，把0，2做全排列，
- 把2抽出来，把0，1做全排列。
- 接下来那不就和上面那个{0,1}一样了吗?
这是不是个递归呢?很明显吧。的确是。
那好我们定义一个方法，这个方法的作用是，把list数组全排列，而参数curr表示当前抽出来的那个数，就像上面例子提到的0一样。
提出来了之后呢，是不是要把curr交换了，这样就可以把所有在这个位置上的所有情况列出来了，所以使用一个for循环，来交换curr和后面剩余数组的数(就是上面例子的1，2，3步骤)。
紧接着定义一个方法，交换两数swap(list,curr,j);，当然你也可以把这个方法直接写到这个函数里面，但是毕竟不美观，不实用。
重点来了：回溯！！！
从这张图中，所谓回溯就是要回到上一没有操作过的状态，再去考虑别的情况。就下面这个A,B,C他需要回到上一次抽数出来之前的状态。这样他才能去抽另外一个数，全排列下一种情况。所以我们需要在写一遍swap(list,curr,j);
问题分析到这了，我们的代码基本上就可以出来了，所以看下代码，如果看不懂在回到我的分析，相信你一定能看懂。
public class Test2 {
static int sum ;
public static void main(String[] args) {
int list[] = {0,1,2,3,4,5,6,7,8,9};
allSort(list,0);
System.out.println(sum);
}
//代表将第a[m]和a[n]相交换
public static void swap(int a[],int m ,int n){
int temp = a[m];
a[m] = a[n];
a[n] = temp;
}
//调用全排列数组list,curr代表当前放在第一个的为第几个数字，比如开始就为数组第0个数字
public static void allSort(int list[],int curr ){
//如果当前数组的索引等于数组的长了，就将方法加1
if (curr == list.length-1){
check(list);
}else {
//数组每一个都要和当前数组的第curr个相交换，所以要用个循环
for (int j = curr; j < list.length; j++){
swap(list,curr,j);
allSort(list,curr+1);
swap(list,curr,j);
}
}
}
public static void check(int list[]){
if (list[1] < list[0]) return;
if (list[2] < list[0]) return;
if (list[3] < list[1]) return;
if (list[4] < list[1]) return;
if (list[4] < list[2]) return;
if (list[5] < list[2]) return;
if (list[6] < list[3]) return;
if (list[7] < list[3]) return;
if (list[7] < list[4]) return;
if (list[8] < list[4]) return;
if (list[8] < list[5]) return;
if (list[9] < list[5]) return;
sum++;
}
}
其实这个全排列都可以当成一个模板了，但是还是推荐大家一定要手敲，自己写代码，写出来了，才是自己的东西。
图片参考：https://blog.csdn.net/Strom72/article/details/80738818
内容总结
以上是互联网集市为您收集整理的全排列算法及解决数字搭积木问题全部内容，希望文章能够帮你解决全排列算法及解决数字搭积木问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。