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.

Long story short, I really did not find anything (javascript or ruby) that fit the bill, so I was stuck having to come up with my own.  It ended up being pretty simplistic once it was all said an done as most of the work is just merging the arrays together. I decided to write this in javascript for a couple reasons – 1) it was much easier (and hence faster) since I am much more familiar with actionscript than ruby, and 2) I wanted a simple way to update the results on the page without having to write all of the rails code necessary to achieve the same results. The downside to having this as pure javascript is that it is client-side intensive once you increase the number of names included.

Let me start with an example of what I’m talking about:

// Given an array [0,1,2,3], generate all permutations for a set of 2 numbers
     // [0,1], [0,2], [0,3], [0,4], [1,0], [1,2]...[3,2]
// Generate all permutations for a set of 3
     // [0,1,2], [0,1,3], [0,2,1], [0,2,3], [0,3,1]...[3,2,1]

Here is the code I came up with:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

function generateCombinations(array, r, callback) {
  var length = array.length;
  var results = [];
 
  for(var x = 0; x < length; x++)
  {
    var rows = recurse(array, x, 1, r);
 
    //mergeResults(results, rows);
    var rowslength = rows.length;
    for(var y = 0; y < rowslength; y++)
    {
      results.push(rows[y]);
    }
  }
 
  callback(results);
}
 
function recurse(array, index, level, r)
{
  var num = array.splice(index, 1);
  var row = [];
 
  for(var x = 0; x < array.length; x++)
  {
    if(level < r - 1)
    {
      var combo = mergeResults(num,recurse(array, x, level + 1, r));
      var combolength = combo.length;
      for(var y = 0; y < combolength; y++)
        row.push(combo[y]);
    }
    else
      row.push(num.concat(array[x]));
  }
 
  array.splice(index, 0, num);
 
  return row;
}
 
function mergeResults(target, source)
{
  var length = source.length;
  var results = [];
 
  for(var x = 0; x < length; x++)
  {
    results.push(target.concat(source[x]));
  }
 
  return results;
}
 
function generateButtonClick() {
    var n = ["one", "two", "three", "four", "five"];
    var r = parseInt(document.getElementById("howmany").value);
    var startswith = $('startswith').value;
    var contains = $('contains').value;
    var result = document.getElementById("namelist");
    result.innerHTML = "";
    generateCombinations(n, r, function(combo) {
      for(var x = 0; x < combo.length; x++)
      {
        var name = combo[x].join(" ");
 
        var li = new Element('ul').update(name);
 
        if(startswith != "")
        {
          if(combo[x][0] != startswith)
            li = null;
        }
 
        if(contains != "" && name.indexOf(contains) == -1)
        {
          li = null;
        }
 
        if(li != null)
          result.appendChild(li);
      }
    });
}

So, being that I was using this to generate baby name combinations, I added a couple filters that allowed us to see only the permutations that started with a selected name, or only those that contained a selected name, or a combination of the two.

Obviously there is lots of room for improvement, both in the algorithm and in the functionality provided. Being able to dynamically substitute spelling variations in the output or being able to mark a particular combination as liked for future retrieval would definitely be handy. I would like to go back (someday) and re-implement the algorithm in ruby and leverage the rails framework to perform the permutation calculations on the server-side.

Anyways, I hope someone can make use of this or improve upon it for future use.