title: Assigning Groups based on Preference List (Take 3)
body: <p>This is the third iteration of a question that had started from a purely algorithmic point of view, and has now turned in to a desperate mission to find a code sample that I can understand.</p>
  
  <p>What I am trying to do is create <em>g</em> groups of a list of people, attempting to satisfy as many preferences as possible. Each person has given an unranked list of top <em>n</em> other people in the list that they would like to be assigned with. It (my program) needs to consider mutual requests as more influential that one-way, and should (hopefully) find something close to the optimal solution.</p>
  
  <p>I want some sort of a code sample (in, really, any C-based language or detailed pseudo-code) so that I can understand the required algorithms and write my program. After my first question, I have determined that this will probably require some sort of variant on the Stable Marriage Problem, but I have been unable to find a full example in either pseudo-code or an actual language that I can understand.</p>
  
  <p>I have asked previous questions about the algorithm <a href="https://cs.stackexchange.com/questions/14486/assigning-groups-based-on-preference-list-take-2?noredirect=1">HERE</a> and <a href="https://scicomp.stackexchange.com/questions/8534/assigning-groups-based-on-preference-list/8536?noredirect=1">HERE</a>, but have not come up with anything (I think it's due to the extremely low number of users on those SE forums). Now I am asking a question here, on the hope that the much higher view rate coupled with a programming oriented question will get me an answer.</p>
  
  <p>Yes, I do realize that questions like this have been asked before, but none are both applicable and answered.</p>
  
  <p>Does anyone know how I can do this?</p>
  
  <p>To add more detail (in response to comments):
  I have a list of people. For each person, I have a list of their top preferences of other people that only includes other people in the main list. No lists are sorted in any way. A name on a preference list means that the requester would like to be with the requested person. I am looking for a way to create a specified number of groups, each containing only people that I have on my main list. I want the groupings to incorporate the preference lists. It should try to put people in the same group if they both request each other in their lists. It should also incorporate requests where one person(person A, in this example) requests someone else (person B), but B does not request A. In this case, although it should still count the request, it should be counted as a lower priority to incorporate than a mutual request.</p>
  
  <p>EDIT:
  Again, as per request, here is a JS function that will (hopefully) help explain my goal:</p>
  
  <pre><code>/*
  Scores a possible grouping
  group would be an object, where the keys are names and the values are arrays of preferences. Ex:
  
      {
          "Person 1": ["Person 2"],
          "Person 2": ["Person 1"],
          "Person 3": ["Person 4"],
          "Person 4": ["Person 2"]
      }
  
  */
  function getGroupScore(group) {
      var totalPoints = 0;
  
      //Add a point for each request
      for (var person in group) {
          for (var request in group[person]) {
              if(request != undefined &amp;&amp; request.length &gt; 0)
                  totalPoints++;
          }
      }
  
      //Add two points for each two-way request
      for (var person in group) {
          for (var request in group[person]) {
              if (group[person][request] != undefined //String validation
                  &amp;&amp; group[person][request].length &gt; 0 //More string validation
                  &amp;&amp; group[group[person][request]] != undefined //Array validation
                  &amp;&amp; group[group[person][request]].indexOf(person) != -1) //Check mutual request
                      totalPoints += 2;
          }
      }
  
      return totalPoints;
  }
  
  /*
  Compares two possble groupings
  */
  function compareGroups(groupA, groupB) {
      var scoreA = getGroupScore(groupA),
          scoreB = getGroupScore(groupB);
  
      if (scoreA &gt; scoreB)
          return 1;
      else if (scoreA == ScoreB)
          return 0;
      else
          return -1;
  }
  </code></pre>