javascript - 给定参与者列表的最大并发 session

Question

问题

在我们的团队签到后，我们中断了与 (n) 名参与者的协调 session ，讨论了各种(唯一命名的)主题。

目前，人们站在一旁试图 self 组织，我们没有最大化 session 的并发性，和/或尽快释放团队成员返回工作岗位。

我们在 Google Spreadsheet 中保留了所有签到后的所有协调 session 的列表。 :

+-----------------------------------------------------------+
|  Meetings                                                 |
+-----------------------------------------------------------+
|  Topic A  |  Topic B  |  Topic C  |  Topic D  |  Topic E  |
+-----------------------------------------------------------+
|  Billy    |   JD      |  David    |   Tania   |   JB      |
|  Mel      |   Rowan   |  Emily    |   David   |   Fred    |
|  Tracey   |   Mike    |           |   Mike    |   Tania   |
|  JB       |   Aaron   |           |   Fred    |           |
|  Luke     |   Billy   |           |           |           |
|  Aaron    |           |           |           |           |
|  Michael  |           |           |           |           |
+-----------------------------------------------------------+

作为起点，我有(肯定是非常低效的)代码迭代每次 session 并返回没有参与者冲突的对数组。

main() 的示例输出，上面作为输入数据(不用担心所有代码都在下面):

[["主题 A","主题 C"],["主题 A","主题 D"],["主题 B","主题 C"],["主题 B","主题 E"],["主题 C","主题 E"]]

我需要什么

理想情况下，我需要一个解决方案，该解决方案可以返回一个数组，该数组按可能一次运行的大多数 session 排序。要么使用从 main 返回的对数组() 或使用电子表格中的数据作为输入的完全不同的方法。

在我这里的示例中，它将采用以下形式:

[[主题 B、主题 C、主题 E]、[主题 A、主题 D]]

然后，我将在 Google 电子表格中按颜色对这些进行可视化分组，以便员工可以看到。

我试图创建一些代码 (main2()) 来减少基于互斥对的数组，但这是完全错误的。例如:该代码输出:

[["主题 A","主题 C","主题 B","主题 E"],"主题 D"]

...这是不正确的，因为 A 和 B 显然有冲突。 (当然A和C，B和E连续就好了)。

我的当前代码

function onOpen () {
 var ui = SpreadsheetApp.getUi();
  ui.createMenu('Meeting Tools')
  .addItem('Compute Optimal Meeting Order', 'main')
  .addToUi();
}

function main() {
  var ss = SpreadsheetApp.getActive();
  var sss = ss.getActiveSheet();
  //var sss = ss.getSheetByName("Sheet3");
  var data = sss.getDataRange().getValues();

  var ui = SpreadsheetApp.getUi();

  var meetings = {};
  var pairs = [];
  var objKey;

  // Structuring data to obj
  for (var x=0; x < sss.getLastColumn(); x++) {
    for (var y=1; y < data.length; y++) {
      if (y==1) {
        objKey = data[y][x];
        meetings[objKey] = [];
      }
      else if (data[y][x]) {
        meetings[objKey].push(data[y][x]);
      }
    }
  }

  var keys = Object.keys(meetings).sort();
  var loc;

  // Starting with "A"
  for (var m in meetings) {
    if (!meetings.hasOwnProperty(m)) continue;

    Logger.log("-----------------------------");
    Logger.log("SCANNING:  " + m);
    Logger.log("-----------------------------");

    loc = keys.indexOf(m);

    // check A, B, C, D, E
    for (var m2 = 0; m2 < keys.length; m2++) {

      var pointer = (m2 + loc) % keys.length;      
      // DO NOT CHECK SAME MEETING
      if (keys[pointer] == m) {
    Logger.log("||||||||| WE ARE COMPARING OURSELVES: (" + keys[pointer] + "/"     + m + "). SKIPPING!");
        continue;
      }

      // FOR EACH PARTICIPANT OF CURRENT MEETING
      for (var p = 0; p < meetings[m].length; p++) {

        Logger.log("");
        Logger.log("  >>> COMPARING " + keys[pointer]);
        Logger.log("  >>> >>> " + meetings[m][p] + " " + (p+1) +"/"+meetings[m].    length);

          // SEEK THE LOCATION OF THE MEETING PARTICIPANT IN THE NEXT MEETING
          var testIndex = meetings[keys[pointer]].indexOf(meetings[m][p]);

          // IF THE MEETING PARTICIPANT IS ALSO IN THE NEXT MEETING
          if (testIndex > -1) {

        Logger.log("We have a match! Meeting "+ m + " has participant " + meetings[m][p] + " which unfortunately clashes with meeting " + keys[    pointer]);
        Logger.log("Therefore Meeting " + m + " cannot run at the same time as     " + keys[pointer]);
        Logger.log("We need to bail out of compairing against: " + keys[pointer    ]);

            // WE BAIL OUT AS WE HAVE A CLASH
            break; 
          }
      // IF THE MEETING PARTICIPANT IS NOT IN THE NEXT MEETING AND WE HAVE     CHECKED EVERYONE. WE SHOULD BE GOOD.
          else if (testIndex == -1 && p+1 == meetings[m].length) {
            Logger.log("This looks to be clear!!! Adding to pair group.");
            pairs.push([m,keys[pointer]]);
          }
      }//loop
    } //loop
  } //obj_loop

  // Logger.log("FINAL TALLY: " + JSON.stringify(pairs));
     Logger.log("FINAL TALLY (CLEANED): " + JSON.stringify(removeRepeats(pairs.sort())    ));

  // ui.alert(JSON.stringify(removeRepeats(pairs.sort())));
  // ss.toast(JSON.stringify(removeRepeats(pairs.sort())));

  // debugger;
  return removeRepeats(pairs.sort());
}


