试探法解决彩票组合问题

问题

假设有一种29选7的彩票，每注由7个1~29的数字组成，而且这7个数字不能重复，编写程序输出所有的号码组合。

思路

还是用试探法解决问题的应用场景。组合嘛，只要不重复就行，所以这个问题就变成了输出7个不重复的1到29之间的数字就行。因为总共有7个位置嘛，每个位置有29种可能，所以你只需要尝试7²⁹次，每次判断是不是各个位的数组有相同的，如果都不同就说明找到了一个组合，但是这个方法太暴力了，也太费劲了，时间上伤不起啊。所以要换一种方法，你只要保证每次不同就行，这样首先把这7个位置上放上29~23这个七个数字，而且是顺序的。现在就一般的情况来谈谈，假设现在只有2个位置，也是这样顺序摆放，你会发现一开始相邻的两个位置上一开始就是不同的，然后再把较小的数字减一，这样相邻的2个位置的数字还是不同的，小的一边减到1，此时小的一边减无可减，于是把大的一边减一，此时小的一边再按此法不断减一直到1就得到一个组合，以此类推每一次变化就是一个组合，最后大的一边是2，于是所有情况就都被列举出来了。推而广之，这七个位置也是一样的，只要最大的那一边没有减到7算法就一直这样持续下去。这个算法的实现可以用循环来完成，也可以用递归来实现，本次我想用递归来实现。那么如何递归呢？这个实际上是个什么过程呢？这个就是减法的借位过程只不过每个位发生借位的上限不同，而且还是动态的。借位嘛，大家都知道最后一位的变化速度是最快的，并且每次下越界的时候就向前一位借位。现在考虑第i位，它每一次减都会促使i+1位从第i位当前值-1开始逐次减1。第i位减到什么时候就得借位了呢？假设总共有n位，那第i位的最小值就是n-i。但是如果你要是既考虑低位又考虑高位的事情，那就没法递归了，这个递归必须是单向的。所以你只需要考虑低位的事情，即，本位每减一次就让低位自己递减去，我姑且把本位的最大值称之为iMax，则本位的递减范围就是[iMax,n-i]，注意这里是闭区间。到最后其实是最低位每变化一次就输出一次整个数组，于是最初的输入就是最大的那个数即29，然后数组的元素个数也叫维度，只要检测到这是最后一位就打印呗，很简单这就是个判断，于是看代码就行了。由于这个打印结果太多太长，控制台缓冲区放不下，于是只能把打印结果输出到文件了，文件是我在桌面建立的叫做outPrinters.txt。

使用

package com.company;

public class Main {

    public static void main(String[] args) {
    // write your code here
        Solution.lotteryCombination(29,7);
    }
}

实现

package com.company;

import java.io.FileOutputStream;
import java.io.PrintWriter;

public class Solution {
    /**
     * 使用试探法解决29选7彩票问题
     */
    static public void lotteryCombination(int maxNumber,int lotteryCounter) {
        if (lotteryCounter <= 0 || maxNumber < lotteryCounter) {
            System.out.println("输入错误");
            return;
        }
        int[] combination = new int[lotteryCounter];
        try {
            PrintWriter out= new PrintWriter(new FileOutputStream(System.getProperties().getProperty("user.home") + "/Desktop/outPrinters.txt"));
            Solution.calculation(combination,maxNumber,lotteryCounter,out);
            out.close();
        } catch (Exception e) {
            System.out.println(e.toString());
        }
    }

    /**
     * 递归函数
     * @param combination
     * @param maxValue
     * @param columnCounter
     * @param printWriter
     */
    static private void calculation(int[] combination,int maxValue,int columnCounter,PrintWriter printWriter) {
        for (int counter = maxValue;counter >= columnCounter;counter--) {
            combination[combination.length - columnCounter] = counter;
            if (columnCounter == 1) {
                for (int element:combination)printWriter.print(element + " ");
                printWriter.println();
            } else {
                Solution.calculation(combination,counter - 1,columnCounter - 1,printWriter);
            }
        }
    }
}

输出

开头一部分 结尾一部分