 <p>Duh! The solution is to add <code>interaction(... drop=T)</code>. I still don't fully understand why not having that breaks things though.</p> <pre><code># The original factor from interaction() had unused levels... str(df$label) # Factor w/ 12 levels "1.1","1.2","1.3",..: 3 7 6 8 10 8 2 2 5 5 # SOLUTION df$label &lt;- interaction(df$u,df$v, drop=T) str(df$label) # Factor w/ 7 levels "2.1","1.2","2.2",..: 5 6 3 7 4 7 2 2 1 1 rank(unique(df$label)) # [1] 5 6 3 7 4 2 1 </code></pre> <p>We will use that rank (shown above) to reorder the levels in-order-observed, before matching our vector against them as follows:</p> <pre><code># And now we get the desired result match(df$label, levels(df$label)[ rank(unique(df$label)) ] ) # [1] 1 2 3 4 5 4 6 6 7 7 </code></pre>