# Thread: Unique representation of N integers randomly chosen out of a set of M (N<M) numbers

1. ## Unique representation of N integers randomly chosen out of a set of M (N<M) numbers

Is it possible to uniquely represent N integers randomly selected out of a larger set of M integers? For example, if M = {1,2,3,...,200} and N = 12, is it possible to map any 12 numbers randomly selected out of M into the set K = {1,2,3...,12}?
In other words, if I have 200 devices with IDs in the range of 1 to 200, and I randomly grab 12 devices out of the lot, is there an algorithm which will allow each device to INDEPENDENTLY change its ID to a UNIQUE number from the set {1,2,3,...,12}?
Note: INDEPENDENTLY means the devices dont need to communicate with other devices or with some central processing unit in order to solve the problem, and UNIQUE means there are no clashes between the new IDs.
Intuitively it seems that there's no way to uniquely reduce 200 numbers into 12. However, on the other hand, knowing that there's a unique prime factorization for every integer, makes you wonder if there is a way to map the unique vector of primes (for each integer) into a unique number in the reduced set.
Thanks

2. ## Creating function to map set {1,2,...N} to randomly chosen set of N integers.

It's not necessary to specify an algebraic or analytic formula to define the function which maps the integers {1,2,3...N} onto the N integers chosen at random,
from a larger set of integers.

For example, recently I wrote an formula in Microsoft Excel that mapped one set of names into another set of names. I used the vlookup function in Excel to do this.

For example suppose you choose randomly, the numbers [123,2,49,6,11,22,199]
and want a function that uniquely assigns them to [1,2,3,4,5,6,7].

Then you simply name and define your function to do exactly that.

RF = 123
RF = 2
RF = 49
RF = 6
RF = 11
RF = 22
RF = 199

Kermit Rose

3. Originally Posted by Arie Is it possible to uniquely represent N integers randomly selected out of a larger set of M integers? For example, if M = {1,2,3,...,200} and N = 12, is it possible to map any 12 numbers randomly selected out of M into the set K = {1,2,3...,12}?
In other words, if I have 200 devices with IDs in the range of 1 to 200, and I randomly grab 12 devices out of the lot, is there an algorithm which will allow each device to INDEPENDENTLY change its ID to a UNIQUE number from the set {1,2,3,...,12}?
Note: INDEPENDENTLY means the devices don’t need to communicate with other devices or with some central processing unit in order to solve the problem, and UNIQUE means there are no clashes between the new IDs.
Intuitively it seems that there's no way to uniquely reduce 200 numbers into 12. However, on the other hand, knowing that there's a unique prime factorization for every integer, makes you wonder if there is a way to map the unique vector of primes (for each integer) into a unique number in the reduced set.
Thanks
The way you're asking the question, the answer is obviously no, there is no injective function from M to K, when M and K are finite sets with |M| > |K|. Maybe you should think more carefully what you are asking. Is it possible to have a solution to your problem when M = {1,2,3} and K = {1,2}? If so, then you're not asking the question you mean to ask. This is my opinion.

(Edit: silly typo.)

4. To Kermit1941: Thanks for the reply, but it doesn't answer my question - perhaps I need to clarify. What I'm after is:

"Given any number from the (larger) set M, determine the index of its mapped representative in set N."

I.e., in your example, if you are given the number 49, can you figure out that the index in the RF array would be 3?

That is the meaning of the requirement for the algorithm to be INDEPENDENT - i.e. I need the algorithm of determining the target (mapped) integer in set N to be independent of any knowledge about other chosen numbers.

Arie

5. Originally Posted by undefined Maybe you should think more carefully what you are asking. Is it possible to have a solution to your problem when M = {1,2,3} and K = {1,2}?

(Edit: silly typo.)
You are probably right, but I didn't get your altered question - could you please explain.

6. Originally Posted by Arie You are probably right, but I didn't get your altered question - could you please explain.
Well when we have sets as small as M = {1,2,3} and K = {1,2}, it's easy to list out all possibilities exhaustively. So, there are only 8 functions from M to K, they are

{(1,1),(2,1),(3,1)}
{(1,1),(2,1),(3,2)}
{(1,1),(2,2),(3,1)}
{(1,1),(2,2),(3,2)}
{(1,2),(2,1),(3,1)}
{(1,2),(2,1),(3,2)}
{(1,2),(2,2),(3,1)}
{(1,2),(2,2),(3,2)}

And none of these work.

But I was asking because I wasn't sure if you had asked the question properly. If you could produce a solution to this small case, then it would act as an example that we could use to figure out what you're really asking.

7. Originally Posted by undefined But I was asking because I wasn't sure if you had asked the question properly. If you could produce a solution to this small case, then it would act as an example that we could use to figure out what you're really asking.
The real-world problem I am trying to solve is the one I mentioned in my original question:"If I have 200 devices with IDs in the range of 1 to 200, and I randomly grab 12 devices out of the lot, is there an algorithm which will allow each device to INDEPENDENTLY (= autonomously) change its (own) ID to a UNIQUE number from the set {1,2,3,...,12}?". On the face of it it's impossible, but thought there might be perhaps some clever way forward.

8. Originally Posted by Arie The real-world problem I am trying to solve is the one I mentioned in my original question:"If I have 200 devices with IDs in the range of 1 to 200, and I randomly grab 12 devices out of the lot, is there an algorithm which will allow each device to INDEPENDENTLY (= autonomously) change its (own) ID to a UNIQUE number from the set {1,2,3,...,12}?". On the face of it it's impossible, but thought there might be perhaps some clever way forward.
The answer is no.

EDIT: You can read about the pidgeonhole principle, but in all honesty, it should be obvious from the start.

#### Search Tags

chosen, integers, n<m, numbers, randomly, representation, set, unique 