与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]); 

这里的关键结论是，当联盟没有足够的席位是有效的，我们可以排除，保证有更少的席位全部联盟，因为双方仅被认为是双方后到来目前考虑。

这使得所考虑的潜在联盟数量出现巨大差异。