`
Coco_young
  • 浏览: 125770 次
  • 性别: Icon_minigender_1
  • 来自: 湖南长沙
社区版块
存档分类
最新评论

枚举法求全排列

阅读更多

问题描述:

输入整数N,按照字典序从小到大打印出1-N的去所有排列。两个序列的字典序大小关系等价于从头开始第一个不相同处的大小关系,(例如(1,2,3)<(3,2,1)),N=3时,输出结果是:(1,2,3)(1,3,2)(2,1,3)(2,3,1)(3,1,2)(3,2,1).

 

算法思想:

设集合S是保持带排列元素的集合,数组A保持排列的元素。

如果集合S为空,则表示完成了一个排列,不再继续递归,否则将S中的元素V加入到A中,且S = S-{V},继续递归寻找下一个可以加入到排列中的元素。伪代码如下:

 

 

Status print_permutation(序列A,集合S)
{
        if(S==空集)
        {
              打印A
        }
        else 从小到大依次尝试将S中的元素加入序列A
        {
              print_permutation(加入元素后的新序列A,S-{V});
        }
}

按照如上伪代码,不难写出如下程序:

#include<iostream>
using namespace std;
//枚举全排列的函数
//n表示元素总个数,A表示当前序列,cur表示当前元素个数 
void Print_Arrangement(int n,int *A,int cur)
{
     int i,j;
     if(n==cur)//如果一个排列完成了 
     {
        for(int i=0;i<n;i++)
        cout<<A[i];
        cout<<endl;
     }
     else for(int i=1;i<=n;i++)
     {
        int ok = 1;
        for(int j=0;j<cur;j++)
        {
           if(A[j]==i)
           ok = 0;
        }//元素是否已经在排列中出现过 
        if(ok)
        {
            A[cur] = i;
            Print_Arrangement(n,A,cur+1);
        }
     }
}
int main()
{
    //测试N=3的情况 
    int A[100];
    int n = 3;
    Print_Arrangement(n,A,0);
    system("pause");
    return 0;
}

下面考虑用处理字符排列的情况,如果是用char数组的话,只需将int数组改成char数组,并且用一个char数组保存待排列的 元素,实现代码如下:

package ScannerTest;
/**
 * 枚举全排列的类
 * @author dell
 *
 */
public class Permutation {

	/**
	 * 主函数
	 * @param args
	 */
	public static void main(String[] args){
		
		char[] container = {'1','2','3'};
		Permutation p = new Permutation(container);
		char[] now = new char[1000];
		p.Print_Permutation(3, now, 0);
	}
	
	/**
	 * 打印排列
	 * @param n
	 * @param now
	 * @param total
	 */
	public void Print_Permutation(int n,char[] now,int total){
		
		if(n==total){
			for(int i=0;i<n;i++){
				System.out.print(now[i]);
			}
			System.out.print("\n");
		}else for(int i=0;i<n;i++){
			
			char add = set[i];
			boolean ok = true;
			
			for(int j=0;j<total;j++){
				if(now[j]==add){
					ok = false;
				}
			}
			
			if(ok){
				now[total] = add;
				Print_Permutation(n,now,total+1);
			}
			
		}
		
	}
	
	public Permutation(char[] s){
		set = s;
	}
	
	
	//待排列集合
	private char[] set;
	
}

但是,如果用字符串String来处理的话,情况稍许不同,代码如下:

 

package ScannerTest;
/**
 * 枚举全排列的类
 * @author dell
 *
 */
public class Arrangement {
	/**
	 * 主函数
	 * @param args
	 */
	public static void main(String[] args){
		Arrangement ar = new Arrangement("123");
		String now = "";
		ar.Print_Arrangement(3, now, 0);
	}
	
	/**
	 * 构造函数
	 * @param str
	 */
	public Arrangement(String str){
		set = str;
	}
	
	/**
	 * 枚举全排列的函数
	 * @param n 总元素个数
	 * @param now 现在的排列
	 * @param total 当前元素个数
	 */
	public void Print_Arrangement(int n,String now,int total){
		
		//如果当前元素个数满足输出条件
		if(total==n){
			System.out.println(now);
		}else{
			//枚举下一步可能出现的每一种情况
			for(int i=0;i<set.length();i++){
				//加入排列的元素
				char add = set.charAt(i);
				boolean ok = true;
				for(int j=0;j<now.length();j++){
					if(now.charAt(j)==add){
						ok = false;
					}
				}
				//如果排列中不包含了该元素
				if(ok){
					now = now+add;
					Print_Arrangement(n,now,total+1);
					//这步非常关键,必须还原字符串
					now = now.substring(0,now.length()-1);
				}
			}
		}
		
	}
	
	

	private String set;//元素集合
}

如上代码,在递归寻找完元素后必须还原字符串!

0
1
分享到:
评论

相关推荐

    代码 基于0-1整数规划隐枚举法离散型优化问题代码

    代码 基于0-1整数规划隐枚举法离散型优化问题代码代码 基于0-1整数规划隐枚举法离散型优化问题代码代码 基于0-1整数规划隐枚举法离散型优化问题代码代码 基于0-1整数规划隐枚举法离散型优化问题代码代码 基于0-1整数...

    枚举法c语言

    枚举法 C 语言实现 枚举法是编程中常用的算法之一,它的思想是从所有候选答案中逐一取出候选答案,并验证该候选答案是否为正确的解。枚举法的本质就是从所有候选答案中去搜索正确的解,使用该算法需要满足两个条件...

    算法设计之枚举法

    在进行归纳推理时,如果逐个考察了某类事件的所有可能情况,因而得出一般结论,那么这结论是可靠的,这种归纳方法叫做枚举法,本算法由C++实现

    代码 基于枚举法离散型优化问题代码

    代码 基于枚举法离散型优化问题代码代码 基于枚举法离散型优化问题代码代码 基于枚举法离散型优化问题代码代码 基于枚举法离散型优化问题代码代码 基于枚举法离散型优化问题代码代码 基于枚举法离散型优化问题代码...

    Discreteoptimization.rar_matlab 隐枚举法_matlab枚举_枚举_隐枚举法_非线性规划

    它包含了枚举法、蒙特卡洛法、线性整数规划、整数规划枚举法、整数规划隐枚举法、非线性整数规划、非线性整数规划图形工具、最小生成树kruskal算法、最短路dijkstra算法、最小生成树kruskal算法mex程序、最短路...

    小学二年级下册数学奥数知识讲解第十课(枚举法).pdf

    例如,当寻找一个数列中的特定项或解决排列组合问题时,枚举法可以帮助孩子们系统地检查所有可能性。 在二年级下册的奥数教学中,枚举法通常用于解决一些简单的计数问题,如计算有多少种不同的方式可以排列或组合...

    代码 基于0-1整数规划枚举法离散型优化问题代码

    代码 基于0-1整数规划枚举法离散型优化问题代码代码 基于0-1整数规划枚举法离散型优化问题代码代码 基于0-1整数规划枚举法离散型优化问题代码代码 基于0-1整数规划枚举法离散型优化问题代码代码 基于0-1整数规划枚举...

    JM97Bcount.rar_枚举_枚举法

    例如,在这个数学建模竞赛中,可能需要通过枚举所有可能的组合、排列或者数列来找到满足特定条件的数学模型。枚举法虽然简单,但处理不当可能导致大量的计算,因此在设计算法时,必须考虑到时间复杂性和空间复杂性,...

    MATLAB源码集锦-基于枚举法离散型优化问题代码

    本资源包聚焦于使用枚举法解决离散型优化问题的MATLAB源码,通过深入学习这些代码,可以增进对离散优化算法的理解并提升实际应用能力。 枚举法是一种直观且基础的解决问题的方法,它通过穷举所有可能的解来找到最优...

    c语言枚举法(穷举法)ppt课件.ppt

    C语言枚举法(穷举法)知识点总结 本节课件主要讲解了C语言中的枚举法(穷举法),通过实例分析和编程思路,探讨了枚举法的应用和优化。 一、枚举法(穷举法)定义 枚举法(穷举法)是一种解决问题的方法,即通过...

    MATLAB源码集锦-基于0-1整数规划隐枚举法离散型优化问题代码

    隐枚举法,又称为隐式枚举或分支定界法,是一种解决0-1整数规划的有效策略。这种方法通过构建一棵决策树来逐步探索所有可能的解空间。在每一步,算法会根据当前节点的最优解和剩余未决定的变量进行分支,将一个变量...

    分支定界法、割平面法、隐式枚举法的整数规划matlab源代码.zip

    本资源包含的"分支定界法、割平面法、隐式枚举法的整数规划matlab源代码.zip"是一套用MATLAB实现的算法,用于解决这类问题。MATLAB作为一种强大的数值计算和可视化工具,常被用来处理各种优化问题,包括整数规划。 ...

    C语言枚举法PPT课件.pptx

    C语言枚举法PPT课件 枚举法是指从可能的集合中一一枚举各个元素,用题目给定的约束条件判定哪些是无用的,哪些是有用的。能够使命题成立者,即为问题的解。枚举法是一种基本的算法思想,在解决计算机科学问题时经常...

    基于matlab分支定界法、割平面法、隐式枚举法的整数规划码

    本主题将深入探讨如何使用MATLAB来实现三种主要的求解整数规划问题的方法:分支定界法、割平面法和隐式枚举法。 **分支定界法** 是一种全局优化技术,用于寻找整数或混合整数线性规划问题的全局最优解。该方法通过...

    算法 枚举法

    计算机算法 枚举法

    分支定界法、割平面法、隐式枚举法的整数规划码.zip

    分支定界法、割平面法和隐式枚举法是解决整数规划问题的三种经典算法,下面将详细阐述这三种方法。 **分支定界法(Branch and Bound)** 分支定界法是一种全局搜索策略,通过将问题的可行域逐步分割成更小的子集...

    简化的背包问题枚举法求解

    标题中的“简化的背包问题枚举法求解”是指在数据结构领域中,解决背包问题的一种基础算法。背包问题是一个经典的优化问题,通常出现在计算机科学的算法设计与分析课程中,也被广泛应用于实际的资源分配问题。在此...

    MATLAB源码集锦-基于0-1整数规划枚举法离散型优化问题代码

    本源码集锦中的代码正是采用枚举法来解决离散型优化问题,这种方法适用于小规模问题,对于每个可能的0-1变量组合,它会逐一检查并计算目标函数的值,寻找最优解。 0-1整数规划的基本形式可以表示为: 1. 目标函数:...

    枚举法求两个数的最大公约数

    枚举法求两个数的最大公约数算法

Global site tag (gtag.js) - Google Analytics