Secret Santa pair allocator in JavaScript I have a Secret-Santa gift swap with my family and we always forget who we had last year and never find time to do it so I wanted to create a simple web app to manage the whole thing. What I'm looking for is a critique on my code. Could it use more built-in JavaScript functions? How's my style?



//get people from database
var people = [{name: 'TestName', spouse: 'TestNameSpouse', current: '', past: ['Dad']},
  { name: 'TestNameSpouse', spouse: 'TestName', current: '', past: ['Mom']},
  { name: 'Mom', spouse: 'Dad', current: '', past: ['TestName']}, 
  {name: 'Dad',spouse: 'Mom',current: '',past: ['SisterInLaw']},
  {name: 'Brother',spouse: 'SisterInLaw',current: '',past: ['TestNameSpouse']},
  {name: 'SisterInLaw',spouse: 'Brother',current: '',past: ['Dad']}
];

const setCurrentToBlank = (people) =&gt; people.forEach((person) =&gt; person.current = '');
const verifyGiftPartners = (people) =&gt; people.every((person) =&gt; person.current);

//Knuth shuffle
var shuffle = function shuffle(array) {
  var currentIndex = array.length,
    temporaryValue,
    randomIndex;

  // While there remain elements to shuffle...
  while (0 !== currentIndex) {
    // Pick a remaining element...
    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex -= 1;

    // And swap it with the current element.
    temporaryValue = array[currentIndex];
    array[currentIndex] = array[randomIndex];
    array[randomIndex] = temporaryValue;
  }
};
var assignGiftPartners = function(people) {
  var peopleLeftToAssign = people.map(person =&gt; person.name);

  people.forEach(function(person) {
    var choices = peopleLeftToAssign.filter(function(personToAssign) {
      return (
        personToAssign != person.name &amp;&amp;
        personToAssign != person.spouse &amp;&amp;
        person.past.indexOf(personToAssign) === -1
      );
    });
    shuffle(choices);
    person.current = choices[0];
    var index = peopleLeftToAssign.indexOf(choices[0]);
    peopleLeftToAssign.splice(index, 1);
  });
};

var allAssigned = false;
var loopCount = 0;
while (!allAssigned) {
  assignGiftPartners(people);
  allAssigned = verifyGiftPartners(people);
  //exit loop if going too long
  if (loopCount &gt; 50) {
    throw 'Something went wrong with the assignment';
  }
  if (!allAssigned) {
    setCurrentToBlank(people);
  }
}

//save choices into database
console.log(people);




Also, I realize that in a year or so we'd have to repeat people, so would it be good to limit the past size to family size - 1?
This is not a review of the coding style and syntax, but of the algorithm used. 

Permutations and randomised rule based selection.

A random search for a set of permutations is never a good method, especially if the set of previous results reduce the size of the set of valid permutations for the next set.

Random solution guessing

Your problem is finding one of a set of solutions. There are only a finite set of possible solutions. 

Your code uses a random guess method. 

Each iteration you randomly guess a possible combination then test its validity. Because the set of valid solutions gets smaller each year, your code needs to make more guesses as the number of valid solutions gets smaller but the set you are guessing in remains the same size.

This method also has been limited (to 50) and thus you could always have a chance of not finding a solution. For the first year there is a relatively small chance of not finding a solution, but this grows quickly. In three years you will need to (on average) run the code 5 times to find a solution. 

Also the limit you must surely have seen is that after 4 years there are no more possible solutions, as everyone has given to everyone. This should be obvious from the code as well, but it still tries to guess a solution where there is none.

There is no need for the code to throw an error. The solutions are known and fixed, so there is no need to guess.

Systematic solution computation.

To do this effectively you need to know the set of all valid solutions. Once you have that set you just randomly select one. There is no need to search for valid solutions as you are only selecting from known valid values.

Pre-computation of the set of valid solutions has a limit, as the possible number of solutions quickly grows with the complexity of a solution. For 6 people there are 80 solutions that are valid, for 10 people that is approaching a million. For 20 people you need to start applying some serious optimisation and storage compression to use this method.

Abstraction

If you compute them systematically and hold them as an abstracted data set, e.g. each person is a letter A,B,C,D,E,F that identifies them both as an entry in the data struc and a position in the abstracted data, e.g. "A" is 1st person in a solution string and the first person in the people array. A solution for a particular year is a string e.g. "CDEFAB" which means person A gives to C, person B gives to D, C to E and so on.

If you ignore the previous year the possible solutions are only 80.

