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

這是一個再簡單不過的組合問題：

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

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

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

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

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

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

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

代碼如下：

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é)點拆分解空間
        int[] level1Values = IntStream.range(0, itemCount - pickCount + 1).toArray();
        ExecutorService threadPool = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());

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

            // 第一個解和最后一個解
            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 個解。%n", itemCount, pickCount, answerCount.get());
        System.out.printf("執(zhí)行時間 %dms", (System.currentTimeMillis() - start));
    }

    /**
     * 遍歷區(qū)間的組合
     *
     * @param firstPicks 區(qū)間的第一個解
     * @param lastPicks  區(qū)間的最后一個解
     *
     * @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 + " 個解");
        return counter;
    }

    /**
     * 根據(jù)當前解計算下一個解，直到遇到最終解，則返回 null
     *
     * @param picks     當前解
     * @param lastPicks 最終解
     *
     * @return 下一個解或 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 后面的點移回到貼緊 movable 的右側
            partialReset(nextPick, movable);
        }

        return nextPick;
    }

    // 在 picks 中尋找第一個可以右移的點
    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; // 實際上不會返回 -1
    }

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

}