與Javascript數組創建聯盟組合

Question

我有一個二維數組，如下所示：

let electionResultsData = [ 
    ["VVD", "vvd", 20.5, 2504948], 
    ["PVDA", "pvda", 19.6, 2340750], 
    ["PVV", "pvv", 15.4, 950263], 
    ["CDA", "cda", 13.6, 801620], 
    ["SP", "sp", 9.8, 909853], 
    ["D66", "d66", 6.9, 757091], 
    ["GL", "gl", 6.7, 219896], 
    ["CU", "cu", 3.2, 294586], 
    ["SGP", "sgp", 1.7, 196780], 
    ["PVDD", "pvdd", 1.3, 182162], 
    ["50PLUS", "50plus", 0.9, 177631], 
    ["OVERIG", "overig", 0.2, 51463], 
    ["PIRATEN", "piraten", 0.1, 30600], 
    ["LP", "lp", 0.1, 3335], 
    ["PVDM", "pvdm", 0.1, 3257], 
    ["JEZUSLFT", "jezuslft", 0, 0], 
    ["ONDRNMR", "ondrnmr", 0, 0], 
    ["LOKAAL", "lokaal", 0, 0], 
    ["ARTIKEL1", "artikel1", 0, 0], 
    ["GEENPEIL", "geenpeil", 0, 0], 
    ["VRIJP", "vrijp", 0, 0], 
    ["BURGBEW", "burgbew", 0, 0], 
    ["FVD", "fvd", 0, 0], 
    ["VDP", "vdp", 0, 0], 
    ["NIEUWEW", "nieuwew", 0, 0], 
    ["DENK", "denk", 0, 0], 
    ["STEMNL", "stemnl", 0, 0], 
    ["VNL", "vnl", 0, 0] 
] 

每個陣列中的第一個值是一個政黨的大寫的名字，第二個值是小寫名稱，第三個值是投票的百分比，第四個值是投票數。僅供參考，這些是荷蘭政黨。

我現在要做的是制定一個計算可能的聯盟的系統。如果雙方在議會中獲得超過75個席位（至少76個席位），雙方之間的聯盟才能實現。我做了一個循環來遍歷與此代碼以上數組：

/** 
* Form coalitions of not more than six parties that exceed 75 parliament seats 
*/ 
formCoalitions(electionResultsData) { 
    let coalitions = []; 
    let maxNumberOfCoalitionParties = 6; 

    // Main loop to check all possible coalitions (28 parties * 28 = 784) 
    for (let i = 0; i < 784; i ++) { 
     let coalitionSeats = 0; 
     let partySeats = 0; 
     let coalitionParties = []; 
     let coalition = []; 

     // The inner loop to generate a combination/coalition 
     for (let i = 0; i < electionResultsData.length; i++) { 
      // Check if a coalition has formed yet 
      if (coalitionSeats < 76) { 
       partySeats = (150/100) * electionResultsData[i][2]; 
       coalitionSeats += partySeats; 
       coalitionParties.push(electionResultsData[i][0]); 

       // If coalition has formed 
       if (coalitionSeats > 75) { 
        // Push data into a second dimension coalition array 
        coalition[0] = parseInt(coalitionSeats); 
        coalition[1] = coalitionParties; 

        // Check if the generated coalition array already exists 
        let coalitionsStringified = JSON.stringify(coalitions); 
        let coalitionStringified = JSON.stringify(coalition); 
        let coalitionExists = coalitionsStringified.indexOf(coalitionStringified); 

        if (coalitionExists === -1) { 
         coalitions.push(coalition); 
        } 
       } 
      } 
     } 
    } 

    // Loop through the coalitions (the charts will be drawn here) 
    for (let i = 0; i < coalitions.length; i++) { 
     console.log(coalitions[i]); 
    } 
} 

的問題是，此代碼僅生成一個可能的聯盟，而不是所有可能的聯盟。我需要以某種方式存儲已經生成的組合，並再次運行循環而不生成相同的聯盟。循環必須繼續這樣做，直到所有可能的不超過六方的聯盟產生。之後，循環可以停止。

解決此問題的最佳方法是什麼？

Answer 1

如果計數小於最大項目和座位總數，則可以使用搜索和測試。

