Mapping Two Continuous Sorted Integer Sets onto One Integer Set

Question

I have an algorithms problem you should help me out with: I am trying to map two continuous sorted integer sets (with potentially differing number of items) to a single continuous sorted integer set preserving linear spacing.

e.g. A: {1,2,3} B: {1,2,3,4} could map onto C: {1,2,3,4,5,6,7} by A: {1->1, 2->4, 3->7} and B: {1->1, 2->3, 3->5, 4->7}

It's pretty each to do these by hand, but I'm having trouble generalizing.

Decomposing the problems, I need to find (1) the number of buckets in the output set and (2) the input -> output mapping

My solution provided here:

// There are LCM(|A|-1,|B|-1)+1 buckets in output C

int numBuckets = LCM( A.Count()-1, B.Count()-1 ) + 1;

// Map elements in A to buckets in output C

for (int i = 0; i < A.Count(); i++)
{ mapping.Add(A.ElementAt(i), (i*((numBuckets - 1)/(A.Count() - 1))).ToString()); }

Answer 1

Suppose the size of set C is |C| = Nc and for set A, |A| = Na. Then, if you want to map A to C, let the first elements map to each other and then skip elements by

floor( (Nc-1)/(Na-1) )