Writing JavaScript Permutation Functions

Let's say you're browsing a crowded outdoor market, and a wild-eyed man in a top hat waves you over. Standing behind a table with three cups in a straight line, he places a ball under the center cup and switches it with the cup to your left. He switches the right and left cups. The center cup with the right cup, the center with the left. It's too fast, you can't keep up. He says for $10, you can guess which cup the ball is under. If you guess correctly, you'll win $100.

You think you like those odds, but you're not sure. Luckily, you have your laptop and a WiFi signal. You open Chrome and enter the developer's tools to do some quick arithmetic in JavaScript.

const cups = ['left', 'center', 'right'];
let odds = 1 / cups.length;
let overUnder = 10 / 100;
console.log(odds > overUnder);

Your odds are greater than your over-under, so it's a good bet. You pay $10 and choose the center cup. No dice! Should've picked left. You can keep playing, but there's a catch. He'll double the prize money for the next round, but you have to guess correctly twice in a row. To sweeten the deal, you'll only have to pay $5. Figuring out your over-under for multiple rounds is a little trickier. With one round, there are exactly three possibilities: left, center, or right. But what about two? You express the results of each round as the item of an array. One possibility, where the ball is under the left cup both times, would look like this.

[left, left];

The second round could also result in center or right.

  [left, left]
  [left, center]
  [left, right]

Since you have to guess twice, the first round result is still unknown. It could be be right or center. So your list of potential outcomes looks like this:

  [left, left]
  [left, center]
  [left, right]
  [center, left]
  [center, center]
  [center, right]
  [right, left]
  [right, center]
  [right, right]

There are nine possibilities. You stand to win $200, and your total buy-in is $15 ($5 plus the original $10). So you consult your dev tools.

odds = 1 / 9;
overUnder = 15 / 200;
console.log(odds > overUnder);

The odds are still in your favor, but for how long? You can keep playing the game for $5 a round, and he'll keep doubling the prize money. But if you fail the second round, you'll have to guess correctly three times in a row. And four times if you fail the third round. At which round do the odds stack up too high?

To figure this out, you generate a permutation function that outputs the possible results over any given number of rounds. Permutation functions generate every possible variation of a set of elements. They are confusing and inefficient, with a factorial O(n!) time complexity. But they are the only way to obtain some data, like a word's complete list of anagrams. Or the total possible outcomes of a number of cup tricks. The skyrocketing time required to compute large, complex permutation is what keeps your passwords safe. It's possible to create so many variations that even a fast computer would take weeks or even years to exhaust all of them.

You create the shell of your flip-cup-outcomes-generating function.

function flipCup(tries) {
  const cups = ['left', 'center', 'right'];
  const outcomeList = [];
  let outcomes = [];
  /**
   * A BUNCH OF LOOPS
   * OR SOMETHING
   **/
  return outcomeList;
}

You eventually realize that no matter how you arrange a series of nested loops, they just won't get the job done. You have to use recursion. So you start building your recursive function to create each array of game results, starting with the base case.

function generate(outcome) {
    if (outcome.length === tries) {
      outcomeList.push(outcome);
      return;
    }
}

This function will only change the value of outcomes. It doesn't return anything, but you include a return statement anyway to terminate it. Now you have to loop through the array of possible outcomes, calling the function within the loop.

for (let i = 0; i < cups.length; i++) {
      outcomes = outcome.concat(cups[i]);
      generate(outcomes);
    }

You put the for-loop in your nested "generate" function, and you put "generate" in your parent flipCup function. Immediately invoke "generate" and return your completed array. Your final code looks like this.

function flipCup(tries) {
  const cups = ['left', 'center', 'right'];
  //parent array
  const outcomeList = [];
  //nested array
  let outcomes = [];
  function generate(outcome) {
    //base case
    if (outcome.length === tries) {
      outcomeList.push(outcome);
      return;
    }
    //loop through cups array, recursively call generate
    for (let i = 0; i < cups.length; i++) {
      outcomes = outcome.concat(cups[i]);
      generate(outcomes);
    }
  }
  generate(outcomes);
  return outcomeList;
}

You plug the number 3 into your function and get quite the avalanche of possibilities.

  [ 'left', 'left', 'left' ],
  [ 'left', 'left', 'center' ],
  [ 'left', 'left', 'right' ],
  [ 'left', 'center', 'left' ],
  [ 'left', 'center', 'center' ],
  [ 'left', 'center', 'right' ],
  [ 'left', 'right', 'left' ],
  [ 'left', 'right', 'center' ],
  [ 'left', 'right', 'right' ],
  [ 'center', 'left', 'left' ],
  [ 'center', 'left', 'center' ],
  [ 'center', 'left', 'right' ],
  [ 'center', 'center', 'left' ],
  [ 'center', 'center', 'center' ],
  [ 'center', 'center', 'right' ],
  [ 'center', 'right', 'left' ],
  [ 'center', 'right', 'center' ],
  [ 'center', 'right', 'right' ],
  [ 'right', 'left', 'left' ],
  [ 'right', 'left', 'center' ],
  [ 'right', 'left', 'right' ],
  [ 'right', 'center', 'left' ],
  [ 'right', 'center', 'center' ],
  [ 'right', 'center', 'right' ],
  [ 'right', 'right', 'left' ],
  [ 'right', 'right', 'center' ],
  [ 'right', 'right', 'right' ]

Twenty-seven total. You consult your over-under algorithm again.

let odds = 1 / 27;
let overUnder = 20 / 300;
console.log(odds > overUnder);

And the over-under has already overtaken your odds. No matter how many times this swindler doubles the pot, it's still dwarfed by the exponential increase in possible results. You are trying to be careful with your money, so you choose not to play another round.

Conclusion:

• Permutations are taxing for both human and machine
• They have a factorial 0(n!) time complexity, which is bad
• Understand them, but avoid them if you can
• To find the total number of permutations, without the full list, you could write a function that returns 3 raised to the power of n.
• Don't give your money to shady carnival barkers