function getCombinations(array, sum, max) { 
 

 
    function fork(i, t) { 
 
     var s = t.reduce(function (r, a) { return r + a[2]; }, 0); 
 
     if (s >= sum) { 
 
      result.push([s, t.map(function (a) { return [a[1], a[2]]; })]); 
 
      return; 
 
     } 
 
     if (i < array.length && t.length < max) { 
 
      fork(i + 1, t.concat([array[i]])); 
 
      fork(i + 1, t); 
 
     } 
 
    } 
 

 
    var result = []; 
 
    fork(0, []); 
 
    return result; 
 
} 
 

 
var electionResultsData = [["VVD", "vvd", 50, 2504948], ["PVDA", "pvda", 40, 2340750], ["PVV", "pvv", 35, 950263], ["CDA", "cda", 33, 801620], ["SP", "sp", 29, 909853], ["D66", "d66", 26, 757091], ["GL", "gl", 26, 219896], ["CU", "cu", 23, 294586], ["SGP", "sgp", 21, 196780], ["PVDD", "pvdd", 21, 182162], ["50PLUS", "50plus", 21, 177631], ["OVERIG", "overig", 20, 51463], ["PIRATEN", "piraten", 20, 30600], ["LP", "lp", 16, 3335], ["PVDM", "pvdm", 15, 3257], ["JEZUSLFT", "jezuslft", 14, 0], ["ONDRNMR", "ondrnmr", 14, 0], ["LOKAAL", "lokaal", 13, 0], ["ARTIKEL1", "artikel1", 11, 0], ["GEENPEIL", "geenpeil", 11, 0], ["VRIJP", "vrijp", 9, 0], ["BURGBEW", "burgbew", 9, 0], ["FVD", "fvd", 8, 0], ["VDP", "vdp", 8, 0], ["NIEUWEW", "nieuwew", 6, 0], ["DENK", "denk", 5, 0], ["STEMNL", "stemnl", 4, 0], ["VNL", "vnl", 2, 0]], 
 
    result = getCombinations(electionResultsData, 76, 6); 
 
\t 
 
document.getElementById('out').appendChild(document.createTextNode(JSON.stringify(result, 0, 4)));

<pre id="out"></pre>

Answer 2

我建議如下。這假定當事人按票數排序。

function* coalitionize(data, maxParties) { 
    if (maxParties < 1) return; 
    var coalition = Array(maxParties).fill(0), 
     fixedSoFar = 0; 
    while (coalition[0] < data.length) { 
    let actualCoalition = coalition.slice(0, fixedSoFar + 1); 
    if (numSeats(data, actualCoalition) > 75) { 
     yield actualCoalition.map((i) => data[i]); 
     coalition[fixedSoFar]++; 
    } else if (fixedSoFar < maxParties - 1) { 
     // add a party to the coalition, simply the next party 
     fixedSoFar++; 
     coalition[fixedSoFar] = coalition[fixedSoFar - 1] + 1; 
    } else { 
     // cannot add more parties; quit this approach 
     fixedSoFar--; 
     coalition[fixedSoFar]++; 
    } 
    // check if we don't try anything stupid 
    while (coalition[fixedSoFar] >= data.length) { 
     // cannot add more parties; quit this approach 
     fixedSoFar--; 
     coalition[fixedSoFar]++; 
    } 
    } 
} 

function numSeats(data, coalition) { 
    return coalition 
    .map((i) => data[i][2] * (150/100)) 
    .reduce((a, v) => a + v, 0); 
} 

這使用被當他們被發現發現了一個Generator到yield聯盟。它稍微簡化了其餘的代碼，因爲聯盟不需要存儲在一個數組中。 Browser support很好，但在IE中不支持。如果需要，你當然可以改變它來使用數組。

請注意，聯盟中的派對數量是一個參數，因此您可以根據需要對其進行調整。全球的想法是這個功能只考慮最小的聯盟。也就是說，當VVD，PVDA和PVV可以組成聯盟時，那些加CDA的人也是聯盟，但我們不考慮這些聯盟。現在，我們從一個單一的聯盟開始。如果它行得通，那麼很好，報告聯盟並轉向下一個派對。如果沒有，如果可以的話，加入聯盟黨。如果我們不能，請刪除最後添加的派對，並繼續嘗試下一個派對。

我們可以跟蹤我們在陣列中嘗試的哪一方，這是coalition在上面的coalitionize函數。陣列的長度是可以參加聯盟的派對的最大數量。每個值都是參與方陣列中的索引，表示我們正在嘗試此時隙中的哪一方。爲了跟蹤陣列中實際有多少方，我們有變量fixedSoFar。從技術上講，你可以在沒有這個變量的情況下做一些數組操作（push,pop），但是這對我來說似乎更加清晰和快速。

我在小提琴中實現了一個稍微更完整的demo。它報告在頁面上發現的聯盟，並顯示聯盟擁有多少（小數）席位。

編輯。如果輸入數據按票數排序，那麼算法不需要像我最初想象的那樣考慮儘可能多的潛在聯盟。我已在updated demo中執行了此操作。

唯一的變化是最後的else子句在while循環中變成了以下內容。

do { 
    fixedSoFar--; 
    if (fixedSoFar < 0) return; 
    coalition[fixedSoFar]++; 
} while ((fixedSoFar === maxParties - 2 && 
    coalition[fixedSoFar] === coalition[fixedSoFar + 1]) || 
    coalition[fixedSoFar] + 1 === coalition[fixedSoFar + 1]); 

這裏的關鍵結論是，當聯盟沒有足夠的席位是有效的，我們可以排除，保證有更少的席位全部聯盟，因爲雙方僅被認爲是雙方後到來目前考慮。

這使得所考慮的潛在聯盟數量出現巨大差異。