Are you trying to encode strings from one alphabet with strings from another alphabet such that the resulting encoding is itself just as random as original string in some sense? I think the sense you're using is the frequency counts of n-grams? I suspect that such an encoding does not exist but perhaps you can preserve n+k-gram distributions assuming your input strings have a certain n-gram distribution. For instance you could have a = 0101, b = 1100, c = 1001 and that might be the sort of thing that could work. It's hard for me to say without much more work than I'm willing to put into this

@MohamadS. I'm asking about you're phrasing saying "the first half must be balanced", it isn't clear if you mean that w = ab where a is a balanced string and b is of the same length or if b is allowed to be any string at all as long as w is of even length.

When you say "first half" do you just mean that it has to have a prefix of length 100 or that the full length has to be exactly 200?

a "hit" occurs when either a read or a write (or both) occurs and the associated address range is inside of a cache line in cache already. A "cache hit" takes no time. A cache miss takes time. I believe it to be the case that a miss for a read or a write will be very close to the same on modern cores since either way they both move data from one layer up to one layer down.

Absolutely fantastic answer D.W.!! There is so much good info there. I wasn't able to type in the right words to find those but that's a perfect answer.

uh, I don't know what a half order is but any DAG induces a partial order by its transitive closure. The "induced graph" of a partial order is just the directed graph where an edge exists between any two nodes if the relation holds between those nodes. A tree is never the induced graph of a partial order unless its very small (size 0 to 2 I think).

In general sure. If it helps you can assume the induced graph is connected as a special case. I don't really expect the general case to be solvable in less than linear time in the size of the collection, you need extra structure I think to be more efficient. I'm interested in learning what special cases might be solvable using existing data structures.