1. package com.example.esdemo;
    3. import java.util.*;
    4. import java.util.concurrent.ExecutorService;
    5. import java.util.concurrent.Executors;
    6. import java.util.stream.Collectors;
    8. /**
    9.  * 穷举排列组合原理
    10.  * 示例:123456
    11.  * 算法1的示例:
    12.  * 当我们需要找到长度为4的排列组合时,可以理解为有4个格子,每个格子都有6种可能,都可能是123456
    13.  * 代码里面可以忽略值,直接使用index来代表每个位置,则每个格子都可能是index为 0 - 5
    14.  * 所有的可能组合数量为 6 * 6 * 6 * 6,即6的4次冥
    15.  * <p>
    16.  * 现在就是将每个格子,每次拨动一个,确保每个格子都有和其他格子每个数字配合的机会,简单的话就是用嵌套for循环,比如上面就用4层for循环
    17.  * 但代码怎么动态生成for循环呢,比较难,下面使用单层for循环,使用indexArr来记录每层的i
    18.  * 嵌套for循环是最内层每次都在递增,越往外层,则相邻内层每满6次,外层递增一次
    19.  */
    20. public class QJ {
    22.     public static Set<String> resultSet = Collections.synchronizedSet(new HashSet<>());
    24.     public static void main(String[] args) {
    25.         //字符串长度小于等于9时,有明显的性能优势,之后时间会急速增加到不可接受
    26.         String sourceString = "0123456789";
    28.         //结果集合,这里其实用set更好,可以防止出现str里面有重复元素导致重复排列
    29.         if (sourceString.length() <= 9) {
    30.             System.out.println("使用算法1");
    31.             findStr1(sourceString);
    32.         } else {
    33.             System.out.println("使用算法2");
    34.             findStr2(sourceString);
    35.         }
    36.     }
    38.     /**
    39.      * 算法1,使用单层for循环来查找可能的值,在源数据长度小于等于9时,具备出色的性能表现
    40.      *
    41.      * @param sourceString
    42.      */
    43.     private static void findStr1(String sourceString) {
    44.         int sourceStrLength = sourceString.length();
    45.         long startTime = System.currentTimeMillis();
    46.         int availableProcessors = Runtime.getRuntime().availableProcessors();
    47.         System.out.println(String.format("CPU核心数:%s", availableProcessors));
    48.         ExecutorService executorService = Executors.newFixedThreadPool(availableProcessors);
    49.         boolean useParallel = true;
    50.         //这层循环,控制当前的数字长度,所以从1开始,最大为字符长度
    51.         for (int resultStrLength = 1; resultStrLength <= sourceStrLength; resultStrLength++) {
    52.             int finalResultStrLength = resultStrLength;
    53.             //这里需要根据i的大小,嵌套for循环,每层for循环都是length次数
    54.             long forCount = (long) Math.pow(sourceStrLength, resultStrLength);
    55.             //当总循环次数达到
    56.             long groupCount = forCount / availableProcessors;
    57.             if (useParallel && groupCount > 100000) {
    58.                 System.out.println(String.format("长度[%s]存在[%s]种组合,使用多线程处理", resultStrLength, forCount));
    59.                 long startIndex = 0;
    60.                 for (long i = 0; i < availableProcessors; i++) {
    61.                     long finalStartIndex = startIndex;
    62.                     if (i != availableProcessors - 1) {
    63.                         executorService.submit(() -> {
    64.                             findStr(finalStartIndex, groupCount, sourceString, sourceStrLength, resultSet, finalResultStrLength);
    65.                         });
    66.                     } else {
    67.                         executorService.submit(() -> {
    68.                             findStr(finalStartIndex, forCount - ((availableProcessors - 1) * groupCount), sourceString, sourceStrLength, resultSet, finalResultStrLength);
    69.                         });
    70.                     }
    71.                     startIndex += groupCount;
    72.                     if (startIndex >= forCount) {
    73.                         break;
    74.                     }
    75.                 }
    76.             } else {
    77.                 findStr(0, forCount, sourceString, sourceStrLength, resultSet, resultStrLength);
    78.             }
    79.         }
    80.         //确认所有可能性均以找到
    81.         executorService.shutdown();
    82.         while (!executorService.isTerminated()) {
    83.             try {
    84.                 Thread.sleep(1L);
    85.             } catch (InterruptedException interruptedException) {
    86.                 interruptedException.printStackTrace();
    87.             }
    88.         }
    89.         System.out.println(String.format("共找到%s种组合,耗时%sms", resultSet.size(), System.currentTimeMillis() - startTime));
    90.     }
    92.     /**
    93.      * findStr1的核心方法
    94.      *
    95.      * @param startIndex
    96.      * @param forCount
    97.      * @param sourceString
    98.      * @param sourceStrLength
    99.      * @param resultSet
    100.      * @param resultStrLength
    101.      */
    102.     private static void findStr(long startIndex, long forCount, String sourceString, int sourceStrLength, Set<String> resultSet, int resultStrLength) {
    103.         //创建一个数组,记录每个for循环当前的位置,所以集合长度为当前for循环的层数
    104.         int[] currentIndexArr = null;
    105.         for (long l = startIndex; l < startIndex + forCount; l++) {
    106.             //每次仅拨动一个位置
    107.             //l为当前拨动的总次数,对应调整index集合的所有index值
    108.             if (l == startIndex) {
    109.                 currentIndexArr = setIndexArr(resultStrLength, l + 1, sourceStrLength);
    110.             } else {
    111.                 currentIndexArr = setIndexArr(currentIndexArr, sourceStrLength);
    112.             }
    113.             //查询是否存在重复的index
    114.             if (existsRepeatIndex(currentIndexArr)) {
    115.                 continue;
    116.             }
    117.             //根据当前个位置的index,获取字符串
    118.             getResultStr(sourceString, resultSet, currentIndexArr);
    119.         }
    120.     }
    122.     /**
    123.      * 根据当前循环次数,变更每个index的值,原理为:嵌套for循环是最内层每次都在递增,越往外层,则相邻内层每满6次,外层递增一次
    124.      * 默认原始indexArr全部都是0
    125.      *
    126.      * @param strLength 当前字符串的长度
    127.      * @param count     循环次数
    128.      * @param length    进制数
    129.      * @return
    130.      */
    131.     private static int[] setIndexArr(int strLength, long count, int length) {
    132.         int[] newIndexArr = new int[strLength];
    133.         long highBitIncrement = count;
    134.         for (int i = strLength - 1; i >= 0; i--) {
    135.             //取余,计算当前索引位的步进
    136.             newIndexArr[i] = (int) (highBitIncrement % length);
    137.             if (i != 0) {
    138.                 highBitIncrement = highBitIncrement / length;
    139.             }
    140.         }
    141.         return newIndexArr;
    142.     }
    144.     /**
    145.      * 基于上一次的index集合,从尾部进行递增
    146.      *
    147.      * @param beforeIndexArr 上一次的index集合
    148.      * @param length         进制数
    149.      * @return
    150.      */
    151.     private static int[] setIndexArr(int[] beforeIndexArr, int length) {
    152.         for (int i = beforeIndexArr.length - 1; i >= 0; i--) {
    153.             int beforeIndex = beforeIndexArr[i];
    154.             int newIndex = (beforeIndex + 1) % length;
    155.             beforeIndexArr[i] = newIndex;
    156.             if (newIndex != 0) {
    157.                 return beforeIndexArr;
    158.             }
    159.         }
    160.         return beforeIndexArr;
    161.     }
    163.     /**
    164.      * 根据index集合,找到当前字符串
    165.      *
    166.      * @param str
    167.      * @param set
    168.      * @param indexArr
    169.      */
    170.     private static void getResultStr(String str, Set<String> set, int[] indexArr) {
    171.         char[] chars = new char[indexArr.length];
    172.         for (int i = 0; i < indexArr.length; i++) {
    173.             chars[i] = str.charAt(indexArr[i]);
    174.         }
    175.         String strTemp = new String(chars);
    176.         if (set.add(strTemp)) {
    177. //            System.out.println(strTemp);
    178.         }
    179.     }
    181.     /**
    182.      * 是否存在重复index
    183.      *
    184.      * @param indexArr
    185.      * @return
    186.      */
    187.     private static boolean existsRepeatIndex(int[] indexArr) {
    188.         for (int i = 0; i < indexArr.length; i++) {
    189.             for (int j = 0; j < indexArr.length; j++) {
    190.                 if (i == j) {
    191.                     continue;
    192.                 }
    193.                 if (indexArr[i] == indexArr[j]) {
    194.                     return true;
    195.                 }
    196.             }
    197.         }
    198.         return false;
    199.     }
    201.     /**
    202.      * 算法2,使用递归组合获取元素,在源数据长度大于9以后,相比算法1,具备明显的性能优势,但时间消耗依旧极为可观
    203.      *
    204.      * @param sourceString
    205.      */
    206.     public static void findStr2(String sourceString) {
    207.         long startTime = System.currentTimeMillis();
    208.         List<Character> data = new ArrayList<>();
    209.         for (char c : sourceString.toCharArray()) {
    210.             data.add(c);
    211.         }
    212.         for (int i = 1; i <= sourceString.length(); i++) {
    213.             findStr(data, new ArrayList<Character>(), i);
    214.         }
    215.         System.out.println(String.format("共找到%s种组合,耗时%sms", resultSet.size(), System.currentTimeMillis() - startTime));
    216.     }
    218.     /**
    219.      * findStr2的核心方法
    220.      *
    221.      * @param data
    222.      * @param target
    223.      * @param length
    224.      */
    225.     private static void findStr(List<Character> data, List<Character> target, int length) {
    226.         List<Character> copyData;
    227.         List<Character> copyTarget;
    228.         if (target.size() == length) {
    229.             String strTemp = target.stream().map(String::valueOf).collect(Collectors.joining());
    230.             boolean add = resultSet.add(strTemp);
    231.         }
    232.         for (int i = 0; i < data.size(); i++) {
    233.             copyData = new ArrayList<>(data);
    234.             copyTarget = new ArrayList<>(target);
    235.             copyTarget.add(copyData.get(i));
    236.             copyData.remove(i);
    237.             findStr(copyData, copyTarget, length);
    238.         }
    239.     }
    240. }