I built this little tool after listening to Waypoint Radio’s Kingdom Hearts Lore Reasons episodes. I must admit I have not played any of the Kingdom Hearts games but I could not help myself to put together yet another name generator!

A what name generator?

From my very limited understanding, members of Organization 13 in the Kingdom Hearts games have names formed from anagrams of their original names plus the letter X. As you might imagine, there are already a number of such generators out there, but they have a number of problems that I wanted to tackle:

1. They are non-deterministic.
2. They do not calculate all of the possible permutations.
3. They cannot guarantee “the best” generated names.

Normally, when putting together a name generator, these tend to be non-issues. Of course you want non-determinism to get different sets of names each time, a non-exhaustive subset of all possibilities for speed and practicality, and a spectrum of different quality names— that is, however you measure quality, you might desire some amount of deviation to add flavor and variety.

However, this particular type of name generator begs for, if not one best-and-final result, at least a sorted, scored list from which you can pick your favorite. Therefore, we must not only calculate all possible permutations of name+X, but also do our best to encourage the best results to rise to the top.

Permuting

I worked out this simple permutation algorithm by visualizing colored marbles being drawn from a bag. Not a great visual, mind you, seeing as we need the letters in a deterministic order each time and random drawing from bags best informs an entirely different class of algorithms, but I digress.

We begin by stepping through each letter and adding it to the results; then, before moving on to the next letter, we select the next letter and add it to every position of every previous result, and repeat this last step until all letters have been exhausted. As you can imagine, performance blows up quite exponentially with regards to the string size, and there is a lot of wasted sub-anagram results which we don’t use but could conceivably be useful in a different context.

Say you have a name “ABC” and you want to find all possible permutations. Step through every letter and add it first to the list of results, then to every position of every existing result on the list. The sequence will look like this:

A   // The list is empty at this point, so just add A and done.
B   // Onto B. First add it to the list.
BA  // Then add it to every position of every item on the list.
AB
C   // Onto C.
CA  // Add to every position of every item on the list.
AC
CB
BC
CBA // Finally we start building some actual results! 
BCA
BAC
CAB
ACB
ABC

There are a number of improvements that can be made to this algorithm if we only care about full anagrams. Firstly, you might’ve noticed that the results right before our final 3-letter results— all non-3-letter results with the letter C— don’t go on to later be built upon by other letters, and can therefore be omitted. Secondly, you might notice that the lone B is guaranteed to never “fill out” to full size. Generally speaking: existing results with length < i are guaranteed to never build up to a full length result, and therefore can be skipped. In practice, that means that:

1. The only letter that needs to be added by itself is the first one and
2. At every insertion step, only bother inserting into results that are of the largest size, which are the only ones that will end up yielding full-length anagrams.

The sequence therefore becomes:

A   // A is the only item added to the empty list.
BA  // B is operating upon the largest items on the list.
AB
CBA // C is operating only upon he largest items as well.
BCA
BAC
CAB
ACB
ABC

It might not seem like much for a 3-letter example, but given the nature of these exhaustive permutations, it can save you hundreds of thousands of useless results with 8 or 9-letter names!

Scoring

Now that we have a list of all possible permutations, we could just as well display them all to the user and allow them to choose their favorite. However, a little bit of creative scoring can go a long way. First, we deploy some basic safeguards to cull the worst options:

1. Don't even bother with "Xname" and "NameX". Boring, just cut them out.
2. Give a low score, but still allow, names with 4-non-y-consonant sequences.

Now the more interesting scoring work begins. The base scorer does the following:

Given a list of 1000+ common words and 1000+ common names, as well as all of the canon Organization XII names, of course, extract all substring fragments of a given length. For every position in the word being scored, compare the next letters of that length against the list of fragments— paying special attention to the first and last fragment— and give the word +1 point if the fragment is found, with additional points if the fragment is at the beginning or end. (It all sounds a lot more complicated than it is). Here's a very barebones example:

Let's say the blessed list of names and words is ["Steven", "Hello"]. For the scorer with length 3 (there are three separate scorers of length 3, 4, and 5 to capture both general and specific word structure), the following fragments are extracted:

Ste
tev
eve
ven
en.
Hel
ell
llo
lo.

The emphasized fragments, as you can see, capture the beginning of the word as well as the end with the added terminal character (which can be anything, really, but a "." seemed fitting).

Using these fragments, a name like "Heltevx" would receive +3 points for a beginning fragment "Hel", none for "elt", none for "lte", +1 for "tev", none for "evx", and none for "vx.", for a total of 4 points.

However, a name like Heltevx is not very good. We can expand our source words/names for scoring to naturally bury it as other better quality names rise to the top, or we can explicitly guard against what makes this name low quality: the "vx" terminal is awkward. To that end, we must put together an imperfect but good-enough list of low quality starting substrings and ending substrings to score negatively. These include awkward consonant combinations, such as "Xb" and "Bx", but allow the esoteric-but-plausible "Xh", for example.

That's pretty much it! All of these details might seem old hat to you if you're familiar with name generators, but I certainly hope they've cleared up some mysteries for you if you're not! Have a look at the generator in action and the source code on GitHub.