Create ordinal value from hierarchical path

Let's say I have a set of path-like structures:

A1 -> B1 -> C1
A1 -> B1 -> C2
A1 -> B2
A2
A3 -> B1
A4 -> B2 -> C3

Now, I want to create an ordinal value for each one of these paths so that they can be sorted, without knowing any information about any of the other paths in the set.

If you imagine the paths to represent something like XML nodes, then As would be root-level nodes, 开发者_Go百科Bs first children, etc. I want to sort by A first, then B, then C, etc. The paths have arbitrary depth and an arbitrary number of nodes at each level.

I've been banging my head around number manipulation for an hour or so now and haven't come up with anything elegant. Unfortunately, I'm also unsure of what terminology to use when searching for related problem domains to draw from.

Edit: It actually would be easy for me to get the total number of paths in the set and having that value available during calculation. I'm going to get back to the whiteboard with that in mind; thanks @rrenaud.

if you want to preserve the order, you really need to know some bounds on the branching factor, depth, or total number of entries in order to do this.

Proof by contradiction. Consider me, your evil adversary. Assume you come up with a numbering system that doesn't know a bound the total size, I'll ask you Number('A'), and then Number('B'). Then I'll take N = Number('B') - Number('A'), and ask you to to Number ('A', 1), ('A', 2), ... ('A', N + 1). Now you are screwed, you can't possibly give a consistent number to ('A', N + 1). You've run out of space if you've done the best job possible, giving each of the prior A's children consective numbers. If you haven't done the best possible job, you've already lost.

The representation you have there is a partial order. That is, not all elements are comparable. You are looking for a linerization of the partial order, (that is, a total order that contains this partial order). For instance, let's say we have A1 -> B1 A1 -> B2 I know from this informatino that A1 > B1 and A1 > B2 .. But I dont know anything about B1 and B2. So there are two possibilties. A1 -> B1 -> B2 or A1 -> B2 -> B1. The problem is also called Topological sorting, and it runs in O(n+m) n:number of nodes, m: edges.

Take these links: http://en.wikipedia.org/wiki/Linear_extension http://en.wikipedia.org/wiki/Topological_sorting