The wife and I have been having problems settling on baby names for our first child (coming any day now!), so I decided that I’d see if I couldn’t help out with a simple web app that would let us put in the names we are considering and spit out all of the possible permutations. After performing a modicum of research in to combination and permutation algorithms for both javascript and ruby (I decided the fastest way to get this done was with rails), I quickly realized that my problem wasn’t as simple as most of these algorithms made it out to be. See, I didn’t need all of the permutations of an array of size n, as that represented all of the names and not just the few that usually make up someones first and middle name(s).  What I needed was an algorithm that listed all of the permutations of an array for a given resulting array size without repetition. I remember finding a particular example that generated permutations in to power-sets, which I could have then just filtered out anything that didn’t match the power-set the user specified, however I can’t recall why that approach didn’t work out.
More >