**Introduction**

Consider the following problem: given a finite set of positive integers, arrange them so that the concatenation of their decimal representations is as small as possible. For example, given the numbers {1, 10, 12}, the arrangement (10, 1, 12) yields the minimum possible value 10112.

I saw a variant of this problem in a recent Reddit post, where it was presented as an “easy” programming challenge, referring in turn to a blog post by Santiago Valdarrama describing it as one of “Five programming problems every software engineer should be able to solve in 1 hour.”

I think the problem is interesting in that it *seems* simple and intuitive– and indeed it does have a solution with a relatively straightforward implementation– but there are also several “intuitive” approaches that *don’t* work… and even for the correct implementation, there is some subtlety involved in *proving* that it really works.

**Brute force**

First, the following Python 3 implementation simply tries all possible arrangements, returning the lexicographically smallest:

import itertools def min_cat(num_strs): return min(''.join(s) for s in itertools.permutations(num_strs))

(*Aside*: for convenience in the following discussion, all inputs are assumed to be a list of *strings* of decimal representations of positive integers, rather than the integers themselves. This lends some brevity to the code, without adding to or detracting from the complexity of the algorithms.)

This implementation works because every concatenated arrangement has the same length, so a lexicographic comparison is equivalent to comparing the corresponding numeric values. It’s unacceptably inefficient, though, since we have to consider all possible arrangements of inputs.

**Sorting**

We can do better, by sorting the inputs in non-decreasing order, and concatenating the result. But this is where the problem gets tricky: what order relation should we use?

We can’t just use the natural ordering on the integers; using the same earlier example, the sorted arrangement (1, 10, 12) yields 11012, which is larger than the minimum 10112. Similarly, the sorted arrangement (2, 11) yields 211, which is larger than the minimum 112.

We can’t use the natural lexicographic ordering on strings, either; the initial example (1, 10, 12) fails again here.

The complexity arises because the numbers in a given input set may have different lengths, i.e. numbers of digits. If all of the numbers were guaranteed to have the same number of digits, then the numeric and lexicographic orderings are the *same*, and both yield the correct solution. Several users in the Reddit thread, and even Valdarrama, propose “padding” each input in various ways before sorting to address this, but this is also tricky to get right. For example, how should the inputs {12, 121} be padded so that a natural lexicographic ordering yields the correct minimum value 12112?

There *is* a way to do this, which I’ll leave as an exercise for the reader. Instead, consider the following solution (still Python 3):

import functools def cmp(x, y): return int(x + y) - int(y + x) def min_cat(num_strs): return ''.join(sorted(num_strs, key=functools.cmp_to_key(cmp)))

There are several interesting things going on here. First, a Python-specific wrinkle: we need to specify the order relation by which to sort. This actually would have looked slightly *simpler* in the older Python 2.7, where you could specify a binary comparison function directly. In Python 3, you can only provide a unary key function to apply to each element in the list, and sort by that. It’s an interesting exercise in itself to work out how to “convert” a comparison function into the corresponding key function; here we lean on the built-in `functools.cmp_to_key`

to do it for us. (This idea of specifying an order relation by a natural comparison without a corresponding natural key has been discussed here before, in the context of Reddit’s comment ranking algorithm.)

Second, recall that the input `num_strs`

is a list of *strings*, not integers, so in the implementation of the comparison `cmp(x, y)`

, the arguments are strings, and the addition operators are concatenation. The comparison function returns a negative value if the concatenation , interpreted as an integer, is less than , zero if they are equal, or a positive value if is greater than . The intended effect is to sort according to the relation defined as .

**It works… but should it?**

This implementation has a nice intuitive justification: suppose that the entire input list contained just two strings and . Then the comparison function effectively realizes the “brute force” evaluation of the two possible arrangements and .

However, that same intuitive reasoning becomes dangerous as soon as we consider input lists with more than two elements. That comparison function should bother us, for several reasons:

First, it’s not obvious that the resulting sorted ordering is even *well-defined*. That is, is the order relation a strict weak ordering of the set of (decimal string representations of) positive integers? It certainly isn’t a *total* ordering, since distinct values can compare as “equal:” for example, consider (1, 11), or (123, 123123), etc.

Second, even assuming the comparison function *does* realize a strict weak ordering (we’ll prove this shortly), that ordering has some interesting properties. For example, unlike the natural ordering on the positive integers, there is no smallest element. That is, for any , we can always find another strictly lesser (as a simple example, note that , e.g., ). Also unlike the natural ordering on the positive integers, this ordering is dense; given any pair , we can always find a third value in between, i.e., .

Finally, and perhaps most disturbingly, observe that a swap-based sorting algorithm will not necessarily make “monotonic” progress toward the solution: swapping elements that are “out of order” in terms of the comparison function may not always improve the overall situation. For example, consider the partially-sorted list (12, 345, 1), whose concatenation yields 123451. The comparison function indicates that 12 and 1 are “out of order” (121>112), but swapping them makes things worse: the concatenation of (1, 345, 12) yields the larger value 134512.

**Proof of correctness**

Given all of this perhaps non-intuitive weirdness, it seems worth being more rigorous in proving that the above implementation actually does work. We do this in two steps:

**Theorem 1**: The relation defined by the comparison function `cmp`

is a strict weak ordering.

*Proof*: Irreflexivity follows from the definition. To show transitivity, let be positive integers with digits, respectively, with and . Then

and

Thus,

i.e., . Incomparability of and corresponds to ; this is an equivalence relation, with reflexivity and symmetry following from the definition, and transitivity shown exactly as above (with equality in place of inequality).

**Theorem 2**: Concatenating positive integers sorted by yields the minimum value among all possible arrangements.

*Proof*: Let be the concatenation of an arrangement of positive integers with minimum value, and suppose that it is not ordered by , i.e., for some . Then the concatenation is strictly smaller, a contradiction.

(Note that this argument is only “simple” because and are *adjacent*. As mentioned above, swapping non-adjacent elements that are out of order may not in general decrease the overall value.)

I don’t understand the proof for theorem 1, the expression after “thus.” I understand how it’s constructed, but how does that prove x ≺ z?

You’re right, this skips some non-trivial additional transformation needed to get to the finish line. I have updated the post to include these steps, hopefully this clarifies.

>For example, how should the inputs {12, 121} be padded so that a natural lexicographic ordering yields the correct minimum value 12112?

>There is a way to do this, which I’ll leave as an exercise for the reader.

I’m not sure it is as simple as it appears. Can you point out the correct padding?

Given strings x and y, most of the post focuses on the order relation x(<)y defined by xy<yx, i.e., does x concatenated with y come lexicographically before y concatenated with x?

Another "padded" ordering that works is defined by xxx…<yyy…, where we concatenate "enough" copies of both x and y so that the resulting strings have the same length, so that we can compare them lexicographically. In the example where x=12 and y=121, we compare (12)(12)(12)=121212 with (121)(121)=121121.

Then there are two interesting observations: (1) this ordering is *equivalent* to the xy<yx ordering discussed in the post, and (2) in implementation of this "padded" ordering, you don't have to actually concatenate copies; you can effectively just start comparing x and y elementwise from the left, wrapping around each cyclically as necessary, until corresponding characters differ.