getcombinations.js

    function getBestPhraseCombinationsWithMaxScoreAble(words, phraseNumWordsList, phrasesData, addressCutOrigin, maxScoreAble, exportResult,
                                                       maxConcurrentTasks = 8, getFreeWorker = undefined, setWorkerIsFree = undefined) {
        var clauseNumWords = words.length;

        var rankingTable = [];
        for (var s = 0; s <= maxScoreAble; s++) {
            rankingTable[s] = [];
        }

        var getResult = function () {
            for (var s1 = rankingTable.length - 1; s1 >= 0; s1--) {
                if (rankingTable[s1].length > 0) {
                    for (var c = 0; c < rankingTable[s1].length; c++) {
                        if (rankingTable[s1][c].length > 0) {
                            return rankingTable[s1][c]; // best score with min of cuts
                        }
                    }
                }
            }
        };

        // BEGIN: get phrase address combinations
        var phraseMinWords = phraseNumWordsList[0];
        var phraseMaxWords = phraseNumWordsList[phraseNumWordsList.length - 1];
        var minOfCuts = Math.ceil(clauseNumWords / phraseMaxWords) - 1;
        var maxOfCuts = Math.floor(clauseNumWords / phraseMinWords) - 1;
        if (minOfCuts > maxOfCuts) {
            console.error({minOfCuts, maxOfCuts, phraseMaxWords, phraseMinWords, clauseNumWords});
            throw new Error('minOfCuts > maxOfCuts');
        }

        var tasksDone = [];
        for (var i = minOfCuts; i <= maxOfCuts; i++) {
            tasksDone[i] = false;
        }
        var workersMap = {};

        var pushSubRankingTable = function (subRankingTable, numOfCuts) {
            if (tasksDone[numOfCuts]) {
                return;
            }

            if (subRankingTable[subRankingTable.length - 1].length > 0) { // has combinations reached max score able
                for (var j = numOfCuts + 1; j <= maxOfCuts; j++) {
                    tasksDone[j] = true;
                    if (workersMap[j]) {
                        workersMap[j][0].terminate(); // worker.terminate
                        if (setWorkerIsFree) {
                            setWorkerIsFree(workersMap[j][1]); // workerIndex
                        }
                    }
                }
            }

            var highestScoreEven = 0;
            for (var s = rankingTable.length - 1; s >= 0; s--) {
                if (rankingTable[s].length > 0) {
                    highestScoreEven = s;
                    break;
                }
            }

            for (var s1 = subRankingTable.length - 1; s1 >= 0; s1--) {
                if (subRankingTable[s1].length > 0) {
                    if (s1 < highestScoreEven) {
                        break;
                    }
                    for (var i = 0; i < 5 && i < subRankingTable[s1].length; i++) { // 5 is max number of combinations to export
                        for (var c = 0; c <= maxOfCuts; c++) {
                            rankingTable[s1][c] = [];
                        }
                        rankingTable[s1][numOfCuts].push(subRankingTable[s1][i]);
                    }
                    break; // only add highest score combinations
                }
            }

            tasksDone[numOfCuts] = true;
            if (tasksDone.every(function (isDone) { return isDone; })) {
                exportResult(getResult());
            }
        };
        if (false && getFreeWorker) { // try to not use worker
            console.log('Use worker for nkAB');
            for (var k = minOfCuts; k <= maxOfCuts; k++) {
                (function (k) {
                    var workerAndIndex = getFreeWorker();
                    var worker = workerAndIndex[0];
                    var workerIndex = workerAndIndex[1];
                    worker.postMessage(JSON.stringify({
                        workerTask: 'pushCombinationsWithNumOfCuts',
                        numOfCuts: k,
                        clauseNumWords: clauseNumWords,
                        phraseNumWordsList: phraseNumWordsList,
                        phrasesData: phrasesData,
                        addressCutOrigin: addressCutOrigin,
                        maxScoreAble: maxScoreAble
                    }));
                    worker.onmessage = function (ev) {
                        if (setWorkerIsFree) {
                            setWorkerIsFree(workerIndex);
                        }
                        pushSubRankingTable(ev.data, k);
                    };
                    workersMap[k] = workerAndIndex;
                })(k);
            }
        } else {
            console.log('DO NOT use worker for nkAB');
            for (var j = minOfCuts; j <= maxOfCuts; j++) {
                if (tasksDone[j]) {
                    console.log('break caused by set done by another', j);
                    break;
                }
                pushSubRankingTable(ChineseTextAnalyzer.pushCombinationsWithNumOfCuts(
                    j, clauseNumWords, phraseNumWordsList,
                    phrasesData, addressCutOrigin, maxScoreAble
                ), j);
            }
        }
        // END: get phrase address combinations

    }
    
    function pushCombinationsWithNumOfCuts(numOfCuts, clauseNumWords, phraseNumWordsList, phrasesData,
                                           addressCutOrigin, maxScoreAble) {
        var rankingTable = [];
        for (var s = 0; s <= maxScoreAble; s++) {
            rankingTable[s] = [];
        }
        var maxScoreEven = 0;
        var maxScoreAbleCombination_minLength = clauseNumWords;

        var pushCombination = function (a) {
            var score = 0, com = [], address;

            var comLength = a.length;
            if (comLength > maxScoreAbleCombination_minLength) {
                return;
            }

            if (a.length === 1) {
                address = getPhraseAddress(0, clauseNumWords, addressCutOrigin);
                com.push(address);
                if (phrasesData[address]) score += clauseNumWords; // endCut - startCut
            }
            else { // a.length > 1
                address = getPhraseAddress(0, a[1], addressCutOrigin);
                com.push(address);
                if (phrasesData[address]) score += a[1];
                for (var i = 2; i < a.length; i++) {
                    address = getPhraseAddress(a[i - 1], a[i], addressCutOrigin);
                    com.push(address);
                    if (phrasesData[address]) score += a[i] - a[i - 1];
                }
                // *Note that: `i` was increased more 1 after end the loop (+1 before check loop condition)
                address = getPhraseAddress(a[i - 1], clauseNumWords, addressCutOrigin);
                com.push(address);
                if (phrasesData[address]) score += clauseNumWords - a[i - 1];
            }

            if (score < maxScoreEven) {
                return;
            }

            maxScoreEven = score;
            if (score === maxScoreAble && comLength < maxScoreAbleCombination_minLength) {
                maxScoreAbleCombination_minLength = comLength;
            }

            rankingTable[score].push(com);
        };

        var n = clauseNumWords - 1;
        var k = numOfCuts;
        var C = phraseNumWordsList;
        var A = C[0];
        var B = C[C.length - 1];

        var timerName = 'nkAB ' + n + '.' + k + '.' + C;
        console.log(timerName + ': start');
        console.time(timerName);
        var a = [0];
        if (k === 0) {
            pushCombination(a);
        } else {
            var backtrack = function (i) {
                var x = 0;
                for (var j = a[i - 1] + A
                    ; j <= n - k + i && j - a[i - 1] <= B
                    ; j += C[x] - C[x - 1]
                ) {
                    x++;
                    if (i === k && (n + 1 - j < A || n + 1 - j > B)) {
                        continue;
                    }
                    a[i] = j;
                    if (i === k) {
                        pushCombination(a);
                    } else {
                        backtrack(i + 1);
                    }
                }
            };
            backtrack(1);
        }
        console.timeEnd(timerName);
        return rankingTable;
    }

    function getCombinations(n, k) {
        if (k < 1 || k > n) {
            throw new Error('k is invalid. Condition: 1 <= k <= n');
        }
        var combinations = [];
        var a = [0];
        var pushCombination = () => {
            var c = [];
            for (var i = 1; i <= k; i++) {
                c.push(a[i]);
            }
            combinations.push(c);
        };
        var backtrack = (i) => {
            for (var j = a[i - 1] + 1; j <= n - k + i; j++) {
                a[i] = j;
                if (i === k) {
                    pushCombination();
                } else {
                    backtrack(i + 1);
                }
            }
        };
        backtrack(1);
        return combinations;
    }