Computing permutations.

For your data the following is all valid solutions.

var allValidSolutions = "DCFEBA,DCFEAB,DCEFBA,DCEFAB,ECFADB,ECFABD,ECFBDA,ECFBAD,ECAFDB,ECAFBD,ECBFDA,ECBFAD,FCEADB,FCEABD,FCEBDA,FCEBAD,FCAEDB,FCAEBD,FCBEDA,FCBEAD,CDFEBA,CDFEAB,CDEFBA,CDEFAB,EDFACB,EDFABC,EDFBCA,EDFBAC,EDAFCB,EDAFBC,EDBFCA,EDBFAC,FDEACB,FDEABC,FDEBCA,FDEBAC,FDAECB,FDAEBC,FDBECA,FDBEAC,CEFADB,CEFABD,CEFBDA,CEFBAD,CEAFDB,CEAFBD,CEBFDA,CEBFAD,DEFACB,DEFABC,DEFBCA,DEFBAC,DEAFCB,DEAFBC,DEBFCA,DEBFAC,FEBADC,FEBACD,FEABDC,FEABCD,CFEADB,CFEABD,CFEBDA,CFEBAD,CFAEDB,CFAEBD,CFBEDA,CFBEAD,DFEACB,DFEABC,DFEBCA,DFEBAC,DFAECB,DFAEBC,DFBECA,DFBEAC,EFBADC,EFBACD,EFABDC,EFABCD".split(",");


This was created with the following code. Note this is a brute force method. You should do some research into optimal methods if you need to include more than a dozen people.

function permutations2Of(chars) {
    var i,j;
    const count = chars.length;
    const sets = [];
    for (i = 0; i &lt; count; i ++) {
        for (j = 0; j &lt; count; j ++) {
            if (j !== i) { sets.push(chars[j] + chars[i]) }
        }
    }
    return sets;
}
function isSetValid(set, ofSet) {
    var i = 0;
    while (i &lt; ofSet.length) {
        if (set.indexOf(ofSet[i ++]) === -1) { return false }
    }
    return true;
}
function findUnique(arr, ofSet, result = [], index = 0, current = "") {
    var i;
    const testSet = index === arr.length - 1; 
    for (i = 0;  i &lt; arr[index].length; i ++)  {
        const aSet = current + arr[index][i];
        if (testSet) {
            if (isSetValid(aSet, ofSet)) { result.push(aSet) }
        } else {
            result = findUnique(arr, ofSet, result, index + 1, aSet);
        }
    }
    return result;
}
const AB = permutations2Of("CDEF");
const CD = permutations2Of("ABEF");
const EF = permutations2Of("ABCD");
const combos = findUnique([AB, CD, EF], "ABCDEF");


This is based on the smallest unit being a couple (e.g. AB is the first and second person, and they can give only to persons "CDEF")

It calculates all the possible permutations for each couple and then calculates all the possible permutations for all couples.

The  function findUnique uses recursion to create all possible solutions and then calls the function isValidSet to test if the solution should be kept.

The set of solutions should only be calculated once; once computed it can be retrieved from a data store and filtered when there is a need for extra rules to be applied - e.g. last years results.

Random solution without the guesswork.

Now it is very easy to find the first years arrangement.

var secretSantas = combos[Math.random() * combos.length | 0];


And convert to your data:

const baseCode = "A".charCodeAt(0);
secretSantas.split("").forEach((id, index) =&gt; {
    const personIndex = id.charCodeAt(0) - baseCode;
    people[index].current = people[personIndex];
});


Additional rules.

The above does not consider the previous year's gifts, but that can be stored as the abstracted string e.g. "DEFGAB". As there are only 4 people for each person to give to there are only 4 years before you are forced to repeat. If you limit the repeat only to 4 years then after the 3rd year everyone will know who is giving to who (if anybody bothered to keep track that is).

So the better rule is to just not repeat two years. You can't give to the person you gave to last year.

Then you can use a filter on the combos array to eliminate any invalid combination due to previous years results.

const lastYearsCombo = "CDEFAB".split("");
const comboFiltered = combos.filter(combo =&gt; {
     for (var i = 0; i &lt; lastYearsCombo.length; i++) {
         if (combo[i] === lastYearsCombo[i]) { return false }
     }
     return true;
});


comboFiltered will only have 17 possible combinations as the rest have been eliminated due to the previous year. The random selection is still the same.

var secretSantas = comboFiltered[Math.random() * comboFiltered.length | 0];