本文共 1842 字,大约阅读时间需要 6 分钟。
求从1~m中,取出n个数,排列组合的结果集,典型案例就是大乐透,红球区从1~35,取出5个数,不计顺序。需要用到递归解决不定层级的for循环问题。
代码如下:
/** * 求从1到m共m个数中取出其中n个的排列组合的结果集,最典型的案例就是大乐透,红球区是从1~35取出5个数 * 写for循环的话,需要写n层for循环,但是n不确定,所以无法直接写for循环,只能通过递归。而递归过程中,因为要记录排列组合的结果,所以内层的循环需要依赖外层循环的值 * 这就需要外层循环将值传入内层,而且从内层中可以层层访问外层值,所以在此定义了一个内部类,我这里定义了个双向链表,其实只用到了单向功能。 * @param m * @param n */ public static void ChoossNFromM(int m, int n){ Listresult = new ArrayList<>(); int i = 0; int degree = 0; recursive(i,(m-n+1), degree, n, result,new Node<>(0)); System.out.println(result.size()); //输出结果集大小 //验证下结果集有没有重复的记录,利用set集合,只要set集合的大小和result集合大小一样,说明结果集没有重复结果 Set set = new HashSet<>(); for(int k=0;k result, Node node){ for(int i = startInd;i < endInd;i++){ Node myNode = new Node(i+1); myNode.setPre(node); if(degree < n-1){ recursive(i+1,endInd+1, degree+1, n, result, myNode); }else{ int temp = i; int[] item = new int[n]; for(int k = n-1;k>=0;k--){ if(myNode==null) continue; item[k] = myNode.getValue(); myNode = myNode.pre; } result.add(item); } } } /** * 内部类 * @param */ static class Node { int value; Node next; Node pre; public Node(int value){ this.value = value; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } public Node getPre() { return pre; } public void setPre(Node pre) { this.pre = pre; } }public static void main(String[] args) { ChoossNFromM(35, 5); }
转载地址:http://eqcdi.baihongyu.com/