、私は次のような2次元配列を持つ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] 
] 

、2番目の値は小文字です3番目の値は投票の割合で、4番目の値は投票の数です。参考までに、オランダの政党です。

私が今しなければならないことは、可能な連合を計算するシステムを作ることです。当事者間の連立は、当事者が議会で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]); 
    } 
} 

問題があるが、このコードは、唯一の可能な連合ではなく、すべての可能な連合を生成します。私は何とか生成された組み合わせを保存し、同じ連合を生成せずにループを再実行する必要があります。このループは、6つ以下の当事者との可能なすべての連合が生成されるまで、これを続けなければならない。その後、ループは停止することができます。

これにはどのような方法が最適ですか？

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); 
} 

これは、すぐにそれらが発見されたとして見出されるGeneratoryieldに連合を使用しています。連合は配列に格納する必要がないため、コードの残りの部分を単純化します。 Browser supportは良いですが、IEではサポートされていません。もちろん、これを変更して必要に応じて配列を使用することもできます。

連合の当事者数はここではパラメータであるため、必要に応じて調整することができます。グローバルなアイデアは、この機能は最小限の連携しか考慮していないということです。すなわち、VVD、PVDA、PVVが連合を形成することができれば、その人たちとCDAも連合ですが、私たちはそれらを考慮しません。さて、私たちは一党連合から始めます。それがうまくいくなら、素晴らしい、連合を報告し、次の当事者に移りなさい。それができなければ、連立政党を追加してください。できない場合は、最後に追加されたパーティを削除し、次のパーティで試し続けます。

アレイ内でどのパーティを試みているかを把握することができます。これは上記のcoalitionize機能のcoalitionです。配列の長さは、連合に加わることができる当事者の最大数です。すべての値は当事者の配列のインデックスであり、そのスロットのために現時点でどのパーティーを試みているかを示します。実際に何人のパーティーが配列に入っているかを追跡するために、変数fixedSoFarがあります。技術的には、この変数を使わずに配列操作（push、pop）を実行することができますが、これは私にとってより明確で速いようです。

もう少し完全なdemoを実装しました。それは、ページにテキストとして見つかった連合を報告し、連合が持つ議席数を示します。

編集。入力データが投票数でソートされている場合、アルゴリズムは当初思ったほど多くの潜在的連合を考慮する必要はありません。私はこれをupdated demoに実装しました。

ループの末尾にあるelse句は、次のようになります。

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

ここで重要な洞察は、連立政権が有効であるために十分な議席を持っていないときに考慮すべき当事者は、当事者の後だけに来るので、私たちはさらに少ない議席を持つことが保証されているすべての連合を除外することができ、ということです現在考えられている。

これは、考えられる連合の数に大きな違いがあります。