精华内容
下载资源
问答
  • 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 = -1 j=0
    2 << 30 >> 31 = -1 j=1
    3 << 31 >> 31 = -1 j=0
    3 << 30 >> 31 = -1 j=1
    4 << 29 >> 31 = -1 j=2
    5 << 31 >> 31 = -1 j=0
    5 << 29 >> 31 = -1 j=2
    6 << 30 >> 31 = -1 j=1
    6 << 29 >> 31 = -1 j=2
    7 << 31 >> 31 = -1 j=0
    7 << 30 >> 31 = -1 j=1
    7 << 29 >> 31 = -1 j=2
    8 << 28 >> 31 = -1 j=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排列组合 实现全排列,支持有序和无序

    展开全文
  • import java.util.ArrayList; public class Main{ public static void main(String[] args) { ArrayList<Integer> al=new ArrayList<Integer>(); al.add(1); al.add(2);... al.add...
    import java.util.ArrayList;
    
    public class Main{
    	public static void main(String[] args) {
    		ArrayList<Integer> al=new ArrayList<Integer>();
    		al.add(1);
    		al.add(2);
    		al.add(3);
    		al.add(4);
    		p(al,0);
    	}
    	public static void p(ArrayList<Integer> al,int i) {
    		if(i==4) {
    			System.out.println(al);
    			return;
    		}
    		for(int j=i;j<4;j++) {
    			int t=al.get(j);
    			al.remove(j);
    			al.add(i,t);
    			p(al,i+1);
    			al.remove(i);
    			al.add(j,t);
    		}
    	}
    }
    public class Main{
    	public static void main(String[] args) {
    		int[] arr= {1,2,3,4,5,6};
    		p(arr,0);
    	}
    	public static void p(int[] arr,int i) {
    		if(i==5) {
    			for(int x=0;x<6;x++) {
    				System.out.print(arr[x]);
    			}
    			System.out.println();
    			return;
    		}
    		for(int j=i;j<6;j++) {
    			int t=arr[i];
    			arr[i]=arr[j];
    			arr[j]=t;
    			p(arr,i+1);
    			t=arr[i];
    			arr[i]=arr[j];
    			arr[j]=t;
    		}
    	}
    }

     

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

    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;
    }
    展开全文
  • 金箍棒(金箍咒全排列组合, 量, 量 - 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"); 显示运算历时();
                金箍咒全排列组合("老少皆宜"); 显示运算历时();
    


    

    展开全文
  • 全排列

    2020-02-25 18:14:18
    全排列定义:无序全排列(1~9):字典序全排列: 定义: 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一 个排列。当m=n时所有的排列情况叫全排列。 鄙人不才,只...
  • 输入:[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...
  • 全排列(有序无重) /*全排列板子 */ #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; } ...
  • 46. 全排列 问题描述 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 示例: ...其次全排列是有序的,而组合是无序的。(即对于全排列来说,【1,2】和【2,1】是两个不同的排列) ...
  • 全排列常用方法

    2020-04-04 16:30:44
    元素有序无序都可 #include<cstdio> #include<algorithm> using namespace std; int a[] = {1, 2, 3, 4, 5}; int ans = 0; void f() { do{ for(int i = 0; i < 5; i++) pri...
  • 47. 全排列 II

    2020-12-26 12:07:14
    题目描述:给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。 解题思路:和全排列一样的用dfs+回溯,只是因为可能有重复的元素,因此在进行选择是否进行当前次迭代,通过看当前值是否已经在...
  • 整数分拆以及等差数列多重约束条件下全排列的生成法,杜瑞卿,刘广亮,为了能够实现整数分拆有序和无序的全部排列和组合,以及任意等差数列的全排列生成及其在多重约束条件下的全排列生成,详细论证了
  • 算法总结(9)--全排列问题

    千次阅读 2016-10-22 21:58:08
    leetcode上涉及到的全排列,注意数组的有序,无序,数组元素是否有重复的 主要是递归算法 每个问题记住关键点,注意特殊处理–全排列问题转载 http://blog.csdn.net/morewindows/article/details/7370155/求下一...
  • 题目: 给定一个可包含重复数字的序列,返回所有不重复的全排列。 示例: 输入: [1,1,2] 输出: ...假如你是从开始一题一题做下来的人,这道题应该轻而易举就搞定...数字集是无序的 数字集含有负数 接下来就是将下思...
  • #include&lt;stdio.h&gt;#include&lt;algorithm&gt;using namespace std;int a[4]={1,2,3,4};char b[4]={'a','b','c','d'};... /*若是无序数列,用sort()排序*/ do{ for(int i=0;i&lt;4...
  • 题目要求 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出...2.接着考虑如何去重与排序,由于Collcetion集合中提供了Set接口:存储无序的(不等于随机性,根据数据的hash
  • 执行用时 :8 ms, 在Subsets的...和以前的全排列不同,这次不需要记录是否访问过。也就是不需要额外的数组记录位置: 因为: 这里的子集内部没有顺序。对于没有顺序的题,按顺序来就ok 重点依然在这一句: ...
  • Median on Segments (Permutations Edition)题意:一个长为n的打乱的全排列,给定m,问包含m的区间中,有多少个区间的中位数是m思路:假设m的位置为pos,先处理出[pos+1~n]中到达每个点的,比m大和比m小的差值. 假设一个...
  • 一、重复有序拆分、 二、不重复有序拆分、 1、无序拆分基本模型、 2、全排列、 三、重复有序拆分方案数证明、
  • 实例: ...有序 可以先求无序,再全排列。 接下来再判断是否重复,使用不同的公式。 摘自《离散数学屈婉玲教材》 来自为知笔记(Wiz) 转载于:https://www.cnblogs.com/menghuizuotian/p/383987...
  • Entirely Unsorted Sequences

    2019-08-24 23:09:27
    题目大意:给定一个正整数序列,问这个序列的全排列中完全无序的排列有多少种,一个元素是有序的当且仅当这个元素前面的元素都小于等于它,后面的元素都大于等于它。如果一个排列没有一个元素是有序的,称这个排列是...
  • 文章目录前言一、数组1. 两数之和2. 寻找两个正序数组的中位数3. 盛最多水的容器4. 三数之和5. 打家劫舍系列打家劫舍Ⅰ打家劫舍Ⅱ打家劫舍Ⅲ6.... 全排列问题全排列的下一个排列写出所有的全排列 I写出所有
  • Pythono 实现 Permutation

    2013-10-05 15:27:00
    不管在R 还是python中,都有现成的函数来轻而易举地进行全排列(Permutation)、无序排列等等。今天想要尝试一下使用自己写代码来实现全排列。 首先,我采用的算法如下: 对于一个数列 i.e. 1,2,3,4 想要进行...
  • LeetCode——回溯

    2019-12-24 16:34:44
    46.全排列(通过设定一个visited[]数组,解放判断,无脑从头开始就行,无序考虑index) 47.全排列II(与46不同,含有重复数组,首先需要进行排序,借助于有序数组对重复元素进行剪枝) 39.组合总和(由于可以复用...
  • 凑平方数 蓝桥真题

    2019-05-20 15:07:23
    全排列 然后将每个排列都分成数份 因为组间无序 所以先排个序再去重 写这道题有两个智障错误 第一是忘开longlong 第二是排序时直接对dfs用的序列排序。。 还有注意遇到当前位置是0时要特殊处理 #include <...
  • 集合排序

    2016-05-11 20:02:42
    给出1到N个无序的数字,要求输出全排列, 例如给出 int[] array={5, 4, 6, 9 } 输出全排列: 第 1 个: 4 5 6 9 第 2 个: 4 5 9 6 第 3 个: 4 6 5 9 第 4 个: 4 6 9 5 第 5 个: 4 9 6 5 第 6 个: 4 9 5...

空空如也

空空如也

1 2 3
收藏数 53
精华内容 21
热门标签
关键字:

无序全排列