# Bin arbitrary data using canonical ordering

I have two lists of words, nouns and verbs:

nouns = RandomWord["Noun", 10] // Sort
(* {"concrete", "curdling", "decoupage", "fairy", "hairline", "hick", "orchid", "referral", "sleepwear", "snorkel"} *)

verbs = RandomWord["Verb", 100];


and I want to know how many elements of verbs come between each successive pair of nouns in alphabetical order. In other words, I want to construct a histogram, treating the elements of nouns as the boundaries of the bins.

If instead I had two lists of numbers, integers and reals, I could do this as follows:

integers = RandomInteger[{1, 100}, 10] // Sort;
reals = RandomReal[{1, 100}, 100];

BinCounts[reals, {integers}]
(* {17, 0, 15, 1, 1, 11, 2, 25, 11} *)


But this does not work with the words: BinCounts (and Histogram and related functions) will only accept a set of bin boundaries that are real numbers.

The best I can think of is

Function[v, SelectFirst[nouns, OrderedQ[{v, #}] &]] /@ verbs


but this seems very inefficient. Is there a way to use BinCounts to do this, or a more efficient (natural / neat) way to do it otherwise?

To clarify what I actually want to use this for, in case it's helpful: there is a (large) ordered set $\mathfrak{S}$ of elements (all words) and I have generated a subset $\mathfrak{T}$ (nouns) whose elements are (I believe) approximately uniformly sampled from $\mathfrak{S}$. To test this, I have generated a new sample $\mathfrak{U}$ (verbs) and want to plot a histogram of $\mathfrak{U}$, using $\mathfrak{T}$ as the bin boundaries.

• binlists=DeleteCases[SplitBy[Sort[Join[nouns,verbs]], MemberQ[nouns,#]&] , {__?(MemberQ[nouns,#]&)}] and bincounts = Length/@binlists? – kglr Jun 19 '18 at 8:38

Maybe

ordering = Ordering[Join[nouns, verbs]];
DeleteCases[
Total[
Split[
Join[
ConstantArray[0, Length[nouns]],
ConstantArray[1, Length[verbs]]
][[ordering]]
],
{2}],
0
]


does what you want?

An alternate way of writing it is

(DeleteCases[#, 0] &)@(Total[#, {2}] &)@Split@Join[
ConstantArray[0, Length[nouns]],
ConstantArray[1, Length[verbs]]
][[ordering]]


The key part here is

Join[
ConstantArray[0, Length[nouns]],
ConstantArray[1, Length[verbs]]
][[ordering]]


The output is a list of zeros and ones where each zero stands for a noun and each one stands for a verb in the ordered list Sort[Join[nouns,verbs]]. Split helps us to find runs of the same element and we can employ Total[#,{2}]& to count the ones in each run. In the end, we remove the "nouns" with DeleteCases[#,0]&.

• Thanks. I am now using Length /@ Cases[Join[Map[{False, #} &, nouns], Map[{True, #} &, verbs]] // SortBy[Last] // SplitBy[#, First] &, {{True, _} ..}], which is essentially the technique in your answer. – Stephen Powell Jun 20 '18 at 7:41
• You're welcome. Note that with nouns = RandomWord["Noun", 100000] // Sort; verbs = RandomWord["Verb", 1000000];, your method needs 4.41 seconds on my machine while mine needs 0.649584. I don't know how large your lists really are... – Henrik Schumacher Jun 20 '18 at 7:52

Why not just transforming the word into a number? This assumes all lowercase, English words with characters in CharacterRange["a", "z"] and of up to 23 characters (Max[StringLength@DictionaryLookup["*"]])

Word2Number[word_String] :=

• Thanks. This does indeed answer the question as posed. I have accepted Henrik's answer because it is somewhat more general. This answer works in any case where one can define a "hash" function (Word2Number) that preserves the order used by Sort. – Stephen Powell Jun 20 '18 at 7:33