如何將一組中的元素分組爲javascript中的不相交子集？

Question

一組9人在2個，3個和4個人的3個不相交的子羣中工作的方式有多少？我如何通過使用javascript回溯來生成所有可能性。

例子：

Gs = group([aldo,beat,carla,david,evi,flip,gary,hugo,ida],[2,2,5]); 

console.log(Gs); // [[aldo,beat],[carla,david],[evi,flip,gary,hugo,ida]], ... 

請注意，我不希望組成員的排列;即[[aldo，beat]，...]與[[beat，aldo]，...]是相同的解決方案。然而，[aldo，beat]，[carla，david]，...]和[[carla，david]，[aldo，beat] ...]之間有區別。

*沒有圖書館請。

Answer 1

如果您只需要路數一組9人，可分爲每2，3和4人3個亞組則這很容易使用C（計算組合數的函數）以數學方式進行計算。

1. 首先你有9個人，你需要選擇2人。因此你做C(9, 2)。
2. 接下來你有7人，你需要選擇3人。因此你做C(7, 3)。
3. 最後，你有4人，你需要選擇4人。因此你做C(4, 4)。然而C(n, n)始終是1。

因此的方式來劃分的一組9人進入的2，3和4人是C(9, 2) * C(7, 3) * C(4, 4) 3個亞組的數目。這可以簡化爲C(9, 2) * C(7, 3)，這是36 * 35這是1260。

我們可以寫一個函數來計算這個我們：

function ways(n) { 
    var l = arguments.length, w = 1; 

    for (var i = 1; i < l; i++) { 
     var m = arguments[i]; 
     w *= combinations(n, m); 
     n -= m; 
    } 

    return w; 
} 

要啓用此功能工作，我們需要定義功能combinations：

function combinations(n, k) { 
    return factorial(n)/factorial(n - k)/factorial(k); 
} 

最後，我們需要定義功能factorial：

function factorial(n) { 
    var f = n; 
    while (--n) f *= n; 
    return f; 
} 

然後我們計算出數字方法如下：

alert(ways(9, 2, 3)); // 1260 

您可以在這裏看到演示：http://jsfiddle.net/bHSuh/

需要注意的是，我們並不需要，因爲這是隱含指定的4人最後的分組。

---

但是我相信你想要生成每種可能的方式。這是運營商非常適合的事情。所以，我們要做的第一件事就是用JavaScript編寫amb操作：

下一步，我們將寫一個挑選一組給定的項目從索引列表的功能：

function pick(list, items) { 
    var length = list.length, selected = [], rest = []; 

    for (var i = 0; i < length; i++) { 
     if (items.indexOf(i) < 0) rest.push(list[i]); 
     else selected.push(list[i]); 
    } 

    return [selected, rest]; 
} 

我們還需要將生成的索引列表的功能：

function getIndices(length) { 
    var indices = []; 

    for (var i = 0; i < length; i++) 
     indices.push(i); 
    return indices; 
} 

最後，我們將遞歸實現group功能：

0現在

function group(options, divisions) { 
    var subgroup = [], groups = [], n = 0; 
    var indices = getIndices(options.length); 
    var division = divisions.shift(), remaining = divisions.length; 

    try { 
     amb(indices, select); 
    } catch (e) { 
     return groups; 
    } 

    function select(index) { 
     subgroup.push(index); 

     if (++n < division) { 
      try { amb(indices.slice(index + 1), select); } 
      catch (e) { /* we want to continue processing */ } 
     } else { 
      var subgroups = pick(options, subgroup); 

      if (remaining) { 
       var children = group(subgroups.pop(), divisions.slice()); 
       var length = children.length; 
       for (var i = 0; i < length; i++) 
        groups.push(subgroups.concat(children[i])); 
      } else groups.push(subgroups); 
     } 

     n--; 
     subgroup.pop(); 
     throw new Error; 
    } 
} 

，你可以按如下方式使用它：再次

var groups = group([ 
    "aldo", "beat", "carla", 
    "david", "evi", "flip", 
    "gary", "hugo", "ida" 
], [2, 3]); 

請注意，您並不需要指定的4人最後的分組，因爲它暗示。

現在讓我們看看輸出是否是因爲我們希望它是：

console.log(groups.length === ways(9, 2, 3)); // true 

你去那裏。確切地說，有1260種方法可以將一組9人分成3個小組，每個小組2,3和4人。

---

現在我知道我的group函數看起來有點令人生畏，但它其實很簡單。嘗試閱讀並理解發生了什麼。

想象一下，你是9人的老闆。你會如何將他們分成2,3和4個人的3個小組？這正是我的group函數的工作方式。

如果在一段時間後仍然無法理解邏輯，我會更新我的答案並詳細解釋group函數。祝你好運。

---

順便說一句我剛剛意識到，對於這個問題，你並不真的需要amb。您可以簡單地使用forEach。生成的代碼會更快，因爲沒有的try-catch塊的：

function group(options, divisions) { 
    var subgroup = [], groups = [], n = 0; 
    var indices = getIndices(options.length); 
    var division = divisions.shift(), remaining = divisions.length; 
    indices.forEach(select); 
    return groups; 

    function select(index) { 
     subgroup.push(index); 

     if (++n < division) indices.slice(index + 1).forEach(select); 
     else { 
      var subgroups = pick(options, subgroup); 

      if (remaining) { 
       var children = group(subgroups.pop(), divisions.slice()); 
       var length = children.length; 
       for (var i = 0; i < length; i++) 
        groups.push(subgroups.concat(children[i])); 
      } else groups.push(subgroups); 
     } 

     subgroup.pop(); 
     n--; 
    } 
} 

