`
wkwukong
  • 浏览: 9448 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

整数1到N的全排列----非递归方法

阅读更多

      庞果网上的一道题目:打印N个字符的全排列,百度了一下。百度百科介绍如下(http://baike.baidu.com/view/1710135.htm),根据百度百科的提示,自己实现了一下,以下为源代码:

public class Combine {
    public static void combine(Integer[] array) {
        Integer[] res = array;
        output(array);
        int flag;
        while (isDes(res)) {
            for (int i = res.length - 1; i > 0; i--) {
                if (res[i - 1] < res[i]) {
                    flag = i - 1;
                    for (int j = res.length - 1; j > flag; j--) {
                        if (res[j] > res[flag]) {
                            swap(res, j, flag);
                            break;
                        }
                    }
                    res = sort(res, i, res.length);
                    output(res);
                    break;
                }
            }
        }
    }

    public static Integer[] sort(Integer[] array, int start, int end) {
        for (int i = start; i < end; i++) {
            for (int j = i; j < end; j++) {
                if (array[i] > array[j]) {
                    int t = array[i];
                    array[i] = array[j];
                    array[j] = t;
                }
            }
        }
        return array;
    }

    public static boolean isDes(Integer[] array) {
        boolean flag = false;
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] < array[i + 1]) {
                flag = true;
                break;
            }
        }
        return flag;
    }

    public static Integer[] swap(Integer[] array, int a, int b) {
        int t;
        t = array[a];
        array[a] = array[b];
        array[b] = t;
        return array;
    }

    public static void output(Integer[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "\t");
        }
        System.out.print("\r\n");
    }

    public static void main(String[] args) {
        Integer[] arr = {1, 2, 3, 4, 5, 6, 7};
        combine(arr);
    }
}

分享到:
评论

相关推荐

    java递归实现N个数全排列输出

    首先定义一个方法,接受一个整型数组和一个整数N作为参数,表示当前处理到数组的第几个元素。初始调用时,数组中的所有元素都未被处理,因此N等于数组长度。 ```java public void permute(int[] nums, int N) { if...

    N个数全排列c语言算法

    输入N,输出1-N全排列c语言算法,非递归算法................

    c++实现全排列

    递归方法可以通过不断地选择每个元素来生成全排列,但是这种方法在元素个数很多时很容易造成堆栈溢出,因此需要找到一种非递归的方法。 非递归方法可以使用排列组合的知识来解决问题。对于一个包含 N 个元素的集合...

    C语言全排列的递归算法

    为了解决这个问题,可以考虑使用非递归的回溯法或者动态规划等其他方法。 总之,全排列的递归算法是C语言编程中一种重要的算法实现,通过理解递归思想和巧妙地处理数组元素,我们可以有效地解决这类问题。同时,...

    局部搜索解决全排列问题

    在描述中提到,对于n位数字的全排列,可以先找到n-1位数字的全排列,然后将第n位数字插入到这些n-1位排列的任意位置,形成关键排列。关键排列是生成全排列的基础,它们可以通过顺序移动相互转换。 具体到C程序实现...

    算法设计与分析 递归与分治策略.docx

    **算法设计与分析:递归与分治策略** 递归与分治策略是算法设计中的重要方法,它们常用于解决复杂问题。本实验报告主要探讨了三种使用...在实际应用中,有时需要考虑使用非递归的分治策略或其他优化方法来提高效率。

    关于全排列算法

    对于大规模数据,由于递归深度限制和效率问题,可能会考虑使用其他算法,如基于栈的非递归方法或者回溯法等。对于n个数取m个进行排列的问题,可以先用组合算法生成所有可能的m个数的组合,然后再对每个组合进行...

    全排列生成算法字典序vc++源码

    在实际应用中,全排列生成算法可能需要优化以处理大规模数据,比如使用非递归方法,或者通过并行化来提高效率。此外,如果需要按字典序快速查找或插入特定排列,可以考虑使用二叉堆或平衡搜索树等数据结构。 总结来...

    全排序算法c++递归实现

    1. **迭代替代递归**:通过迭代而非递归的方法来生成全排列可以显著减少函数调用的开销。 2. **避免重复计算**:在递归过程中记录已生成的排列,以避免重复计算。 3. **并行处理**:利用多线程或多进程技术来并行...

    全排序问题分析及程序

    在提供的代码中,`Perm`函数是一个递归函数,用于生成给定列表`list`中从索引`0`到`k-1`的元素作为前缀,剩余的元素`k`到`m-1`进行全排列的全部可能。如果`k`等于`m-1`,意味着已经到了排列的最后一个位置,这时函数...

    生成排序C代码

    - 初始化数组`P`,使其包含从1到`n`的整数。 - 调用`perml()`函数生成所有可能的排列。 2. **排列生成函数`perml(int m, int n, int P[])`**: - 参数`m`表示当前处理的元素位置。 - 参数`n`表示数组的总长度。...

    python——全排列数的生成方式

    在上述代码中,首先读取输入的整数`n`,然后创建一个包含1到n的列表`a`。调用`perm`函数,以递归的方式生成所有可能的排列,并存储在`q`中。 为了输出所有排列,我们需要计算排列的总数,即n的阶乘(n!),然后遍历...

    java算法题(30个)

    - 判断素数的方法是检查该数是否能被2到sqrt(n)之间的任何数整除,若不能则为素数。 3. **水仙花数**: - 知识点:三位数处理,位运算。 - 通过循环遍历100-999,提取每位数字并计算立方和。 4. **分解质因数**...

    ACM/ICPC算法大全(c语言)

    - 0-1分数规划是指一类特殊形式的分数规划问题,其中变量只能取0或1。 - **最长有序子序列(递增/递减/非递增/非递减)** - 讨论了如何求解不同类型的最长有序子序列。 - **最长公共子序列** - 最长公共子序列...

    ACM算法整合

    - **0-1分数规划** - 分数规划问题通常涉及最大化或最小化某个分数形式的目标函数。 - **最长有序子序列(递增/递减/非递增/非递减)** - 寻找序列中最长的有序子序列。 - **最长公共子序列** - 寻找两个序列中...

    递归特训(共11道题)1204.pdf

    如果是奇数,`X^N = X^(N-1) * X`。优化策略包括二进制除法和缓存中间结果。 11. **序列搜索**:在一个升序序列中查找一个数。递归方法是如果序列中间元素等于目标值,则返回真;如果目标值小于中间元素,递归搜索...

    全排列算法的原理和实现代码

    对于更大的n,我们可以将第一个位置留给剩下的n-1个数字,然后对剩余的数字进行全排列,重复这个过程直到所有数字都被考虑在内。 以数字集合{1, 2, 3, 4, 5}为例,我们首先固定第一个位置,然后对剩下的数字{2, 3, ...

    浙江大学ACM模板

    - 字典序全排列的概念及其生成方法。 - 如何利用字典序对全排列进行排序。 **2.6 字典序组合** - 字典序组合的定义及其生成方法。 - 在实际问题中如何运用字典序。 #### 三、数据结构 **3.1 并查集** - 并查集的...

    第六次练习赛题解1

    斐波那契数列的定义是F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2),n&gt;=2。在给定的代码中,兔子序列计算采用了递归的方法。函数`fun`通过递归地填充`path`数组来生成特定长度的兔子序列。递归的终止条件是序列的长度等于...

Global site tag (gtag.js) - Google Analytics