James Pine Has A Blog

Jump to Comments

Every now and then it’s useful to challenge oneself, to grow, to stretch. A couple of months ago, a friend of mine noticed a McDonalds, Kentucky Fried Chicken and Arby’s within spitting distance of each other, a trifecta of sorts. Then came the eureka moment, where he envisioned combining a Big Mac, Double Down and Beef ‘n Cheddar into the greatest fast food sandwich imaginable.

The supplies (we put some fries into the sandwich for good measure).

The main ingredients, from left to right, Big Mac, Double Down, Beef ‘n Cheddar.

Assembly complete.

At this point, you might be wondering what nutritional value this behemoth contains, so I’ve compiled it below using the official Arby’s Menu, McDonalds Nutrition Facts and KFC Nutrition Information. The % daily values are based off of the US FDA Reference Daily Intake of a 2,000 calorie diet.

I was shocked, I figured I would at least be consuming 1,500 calories and more than 100% of the daily value in several categories. As it turns out, compared to the 10 Worst Restaurant Salads, this sandwich would rank 2nd by sodium, but only 5th by calories and 10th by total fat! In fact, with a bit less sodium I would consider the Beef ‘n Cheddar healthy. Percentage wise, it’s actually the protein content which is furthest from the norm.

An action shot.

Slow and steady.

My friend finished his sandwich quite a few minutes before I did. The final 5 bites or so were tough, but in the end I too prevailed. However, a part of me still felt empty inside…we had not come up with a good name for the creation. I thought some permutation of the words in the sandwich names would pop out as an obvious choice, but that didn’t happen. In the end I decided to write a script to generate all the permutations (leaving out the ‘n “word”) which left me with 6! (720) possibilities. My first version was recursive and looked like this (thanx Harry Terkelsen for pointing out my boneheaded use of append where I should have used insert):

#!/usr/bin/python

import sys

def permute(l):
  if len(l) == 2:
    original = list(l)
    l.reverse()
    return [original, l]

  accumulated_permutations = []
  for x in xrange(len(l)):
    element = l[0]
    permutations = permute(l[1:])
    for permutation in permutations:
      permutation.insert(x, element)
    accumulated_permutations.extend(permutations)

  return accumulated_permutations

def main(argv):
  name_permutations = permute(['big', 'mac', 'double', 'down', 'beef', 'cheddar'])
  for x in name_permutations:
    print ' '.join(x)

if __name__ == '__main__':
  main(sys.argv)

That certainly worked, but a part of me wasn’t happy with the algorithm. It created an awful lot of new lists and generated the entire result set in memory before returning. If I ever wanted to push myself and combine 5 sandwiches where each name was a bigram (permute 10 words) it would take my computer 23 seconds (and 600M+ of RAM) to generate all 10! combinations. With 6 sandwiches (12 words) after 21 minutes my computer had used up 8GB of RAM and still wasn’t finished. Clearly it would be better to create some sort of iterator or generator to yield permutations as needed. Even better would be to have a method of requesting ranges of permutations as I could then use multiple computers in parallel to generate them and merge the results at the end.

After some more thought I remembered reading about an interesting method of computing permutations based on patterns in Higher-Order Perl and after a little more tweaking I had a parallelizable set of functions:

#!/usr/bin/python

import sys


def nth_pattern(n, size):
  """Get the Nth pattern for a permutation of a given size."""
  pattern = []
  for i in xrange(1, size + 1):
    pattern.insert(0, n % i)
    n = n / i
  if n:
    return []
  else:
    return pattern


def pattern_to_permutation(pattern, items):
  """Generate a permutation of items based on the pattern."""
  items = items[:]
  r = []
  for x in pattern:
    r.append(items.pop(x))
  return r


def permute(items, start_n, end_n):
  """Generate the range of permutations of items between start_n and end_n."""
  size = len(items)
  while start_n < end_n:
     pattern = nth_pattern(start_n, size)
     if not pattern:
       break
     result = pattern_to_permutation(pattern, items)
     yield result 
    start_n += 1


def factorial(n):
  """Compute n!."""
  total  = 1
  while n > 1:
    total = total * n
    n -= 1
  return total


def main(argv):
  """Main driver which could be easily transformed into a MapReduce."""
  names = ['big', 'mac', 'double', 'down', 'beef', 'cheddar']
  num_permutations = factorial(len(names))
  num_machines = argv[1]  # Number of machines to use in parallel.
  end_n = 0
  for machine in xrange(num_machines):
    size = num_permutations / num_machines
    start_n = machine * size
    end_n = (machine + 1) * size
    # This would be an asynchronus  RPC if truely running in parallel.
    p = permute(names, start_n, end_n)

  # In case we have some leftover work
  if end_n < num_permutations:
   p = permute(names, end_n + 1, num_permutations)


if __name__ == '__main__':
  main(sys.argv)

The parallizeable version also lends itself to random permutation requests e.g. should I ever visit McDonalds, Kentucky Fried Chicken, Arby’s, Taco Bell, Burger King, Carl’s Jr. and In-N-Out:

names = ['big', 'mac', 'double', 'down', 'beef', 'cheddar', 'gordita', 'supreme', 'whopper', 'western', 'bacon', 'animal', 'style']
num_permutations = factorial(len(names))
x = random.randint(0, num_permutations)
p = permute(names, x, x + 1)[0]
for permutation in p:
  print permutation

I might order a: Double Bacon Down Whopper Gordita Mac Animal Big Cheddar Supreme Western Beef Style!