3
$\begingroup$

First off, I apologize if this is the wrong board. I'm a heavy StackOverflow user, and this is technically a programming question (or at least serves programming use), but I find it to be based moreso in math.

I have two sets of sequential integers that relate to each other, for the sake of example, defined as such:

Set A: [1..50] Set B: [1..150] 

I need to generate a third set from a combination of these two sets, with unique values. All integers from Set A must be programmatically paired with all integers from Set B to create Set C, which will contain unique integers. Jumping right into it, I thought "Well, just add the two to together!" I found quickly that such an idea wasn't even close to feasible.

Set A   Set B   Set C -----   -----   ----- 1       1       2 1       2       3 * 1       3       4 * 2       1       3 * 2       2       4 * 2       3       5  *Non-unique Values 

Multiplication didn't go so well either...

Set A   Set B   Set C -----   -----   ----- 1       1       1 1       2       2 * 1       3       3  2       1       2 * 2       2       4  2       3       6  *Non-unique Values 

So I'm looking for an operator or small formula to put between Set A and Set B to generate a unique, integral Set C.

EDIT

Both sets will have values added to them over time, so I need a solution that could handle an infinitely large Set A and Set B

  • 0
    I'm apparently not smart enough to have posted this here... :) I'm sure your answers are right, but I have no idea what they mean2012-06-15

4 Answers 4

2

How about just $ c = 150a + b$? Or $c=150(a-1)+b$ if you want it to be $1$-based.

(From a coding point of view, that's how indexing into packed multidimensional arrays work).


Edit after question was updated: If both of your sets are effectively all of $\mathbb N$, you can use something like $ c = \frac{(a+b-1)(a+b-2)}{2} + a $ which assumes the lowest possible value for $a$ and $b$ is $1$. If the value sets are $0$-based, use $ \tag{*} c = \frac{(a+b)(a+b+1)}{2} + a $ If $a$ and/or $b$ can be negative, first map them to 0-based ones using, for example, $ x\mapsto\begin{cases} 2x & \text{if }x\ge 0 \\ -1-2x & \text{if } x < 0\end{cases} $ and then use $(\text{*})$.

  • 0
    answer updated.2012-06-15
2

Any bijection from $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ will work. Or, for the purposes of finding sources on the internet, the slightly modified version: Any bijection from $\mathbb{Q}\to \mathbb{N}$ will work, where $a $ from Set A and $b$ from Set B is associated to the natural number that corresponds to $a/b \in \mathbb{Q}$ in the bijection.

  • 0
    I thought as much :-)2012-06-15
2

Here are some other possible solutions:

  • $c = 2^a 3^b$ (results in a very large $c$)

  • Write $a,b$ in binary, and interleave the bits (or bytes, or larger chunks)

  • Consider the complex integer $a+ib$ and express it in base $2i$

  • Express $a,b$ in binary-coded decimal and concatenate them, separated by some nibble such as F which cannot appear in BCD

Of course, in most cases, the right solution for a program would be for the elements of set C not to be integers, but some aggregate type: in C, something like struct { int a,b; }; in C++, pair; in Perl, a list (or perhaps the string "\$a,\$b"); et cetera.

0

Each integer has a sequence representation derived from its prime factorization, e.g., $ F(15) = F(2^0 3^1 5^1) = [0,1,1,...]. $ Interleave the representations of $a$ and $b$, then convert back to an integer, to obtain a unique integer associated with $(a,b)$. $ F(32) = F(2^5) = [5,...]. $ $ [0,1,1,...] \oplus [5,...] = [0,5,1,0,1,...]. $ $ F^{-1}(F(15)\oplus F(32))=F^{-1}([0,5,1,0,1,...])=2^0 3^5 5^1 7^0 11^1=13365. $

  • 0
    This is _true_, but since the OP was looking for something that can be implemented in practice and factoring is (thought to be) hard, I don't think it is the solution for him.2012-06-16