摘要：如何用多線程遍歷這棵樹呢按一級節(jié)點(diǎn)不同的值，分別放到線程里面遍歷即可。代碼如下多線程遍歷組合樹根據(jù)一級節(jié)點(diǎn)拆分解空間對拆分的解空間多線程遍歷第一個(gè)解和最后一個(gè)解遍歷解區(qū)間取的組合遍歷完成，共有個(gè)解。

這是一個(gè)再簡單不過的組合問題：

編號 0-9 的 10 個(gè)球里面拿取任意 5 個(gè)，有多少種不同的組合？

答案是可以用公式算出來的，也就是 (10!) / ((5!) ^ 2) = 252 個(gè)。但是如果要把它們?nèi)勘闅v出來呢？

下面是一種效率比較高的遍歷方式，原理是將所有結(jié)果集看作是樹節(jié)點(diǎn)（準(zhǔn)確的說是葉子節(jié)點(diǎn)），然后去遍歷這棵樹即可。樹的生成規(guī)則是：

一級節(jié)點(diǎn)的值是第一個(gè)球的編號，二級節(jié)點(diǎn)是第二個(gè)球的編號，依此類推；

任何一級節(jié)點(diǎn)的值必須大于上級節(jié)點(diǎn)的值。

這樣能做到所有的葉子節(jié)點(diǎn)剛好覆蓋所有的解，沒有多余沒有缺失。

如何用多線程遍歷這棵樹呢？按一級節(jié)點(diǎn)不同的值，分別放到線程里面遍歷即可。每個(gè)節(jié)點(diǎn)代表一個(gè)子樹，先計(jì)算該樹的起始和終止節(jié)點(diǎn)，作為解空間的邊界，然后從起始節(jié)點(diǎn)開始遍歷直到終止節(jié)點(diǎn)為止即可。

代碼如下：

import java.util.Arrays;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicLong;
import java.util.stream.IntStream;

/**
 * 多線程遍歷組合樹
 */
public class CombinationIterator {

    public static void main(String[] args) throws Exception {

        int itemCount = 50;
        int pickCount = 10;
        AtomicLong answerCount = new AtomicLong();

        long start = System.currentTimeMillis();

        // 根據(jù)一級節(jié)點(diǎn)拆分解空間
        int[] level1Values = IntStream.range(0, itemCount - pickCount + 1).toArray();
        ExecutorService threadPool = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());

        // 對拆分的解空間多線程遍歷
        for (int level1Value : level1Values) {

            // 第一個(gè)解和最后一個(gè)解
            int[] firstPicks = IntStream.range(level1Value, pickCount + level1Value).toArray();
            int[] lastPicks =
                    IntStream.concat(
                            IntStream.range(level1Value, level1Value + 1),
                            IntStream.range(itemCount - pickCount + 1, itemCount)
                    ).toArray();

            // 遍歷解區(qū)間
            threadPool.submit(() -> answerCount.addAndGet(iterateSubTree(firstPicks, lastPicks)));
        }

        threadPool.shutdown();
        threadPool.awaitTermination(1, TimeUnit.HOURS);

        System.out.printf("%d 取 %d 的組合遍歷完成，共有 %d 個(gè)解。%n", itemCount, pickCount, answerCount.get());
        System.out.printf("執(zhí)行時(shí)間 %dms", (System.currentTimeMillis() - start));
    }

    /**
     * 遍歷區(qū)間的組合
     *
     * @param firstPicks 區(qū)間的第一個(gè)解
     * @param lastPicks  區(qū)間的最后一個(gè)解
     *
     * @return 區(qū)間的解數(shù)量
     */
    private static long iterateSubTree(int[] firstPicks, int[] lastPicks) {
        long counter = 0;
        int[] picks = firstPicks;

        do {
            if (picks != null) {
                // System.out.println(Arrays.toString(picks));
                counter++;
            }

            picks = getNextPick(picks, lastPicks);
        } while (picks != null);

        System.out.println("區(qū)間 " + Arrays.toString(lastPicks) + " 遍歷完成，共 " + counter + " 個(gè)解");
        return counter;
    }

    /**
     * 根據(jù)當(dāng)前解計(jì)算下一個(gè)解，直到遇到最終解，則返回 null
     *
     * @param picks     當(dāng)前解
     * @param lastPicks 最終解
     *
     * @return 下一個(gè)解或 null
     */
    private static int[] getNextPick(int[] picks, int[] lastPicks) {

        if (Arrays.equals(picks, lastPicks)) {
            return null;
        }

        int[] nextPick = Arrays.copyOf(picks, picks.length);
        int movable = findMovable(nextPick, lastPicks);
        nextPick[movable]++;

        if (movable != nextPick.length - 1) {
            // 將 movable 后面的點(diǎn)移回到貼緊 movable 的右側(cè)
            partialReset(nextPick, movable);
        }

        return nextPick;
    }

    // 在 picks 中尋找第一個(gè)可以右移的點(diǎn)
    private static int findMovable(int[] picks, int[] lastPicks) {

        for (int i = picks.length - 1; i >= 0; i--) {
            if (picks[i] < lastPicks[i]) {
                return i;
            }
        }

        return -1; // 實(shí)際上不會(huì)返回 -1
    }

    // 指定位置后面的點(diǎn)都移回到貼緊該位置的右側(cè)
    private static void partialReset(int[] picks, int resetStart) {
        for (int i = resetStart + 1; i < picks.length; i++) {
            picks[i] = picks[i - 1] + 1;
        }
    }

}