因爲我們不使用amb了該計劃已減少十倍的執行時間。見自己的結果：http://jsperf.com/amb-vs-foreach

而且我終於創建了上述程序的演示小提琴：http://jsfiddle.net/Ug6Pb/

Answer 2

我相信有更快的公式，但我從來沒有在數學很大，這似乎工作，如果我理解正確的問題：

function combo(r, ops){ 
    function unq(r){return r.filter(function(a,b,c){return !this[a] && (this[a]=1);},{}); } 

    var combos={}, pairs=[]; 

     r.forEach(function(a,b,c){ 
     combos[a]=r.filter(function not(a){return a!=this && !combos[a]}, a); 
     }); 


     Object.keys(combos).forEach(function(k){ 
     combos[k].forEach(function(a){ 
       pairs.push([k, a]+''); 
     });  
     }); 

     return unq(unq( 
      pairs.map(function(a){ 
        return unq(a.split(",")).sort(); 
       })).map(function(a){ 
        return a.length==ops && a; 
       }).filter(Boolean)) 
      .sort(); 

}//end combo 



var r="aldo,beat,carla,david,evi,flip,gary,hugo,ida".split(","); 

// find groups of different lengths: 

combo(r, 2) // 2 folks == 36 combos 
combo(combo(r, 2), 3) // 3 folks == 84 combos 
combo(combo(combo(r, 2), 3), 4) // 4 folks == 126 combos 

我沒有刻意去遞歸IZE的函數，因爲你只需要去4-in和一個lispy調用的作品，但如果我不得不走得更遠，我想寫一個額外的外包裝夾心呼叫...

Answer 3

核心實施的回溯算法很簡單（見下面的函數doBacktrack）。通常複雜性是在具體的回溯問題的細節

以下是我爲您的問題執行回溯算法。它基於Steven Skiena算法設計手冊中的回溯算法描述（或者我記得的）。我沒有添加修剪算法（因爲它已經使我比我想象的要長:)），但是如果你想提高它的性能，只需爲函數done（）添加一個合理的實現來防止與可以推斷，以不候選人的處理持續可行的解決方案

function backtrack() { 
    var people = 
     ['aldo','beat','carla','david','evi','flip','gary','hugo','ida']; 
    var initial_state = 
     [[], [], []]; 
    var groups = 
     [2, 3, 4]; 
    var data = 
     {groups: groups, people: people, people_idx_for_name: {}}; 
    people.forEach(function(e, i) { 
    data['people_idx_for_name'][e] = i; 
    }); 
    var solutions = []; 

    doBacktrack(initial_state, solutions, data); 

    return solutions; 
} 

function doBacktrack(candidate, solutions, data) { 
// console.log('processing: ' + candidate); 
    if (isSolution(candidate, data)) { 
     processSolution(candidate, solutions); 
    } 
    if (done(candidate, solutions, data)) { 
    return; 
    } 
    var new_candidates = calculateNewCandidates(candidate, data); 

    for (var i=0; i<new_candidates.length; i++) { 
    doBacktrack(new_candidates[i], solutions, data); 
    } 
} 

function calculateNewCandidates(candidate, data) { 
    var groups = data['groups']; 
    var i = 0; 
    while (i<groups.length && candidate[i].length == groups[i]) { i++; } 
    if (i < groups.length) { 
    //determine list of not yet selected people 
    var not_yet_selected = determineNotYetSelectedPeople(candidate, data, i); 

    var results = []; 
    for (var j=0; j<not_yet_selected.length; j++) { 
     var candidate_copy = candidate.slice(0); 
     for (var k=0; k<candidate_copy.length; k++) { 
     candidate_copy[k] = candidate_copy[k].slice(0); 
     } 
     candidate_copy[i].push(not_yet_selected[j]) 
     results.push(candidate_copy); 
    } 
    return results; 

    } else { 
    return []; 
    } 
} 

function determineNotYetSelectedPeople(candidate, data, group) { 
    var people = data['people']; 
    var people_idx_for_name = data['people_idx_for_name']; 
    var selected_people = {}; 
    var results = []; 
    var max = -Number.MAX_VALUE; 
    candidate.forEach(function(candidate_group, i) { 
    candidate_group.forEach(function(already_selected_person_name) { 
     var already_selected_person_idx = people_idx_for_name[already_selected_person_name]; 
     if (max < already_selected_person_idx && i==group) { max = already_selected_person_idx; } 
     selected_people[already_selected_person_name] = true; 
    }); 
    }); 
    for (var i=0; i<people.length; i++) { 
    if (!selected_people[people[i]] && i > max) { results.push(people[i]); } 
    } 
    return results; 
} 

function isSolution(candidate, data) { 
    var groups = data['groups']; 
    for (var i=0; i<groups.length; i++) { 
    if (candidate[i].length != groups[i]) {return false;} 
    } 
    return true; 
} 

function processSolution(candidate, solutions) { 
    var solution = []; 
    candidate.forEach(function(e) { 
    var l = []; 
    solution.push(l); 
    e.forEach(function(f) { 
     l.push(f); 
    }); 
    }); 
    solutions.push(solution); 
} 

//use this to improve performance with prunning if possible 
function done() { 
    return false; 
} 

var solutions = backtrack(); 
console.log(solutions); 
console.log(solutions.length);