function main2(array) {

  // DEBUG
  //  array = [["A","C"],["A","D"],["B","C"],["B","E"],["C","E"]];
  //  array = [["A","C"],["A","D"],["B","C"],["B","E"],["C","E"]];
  array = main();

  var holdingArr = [];
  for (var i = array.length - 1; i >= 1; i--) {

    //DEBUG
    //var pair = ["Z","X"];
    var pair = array[i];

    if (arrayPairCheck([array[0]], pair)) {
      holdingArr.push(pair);
      array.pop(i);
    } 
    else {
      array[0] = array[0].concat(array[i]);
      array.pop(i);
    }
  } //loop

  if (holdingArr && holdingArr.length > 0) {
    for (var j=0; j < holdingArr.length; j++) {
      var checkIndex = holdingMeetingExistsInPair(array[0],holdingArr[j]);
      if (checkIndex !== false) {
        array.push(holdingArr[j][checkIndex]);
      }
    } //loop
  }

  // DEBUG
  debugger;
  Logger.log(JSON.stringify(array));
}


function holdingMeetingExistsInPair(arrayFirstIndexGroup,holdingArrPair) {
  if (arrayFirstIndexGroup && arrayFirstIndexGroup.length > 0) {
    if (arrayFirstIndexGroup.indexOf(holdingArrPair[0]) === -1) {
      return 0;
    }
    if (arrayFirstIndexGroup.indexOf(holdingArrPair[1]) === -1) {
      return 1;
    }
  }
  return false;
}


function arrayPairCheck(array,pair) {

  // DEBUG
  // array = [["A","C"],["A","D"],["B","C"],["B","E"],["C","E"]];
  // pair = ["Z","X"];

  var seen = false;

  if (array && array.length > 0) {
    for (var i=0; i < array.length; i++) {
      array[i].map(function(item,item2) {
        if (item === pair[0] || item === pair[1]) {
          seen = true;
          return true;
        }
      });
    } //loop
  }

  if (seen) { return true; } else { return false; }
}

// http://stackoverflow.com/questions/27734661/javascript-arrays-ab-ba
function removeRepeats(list) {
    var i;
    var b = [];
    var _c = [];

    for (i = 0; i < list.length; i++) {
        var a = list[i].sort();
        var stra = a.join("-");

        if(_c.indexOf(stra) === -1) {
            b.push(a);
            _c.push(stra);
        }
    }

    return b;
}

最后

我一直在阅读有关拼凑理解的一些途径如下。我的代表太低无法链接这些。有人可能会确认这是一个追求的方向？

• Traveling salesman problem

• Hopcroft–Karp 算法

感谢您花在这上面的时间。

更新 1

对于以下情况，解决方案应正确地将 session 顺序设置为:

1) W, X, Z
2)V，Y

