精华内容
下载资源
问答
  • Java遍历无序全排列组合 在做迷宫生成,拆墙时需要用到无序的全排列,网上找到一段代码,也没有注释,看不懂,自己研究了下,把分析过程贴出来. 原文链接 java排列组合 实现全排列,支持有序和无序 先上代码 /** * 方法...

    Java遍历无序全排列组合

    在做迷宫生成,拆墙时需要用到无序的全排列,网上找到一段代码,也没有注释,看不懂,自己研究了下,把分析过程贴出来.

    原文链接
    java排列组合 实现全排列,支持有序和无序

    先上代码

    /**
         * 方法一:无序
         *
         * @param data
         * @param <E>
         * @return
         */
        public static <E> List<List<E>> arrangeSelect1(List<E> data) {
    
            int size = data.size();
            // 一共 2^size-1 个无序全排列组合
            int count = (int) (Math.pow(2, size) - 1);
    
            List<List<E>> arrangeAllSet = new ArrayList<>();
    
            for (int i = 1; i <= count; i++) {
    
                List<E> arrangeSet = new ArrayList<>();
    
                for (int j = 0; j < size; j++) {
                    if ((i << (31 - j)) >> 31 == -1) {
                        arrangeSet.add(data.get(j));
                    }
                }
                arrangeAllSet.add(arrangeSet);
            }
            return arrangeAllSet;
        }
    
    	@Test
        public void test() {
            List<Integer> data = new ArrayList<Integer>();
            for(int i=0; i<3; i++) {
                data.add(i);
            }
    
            List<List<Integer>> arrangeList1 = arrangeSelect1(data);
            System.out.println(arrangeList1);
    
        }
    

    他这边主要用到了左移和右移,特点如下
    << 左移,丢弃最高位(符号位同样丢弃),0补最低位
    >> 右移 符号位不变,左边补上符号位

    下面上分析过程
    int a = 1;
    0x00000001 (1的16进制)
    0000 0000 0000 0000 0000 0000 0000 0001 (1的二进制)

    执行 1 << 31
    1000 0000 0000 0000 0000 0000 0000 0000

    执行 1 << 31 >> 1
    1100 0000 0000 0000 0000 0000 0000 0000

    执行 1 << 31 >> 2
    1110 0000 0000 0000 0000 0000 0000 0000

    执行 1 << 31 >> 31 = -1
    1111 1111 1111 1111 1111 1111 1111 1111

    执行 1 << 10
    0000 0000 0000 0000 0000 0100 0000 0000

    执行 1 << 10 >> 31 = 0
    0000 0000 0000 0000 0000 0000 0000 0000

    结论: 对于1来说,只有一种情况可以让表达式 1 << (31 - j)) >> 31 == -1 成立,就是 j=0
    对于2,3,4,5…来说,也可以用同样的方法得到 j 的取值,结果如下:

    i 表达式j 取值
    1 << 31 >> 31 = -1j=0
    2 << 30 >> 31 = -1j=1
    3 << 31 >> 31 = -1j=0
    3 << 30 >> 31 = -1j=1
    4 << 29 >> 31 = -1j=2
    5 << 31 >> 31 = -1j=0
    5 << 29 >> 31 = -1j=2
    6 << 30 >> 31 = -1j=1
    6 << 29 >> 31 = -1j=2
    7 << 31 >> 31 = -1j=0
    7 << 30 >> 31 = -1j=1
    7 << 29 >> 31 = -1j=2
    8 << 28 >> 31 = -1j=3
    • 横向看,可以看到数字3对应的 j 有两种情况,7有3种,其实可以看成3 = 1 + 2, 3的表达式是有1和2的表达式组合起来的,同样7 = 1 + 2 + 4,所以7的表达式就是1,2,4的表达式组合起来的.

    • 纵向看 j取值列,可以发现,
      第一行是1个元素{0}的全排列{0},
      第1-4行是两个元素{0, 1}的全排列{[0],[1],[0,1]},
      第1-12行是3个元素{0, 1, 2}的全排列{[0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2]}

    • 所以通过 i 和 j 的两重循环,就可以将所有的无序排列组合全部打印出来.

    • 至于具体的原理分析,可以看我的文章 自制迷宫代码中的 arrangeSelect1() 方法,里面有具体分析。

    参考资料
    java排列组合 实现全排列,支持有序和无序

    展开全文
  • 递归无序全排列

    2014-01-02 21:10:55
    #include void swap(int *a, int *b){  int c;  c = *a;  *a = *b;  *b = c; } void perm(int a[], int num1, int num2){  int i;  if(num1 > num2){  for(i = 0; i ... 
    #include<stdio.h>
    


    void swap(int *a, int *b){
        int c;
        c = *a;
        *a = *b;
        *b = c;
    }


    void perm(int a[], int num1, int num2){
        int i;
        if(num1 > num2){
            for(i = 0; i <= num2; i++){
                printf("%d ",a[i]);
            }
                printf("\n");
                return ;
        }
        else{
            for(i = num1; i<= num2; i++){
                swap(&a[i],&a[num1]);
                perm(a, num1+1, num2);
                swap(&a[i],&a[num1]);
            }
        }
    }


    int main()
    {
        int a[10];
        int i,n;
        printf("Enter the number:");
        scanf("%d",&n);
        for(i = 0; i < n; i++)
            a[i] = i+1;
        perm(a,0,i-1);
        return 0;
    }
    展开全文
  • // 全排列下标 int allIndex = 0; // 目标数组长度 private final int totalCount = 15; // 选几个数 int numCount = 1; // 存储所有的排列 private int[][] allSequence; // 存储单个排列 private final ...

    指定 totalCount 和 numCount 后, 可以打印所有的排列组合

    	// 全排列下标
        int allIndex = 0;
        // 目标数组长度
        private final int totalCount = 15;
        // 选几个数
        int numCount = 1;
        // 存储所有的排列
        private int[][] allSequence;
        // 存储单个排列
        private final int[] simple = new int[numCount];
    
        @Test
        public void test0831() {
            // 初始化allSequence
            double allSequenceCount = 1;
            for (int i=0; i<numCount; i++) {
                allSequenceCount = allSequenceCount * (totalCount-i) / (numCount-i);
            }
            allSequence = new int[(int)Math.round(allSequenceCount)][numCount];
    
            allPossible(0, numCount);
        }
    
        /**
         *
         * @param index 上一层选取的数的下标
         * @param count 这一层需要选几个数
         */
        public void allPossible(int index, int count) {
            for (int i=index; i<totalCount-count+1; i++) {
                simple[numCount - count] = i;
                if (count > 1) {
                    allPossible(i+1, count - 1);
                } else {
                    for (int j=0; j<numCount; j++) {
                        allSequence[allIndex][j] = simple[j];
                    }
                    allIndex++;
                }
            }
        }
    
    展开全文
  • 金箍棒(金箍咒全排列组合, 量, 量 - 2, 量 - 1) + " " : "")); } ++无限嵌套[嵌套量 - 1]; 跟 = 嵌套量; 金箍咒全排列组合 = ""; } while (无限嵌套[0] 量); }               ...

    可以这样说:
    1.使用判断替换内嵌循环体的可以叫做非等待嵌套循环
    2.使用循环体作为内嵌循环的可以叫做等待型嵌套循环
    3.有了无限嵌套循环的算法了

    正是我使用了判断替换内嵌循环,才推导出了无限嵌套循环,自我接触编程以来从未有无限嵌套循环,而是要几层嵌套循环就写几层,现在可以说是有了无限嵌套循环了,看似普通的2层嵌套循环,其实是实现无限嵌套循环功能的,如果说这样的发明创造也算是能为国争光的话,我当仁不让,而且是出自一个业余爱好者发明创造的。

    看我上面发出来的程序,就是混合使用了非等待嵌套循环+等待嵌套循环的做法,可以说非等待嵌套循环有其应用的场景立锥之地,因此,我说可以列入教学,当然不是我一人说了就算的了,我自己觉得留待历史去回答。2019-9-28记录此段话。http://bbs.csdn.net/topics/394557285?page=3#post-409213128

    生成函数:组合的个数是位数的阶乘,规律是从头开始依次把后面各位的提到头位(不是交换位置),并依位次嵌套,把位次的从头开始依次把后面各位的提到头位。

    泛型类型参数 五月五端午香囊(丁香,白术,肉桂,白芷,藿香,艾叶)

     

            static string 金箍棒(string 字符串, int 量, int 插位, int 调位)
            {
                if (插位 == 调位) return 字符串;
                插位 = Math.Abs(插位 %= 量); 调位 = Math.Abs(调位 %= 量);
                string 前 = "", 后 = "", 读 = "";
                int 头 = 0, 尾 = 量 - 1;
                Action<bool> 合成 = delegate(bool 选)
                {
                    if (选) { 前 += 读; ++头; } else { 后 = 读 + 后; --尾; }
                };
                Action<bool> 读取 = delegate(bool 选)
                {
                    读 = (选 ? 头 : 尾) != 调位 ? 字符串[(选 ? 头 : 尾)].ToString() : "";
                    合成(选);
                };
                Action<bool> 处理 = delegate(bool 选)
                {
                    if ((选 ? 头 : 尾) < 插位) 读取(选);
                    else if ((选 ? 头 : 尾) == 插位)
                    {
                        读 = 字符串[调位].ToString() + (插位 != 调位 ? 字符串[插位].ToString() : "");
                        合成(选);
                    }
                    else if ((选 ? 头 : 尾) > 插位) 读取(选);
                };
                do
                {/*字符量奇偶处理,采用折半我称双向处理,减少循环量提高处理速度,对整体减少时间是有效的2016-1-30 17:59*/
                    if (头 <= 尾) 处理(true);
                    if (头 < 尾) 处理(false);
                } while (头 <= 尾);
                return 前 + 后;
            }
            static void 金箍咒全排列组合(string 字符串)
            {
                string 金箍咒全排列组合 = "";
                int 量 = 字符串.Length, 嵌套量 = 量 - (量 > 2 ? 2 : 1)/*设置跳过位数*/, 跟 = 嵌套量;
                int[] 无限嵌套 = Enumerable.Repeat(0, 嵌套量).ToArray();
                do/*2016年1月29日16~17点钟完成:1.字符串不转数组2.字符串不进行位置交换只按变化的下标读取3.减少一半循环量直接获得2个排列组合效率高4.按顺序输出不需重新排序5.自动嵌套代码量比写固定嵌套少6.依然可以对数组执行。减少一个嵌套可节省很多循环量,用直接获取最后2位组合可节省一半循环量,这就是只循环生成一半的量,只是不是用反转数的逻辑,妙不可言!是这个算法的快诀窍,不过这种方式到底是否节省一半循环量觉得有点不可思议的感觉。*/
                {
                    if (量 < 2) break;
                    while (--跟 >= 0)/*嵌套逐级运算*/
                        if (无限嵌套[跟] >= 量 - 跟)
                        {
                            if (跟 - 1 < 0) break;/*防止越界*/
                            ++无限嵌套[跟 - 1];
                            无限嵌套[跟] = 0;
                        }
                    if (无限嵌套[0] < 量)
                    {
                        跟 = 0; /*Console.WriteLine(string.Join(" ", 无限嵌套));*/
                        foreach (int 嵌套 in 无限嵌套)
                            金箍咒全排列组合 = 金箍棒(跟 == 0 ? 字符串 : 金箍咒全排列组合, 量, 跟, 嵌套 + 跟++);
                        Console.Write(金箍咒全排列组合 + " " + (量 > 2 ? 金箍棒(金箍咒全排列组合, 量, 量 - 2, 量 - 1) + " " : ""));
                    }
                    ++无限嵌套[嵌套量 - 1];
                    跟 = 嵌套量;
                    金箍咒全排列组合 = "";
                } while (无限嵌套[0] < 量);
            }

     

     

     

     

     

     

     

     

     

    主函数调用:

                Action 显示运算历时 = delegate()
                { Console.WriteLine("运行时间: {0}ms", 总运行时间.ElapsedMilliseconds); Console.WriteLine("准备就绪按回车键开始:"); Console.ReadKey(); 总运行时间 = Stopwatch.StartNew(); };
                金箍咒全排列组合("12"); 显示运算历时();
                金箍咒全排列组合("123"); 显示运算历时();
                金箍咒全排列组合("1234"); 显示运算历时();
                金箍咒全排列组合("12345"); 显示运算历时();
                金箍咒全排列组合("123456"); 显示运算历时();
                金箍咒全排列组合("1234567"); 显示运算历时();
                金箍咒全排列组合("12345678"); 显示运算历时();
                金箍咒全排列组合("123456789"); 显示运算历时();
                金箍咒全排列组合("0123456789"); 显示运算历时();

                金箍咒全排列组合("AB"); 显示运算历时();
                金箍咒全排列组合("ABC"); 显示运算历时();
                金箍咒全排列组合("ABCD"); 显示运算历时();
                金箍咒全排列组合("老少皆宜"); 显示运算历时();
    


    

    展开全文
  • 全排列算法

    2021-03-21 21:53:04
    全排列算法 方法一:加与不加 思想:每次考虑当前元素时,面临两个选择,即加入子集或者不加入子集,如图所示: 看了图片之后便可对此一目了然 代码如下: package 递归; import java.util.HashSet; import java....
  • 全排列 题目来源:open judge1750全排列 全排列 .0 #include <bits/stdc++.h> using namespace std; void permutation(char a[],int m,int n){//对下标为m_n的字符数组段进行排列 if(m==n){//安排好了最后一...
  • 全排列

    2020-02-25 18:14:18
    全排列定义:无序全排列(1~9):字典序全排列: 定义: 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一 个排列。当m=n时所有的排列情况叫全排列。 鄙人不才,只...
  • 对于求解全排列问题有最暴力的递归枚举法,但是我们希望可以优化时间,因此出现了递归交换法。
  • C++全排列

    千次阅读 2019-03-03 17:35:55
    最近通过学习算法, 了解了全排列实现的几种方式,在此记录总结一下。 方式一:DFS深度优先搜索 该算法的实现可以当成模板来套用,当然本菜鸡习惯的写法不一定适合你,不过个人觉得还是比较好理解的,你可以多看看...
  • N个数的无重复全排列

    2021-04-13 22:48:59
    文章目录一、输出N个数的无重复全排列二、思路三、代码: 一、输出N个数的无重复全排列 Input: 输入一个数值N(1<=N=50) Output: 输出N个数的无重复全排列,每个数之间用空格隔开 最后一行输出无重复全排列的...
  • 全排列(有序无重) /*全排列板子 */ #include<stdio.h> int a[10],n,hash[10]={0}; void dfs(int step) { if(step==n+1) { for(int i=1;i<=n;i++) printf("%d ",a[i]); printf("\n"); return; } ...
  • 输入:[1,2,3,4]输出: 方法一:无序 [[1],[2],[1,2],[3],[1,3],[4],[2,3],[1,4],[1,2,3],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4]] 方法二:有序 [[1],[2],[3],[1,2],[4],[1,3],[1,4],[2,3],[2,4],[1,2,3],[3...
  • C++ STL 全排列函数详解

    千次阅读 2019-05-01 21:29:28
    其实全排列在c++中有标准库,直接调用就行,简直不能太爽! 头文件:#include <algorithm> 函数模板:next_permutation(arr, arr+size); 函数模板:prev_permutation(arr, arr+size); 解释:arr为数组,...
  • 全排列问题

    2016-03-28 21:56:48
    1、打印一个无重复元素数组的全排列public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> ans = new ArrayList(); if (nums==null || nums.length==0) { return ans; } permute(an
  • 对于排列后的数据,判断数据是否满足特定需求(此处为是否能够被7整除) package search; import java.util.*; public class test { static List<String> result = new ArrayList<... public static void ...
  • 全排列的算法及c++实现

    千次阅读 2016-02-29 23:19:44
    全排列:当n==m时,称为全排列。例如,如果集合是{a,b,c},那么这个集合中元素的所有排列是{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)},显然,给定n个元素共有n!种不同的排列,如果给定集合是{a,b,c,d},...
  • 题目: 给定一个可包含重复数字的序列,返回所有不重复的全排列。 示例: 输入: [1,1,2] 输出: ...假如你是从开始一题一题做下来的人,这道题应该轻而易举就搞定...数字集是无序的 数字集含有负数 接下来就是将下思...
  • 全排列的java实现(含重复数字)

    千次阅读 2014-02-28 10:42:36
    全排列就是从第一个数字起每个数分别与它后面的数字交换。 我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这二个数就不交换了。如122,第一个数与后面交换得212、221。然后122中第二数就不用与第三个...
  • js实现全排列组合算法

    万次阅读 2017-07-06 20:11:03
    js实现全排列组合算法
  • 全排列的实现

    2017-04-06 18:41:00
    实现方法文章主要讲两种实现全排列的方法: 1. 使用C++的STL模板实现数字或字符的全排列。 2. 使用递归的思想实现数字或字符的全排列。STL模板实现在C++的模板中,有一对专门用于实现数字或字符全排列的模板:next...
  • 整数分拆以及等差数列多重约束条件下全排列的生成法,杜瑞卿,刘广亮,为了能够实现整数分拆有序和无序的全部排列和组合,以及任意等差数列的全排列生成及其在多重约束条件下的全排列生成,详细论证了
  • 全排列 II 包含重复数字序列,返回不重复全排列 tips python中传参是形参,如int,tuple等,但是遇到动态数组或集合就是传递的实参,如set和list,dict 动态数组无法被hash化,所以无法加入集合,转为tuple形式即可...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,592
精华内容 636
关键字:

无序全排列