全排列 -深度优先算法中的剪枝问题

86 阅读 0 评论 57 点赞

我是靠谱客的博主哭泣乌龟，最近开发中收集的这篇文章主要介绍全排列 -深度优先算法中的剪枝问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在深度优先算法中，如果遇到需要剪枝的问题，如果你不剪，必然会爆内存，爆栈。

看以下的题目：

给出一个字符串S（可能有重复的字符），按照字典序从小到大，输出S包括的字符组成的所有排列。例如：S = "1312"，

输出为：

1123

1132

1213

1231

1312

1321

2113

2131

2311

3112

3121

3211

Input输入一个字符串S（S的长度 <= 9，且只包括0 - 9的阿拉伯数字）Output输出S所包含的字符组成的所有排列Sample Input

Sample Output

1123
1132
1213
1231
1312
1321
2113
2131
2311
3112
3121
3211
题目看起来很简单，似乎是个水题，但是，你不剪枝就出错。
错误解法：用一个数组来保存结果.
实现代码：
package KingLong;

import java.util.Arrays;
import java.util.Scanner;

public class Main
{
    static final int MAX = 10;
    static int num[] = new int[MAX];
    static boolean vis[] = new boolean[MAX]; 
    static int len;
    public static void main(String []args)
    {
        Scanner cin = new Scanner(System.in);
        String str = cin.next();
        len = str.length();
        for(int i = 0 ; i < len ; i++)
        {
            num[i] = str.charAt(i)-'0';
        }
        Arrays.sort(num,0,len);
        dfs(0,"");
    }
    static void dfs(int cnt,String str)
    {
        if(cnt == len)
        {
            System.out.println(str);
            return;
        }
        for(int i = 0 ; i < len ; i++)
        {
            if(vis[i] == false)
            {
                vis[i] = true;
                dfs(cnt+1,str+num[i]);
                vis[i] = false;
                while(i < len && num[i] == num[i+1])
                {
                    i++;
                }
            }
        }
    }
}
结果爆栈了，气人啊。
剪枝的方法：
package KingLong;

import java.util.Arrays;
import java.util.Scanner;

public class Main
{
	static final int MAX = 10;
	static int num[] = new int[MAX];
	static boolean vis[] = new boolean[MAX]; 
	static int len;
	public static void main(String []args)
	{
		Scanner cin = new Scanner(System.in);
		String str = cin.next();
		len = str.length();
		for(int i = 0 ; i < len ; i++)
		{
			num[i] = str.charAt(i)-'0';
		}
		Arrays.sort(num,0,len);
		dfs(0,"");
	}
	static void dfs(int cnt,String str)
	{
		if(cnt == len)
		{
			System.out.println(str);
			return;
		}
		for(int i = 0 ; i < len ; i++)
		{
			if(vis[i] == false)
			{
				vis[i] = true;
				dfs(cnt+1,str+num[i]);
				vis[i] = false;
				while(i < len && num[i] == num[i+1])//这个是最重要的一步
				{
					i++;
				}
			}
		}
	}
}

import java.util.Arrays; import java.util.Scanner; publicclass Main { staticfinalint MAX = 10; staticint num[] = newint[MAX]; staticboolean vis[] = newboolean[MAX]; staticint len; public static void main(String []args) { Scanner cin = new Scanner(System.in); String str = cin.next(); len = str.length(); for(int i = 0 ; i < len ; i++) { num[i] = str.charAt(i)-'0'; } Arrays.sort(num,0,len); dfs(0,""); } static void dfs(int cnt,String str) { if(cnt == len) { System.out.println(str); return; } for(int i = 0 ; i < len ; i++) { if(vis[i] == false) { vis[i] = true; dfs(cnt+1,str+num[i]); vis[i] = false; while(i < len && num[i] == num[i+1]) { i++; } } } } }