+-----------------------------------------------------------+
|  Meetings                                                 |
+-----------------------------------------------------------+
|  Topic V  |  Topic W  |  Topic X  |  Topic Y  |  Topic Z  |
+-----------------------------------------------------------+
|  Billy    |   JD      |  David    |   Tania   |   JB      |
|  Mel      |   Rowan   |  Emily    |   David   |   Fred    |
|  Tracey   |   Mike    |           |   Mike    |           |
|  JB       |           |           |   Fred    |           |
|  Luke     |           |           |           |           |
|  Aaron    |           |           |           |           |
|  Michael  |           |           |           |           |
+-----------------------------------------------------------+

Answer 1

这绝对是一个有趣的问题。我的方法是使用矩阵运算来找出哪些主题没有冲突。第一步是创建一个矩阵来表示没有冲突的对，类似于您的方法。

所以对于这个示例数据集

+-----------------------------------------------------------+
|  Meetings                                                 |
+-----------------------------------------------------------+
|  Topic A  |  Topic B  |  Topic C  |  Topic D  |  Topic E  |
+-----------------------------------------------------------+
|  Billy    |   JD      |  David    |   Tania   |   JB      |
|  Mel      |   Rowan   |  Emily    |   David   |   Fred    |
|  Tracey   |   Mike    |           |   Mike    |   Tania   |
|  JB       |   Aaron   |           |   Fred    |           |
|  Luke     |   Billy   |           |           |           |
|  Aaron    |           |           |           |           |
|  Michael  |           |           |           |           |
+-----------------------------------------------------------+

我们可以说主题 A 与主题 C 和主题 D 没有冲突，我们可以像这样用矩阵/数组表示它:

+---------------------------------------------------------------+
        |Topic A|Topic B |Topic C|Topic D|Topic E|
Topic A |1      |0       |1      |1      |0      |

但是，Topic C 和 Topic D 确实有冲突，我们稍后再讲。同样，我们像这样填充剩余的矩阵

Unique Pair Matrix
        TopicA TopicB TopicC TopicD TopicE
TopicA  1      0      1      1      0   
TopicB  0      1      1      0      1   
TopicC  1      1      1      0      1   
TopicD  1      0      0      1      0   
TopicE  0      1      1      0      1   

正如您从该表中注意到的，主题 C 行有 0 对应于主题 D 列，这表示冲突。另外，请注意，对 Angular 线设置为 1，因为相同的 session 不会相互冲突(同样对于下一步，我们需要将其设置为 1)。

接下来只需将矩阵乘以自身即可得到如下所示的矩阵。理想情况下，你会转置矩阵然后相乘，在这种情况下，你不需要(方阵)

Number of Unique Pair Matrix
        Topic A Topic B Topic C Topic D Topic E
Topic A 3       1       2       2       1
Topic B 1       3       3       0       3
Topic C 2       3       4       1       3
Topic D 2       0       1       2       0
Topic E 1       3       3       0       3

此矩阵表示 session 不相互冲突的次数。因此，为了满足 A 和 C，它们不会冲突两次，一次是从第 1 行计算的，另一次是从第 3 行计算的。类似地，对于主题“D”和“A”，我们得到一个值 2。但是总的唯一对A(以对 Angular 线值表示)为 3，这意味着满足 C 和 D 有冲突，因为它们只与 A 形成唯一对两次。

在第 2 行中，您会注意到，主题 B、C、E 来自总共 3 个独特的对，这代表可以一起举行的 session 的最多数量以及这些 session 中可以举行的 session 。

使用此功能，您可以确定首先召开的 session 数量最多的 session ，然后是其余 session 。下面的代码正是这样做的:

function onOpen () {
 var ui = SpreadsheetApp.getUi();
  ui.createMenu('Meeting Tools')
  .addItem('Compute Optimal Meeting Order', 'Jmain')
  .addToUi();
}
function Jmain() {
  var ss = SpreadsheetApp.getActive();
  var sss = ss.getActiveSheet();
  var sss = ss.getSheetByName("Sheet2");
  var data = sss.getRange(2,1,sss.getLastRow()-1,sss.getLastColumn()).getValues();
 //This the matrix that will hold data for unique pairs
  var shadowRel = []
  var headers = data[0].slice()
  data = transpose(data)
  var shadowRel = []
  for (var i = 0 ; i < data.length ; i ++){
    shadowRel[i] = headers.slice()                                            //Each Row is set Headers values to begin with
    for (var j = 1 ; j < data[i].length ; j++){
      var found = false
     for(var k = 0 ; k < data.length ; k++){

       if(k != i) {
         if (data[k].indexOf(data[i][j]) != -1 && data[i][j] != ""){
             //
            shadowRel[i][k] = 0                                                   // Whenver there is a clash the martix is set to zero
            found = true
         }  
       }
     }
    }
  }

 shadowRel = mMutliply (shadowRel)              //Matrix Multiplication
 sss = ss.getSheetByName("Sheet3")                
 sss.getRange(2,2,shadowRel.length,shadowRel[0].length).setValues(shadowRel)        //Set the values of multiplied martix in sheet 3
 var ui = SpreadsheetApp.getUi()

 var meetingOrder = mostNoMeetings(shadowRel,headers)
 Logger.log("Meeting Order: ")
 Logger.log(meetingOrder)
 var prompt = "Meeting Order: "
 for (i = 0 ;i <meetingOrder.length; i++){
 prompt += "\n"+(i+1)+") "+ meetingOrder[i]
 }
 ui.alert(prompt)
}

// Transpose the data so as to check match in each row. 
function transpose(arr) {
        return Object.keys(arr[0]).map(function (c) {
            return arr.map(function (r) {
                return r[c];
            });
        });
    }

function mMutliply (arr){                           //Number of row and column needs to be equal
  var mMutRes = []
  for (var i = 0; i < arr.length ; i++)
    for(var j = 0; j<arr[0].length ; j++){
      if(arr[i][j] !== 0)
         arr[i][j] = 1                    // Remaining Text is converted to 1, has no class

    }
  var ss = SpreadsheetApp.getActive()
  var sss = ss.getSheetByName("Sheet3")
  sss.getRange(arr.length+5,2,arr.length,arr[0].length).setValues(arr)  //Set Value of unique pair to sheet 3
  for (var i = 0; i < arr.length ; i++){
     mMutRes[i] = []
    for(var j = 0; j<arr[0].length ; j++){
      var sumProd = 0
      for(var k = 0 ; k < arr.length ; k ++)
      {
        sumProd += (arr[k][j] * arr[i][k])

      }
      mMutRes[i][j] = sumProd

    }
  }
  return mMutRes 
}

function mostNoMeetings(shadowRel,headers){
  var UsedIndex = []
  var MaxColIndex = []
  var counter = 0
  var MeetingGroups = []
  for(var maxNo = shadowRel.length ; maxNo > 0 ; maxNo--) {        //Look for most repeated pair, max possible is the numbers of topics/meetings at same time
  var maxFound = false
  for (var i = 0 ; i < shadowRel.length; i++){
    for(var j= 0; j< shadowRel[0].length; j++){
      if(i != j && UsedIndex.indexOf(i) == -1 && UsedIndex.indexOf(j) == -1)   // Eliminate row / column corresponding to topics/Meetings already scheduled. 
        if(shadowRel[i][j] == maxNo){
          MaxColIndex[counter] = j
          counter++
          maxFound = true

        }
    }
    if(maxFound){
    var temp =  []
    temp.push(headers[i])
    for (var k in MaxColIndex){
      if(temp.length < maxNo)
       temp = temp.concat(headers[MaxColIndex[k]])
      else
       MaxColIndex.splice(k)
    }
    MaxColIndex[counter] = i
    MeetingGroups.push(temp)
    UsedIndex = UsedIndex.concat(MaxColIndex)
    //Logger.log(UsedIndex)
    MaxColIndex = []
    counter = 0
    maxFound = false
    }
   }
  }
  // Incase any are remaining meetings that didnt form pairs which have to be held independently
  for ( i = 0 ; i < shadowRel.length; i++){
    if(i != j && UsedIndex.indexOf(i) == -1 && UsedIndex.indexOf(j) == -1){
     MeetingGroups.push(headers[i]) 
    }
  }

  return MeetingGroups
}

最后，确保您的数据在工作表 2 中，而工作表 3 为空，将上述矩阵和相乘矩阵的输出发布到工作表 3，以直观地表示发生的情况。

希望对您有所帮助!