Solved

I need simple one-to-one function

Posted on 2004-04-11
14
205 Views
Last Modified: 2010-04-17
Hi, I have a simple question in calculus:

Given a set of different integers A, each integer in range from 1 to 5000. It may be assumed that the set size won't be more than 50 (ie: |A|<=50).
I need a one-to-one function f that takes set A and returns an integer. (f: {..} --> R)
So for any A!=B => f(A)!=f(B) (!= stand for not equal). Of course, since A is a set, the order of integers doesn't matter, so A={1,2,3} identical to B={3,1,2}.

I'm sure there are a lot of simple functions that do the job, and functions with only primitive operators such as +,-,*,/ will be preffered.

Thanks in advance.

0
Comment
Question by:alex130
  • 5
  • 3
  • 2
  • +2
14 Comments
 
LVL 12

Accepted Solution

by:
venkateshwarr earned 75 total points
ID: 10800221
Hi alex130,

You are talking about arrays.
if you define an array as

int f[100];

f(1)=5;

then this is a  one-to-one mapping.


Cheers!
venkat.
0
 
LVL 27

Assisted Solution

by:Dabas
Dabas earned 75 total points
ID: 10800226
Hi alex130:
The easiest way would be to multiply each integer by 2^i where i is the position of the integer inside the set.
^ = to the power of.
The elements of the set will have to be sorted first.

With your {1,2,3) example, the function would be:

2^0 * 1 + 2^1 * 2 + 2^2 * 3 = 1 * 1 + 2 * 2 + 4 * 3 = 17


Dabas
0
 

Author Comment

by:alex130
ID: 10800320
Clarification for venkateshwarr:
There are a lot of different sets with specific size, for example if |A|=3 then there are more than 1.38^10 different sets. So I need a function which takes a set (which may be preseted as linked list of integers), checks list size and computes unique integer for the set according to numbers it contains. Then I store that computed integer, and if I get the same list again I can compare function output against already stored integers. So it saves time and space storage in time consuming applications.
0
Gigs: Get Your Project Delivered by an Expert

Select from freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely and get projects done right.

 

Author Comment

by:alex130
ID: 10800329
Comment for Dabas:
Your function is indeed gives one-to-one mapping, but it's not applicable since the numbers it produces are way beyond huge :)
Consider a set of 30 consequent integers: starting from 4950 to 4979. Even last computation 2^30 * 4979 is a huge number, not talking about the whole sum of previous 29.
I'm sorry, I've made a mistake when I told the function output need to be integer. It may (even should)  be double.
0
 

Author Comment

by:alex130
ID: 10800334
GENERAL CLARIFICATION:
Function output may (should) be double. :)

f: {..} --> R means that functino takes a set of integers and returns a real number.
0
 
LVL 27

Expert Comment

by:Dabas
ID: 10800341
alex130:
Huge number indeed.
But if you have 30 consequent integers, then the amount of possible distinct permutations is equally huge!


Dabas
0
 
LVL 84

Assisted Solution

by:ozo
ozo earned 75 total points
ID: 10800449
There are 5000!/(50!(5000-50!)) possible sets A, that requires over 400 bits to uniquely identify.
Would you settle for a hash function that was not one-to-one, but only rarely returned identical numbers
0
 
LVL 2

Assisted Solution

by:rqs
rqs earned 75 total points
ID: 10809923
the cardinality of the power set implied here is even bigger,
  50
-----          5000!
\         ----------------  =  2.30715956708335E+120       (the value is from a VB program I wrote)
/         K! (5000 - K)!
-----
K = 1

But this value can still fit in a VB double precision variable which can hold up to 1.79769313486232e+308.
So it's possible to find a function that maps each possible set of integers to a unique number value that
can fit in a double variable type. That is if there exists such a mapping function.

A possible scheme would be to number each set starting from 1:
f({1}) = 1; f({2}) = 2; ....... f({5000}) = 5000;
f({1,2}) = 5001; f({1,3}) = 5002; ...... f({1,5000}) = 9999;
f({2,3}) = 10000; f({2,4}) = 10001; .....f({2,5000}) = 14998;
and so on.... there's a pattern with numbers so there might be a possibility to create a function
from this pattern (most likely a spliced one).









0
 

Author Comment

by:alex130
ID: 10816469
Thoughts: Mapping with hash function and giving each set a unique integer number is either inefficient, space wasting and would take years to compute. It will be better to map to real numbers, using mathematical formula, depending on the set length.
For example consider the following function, I'm not sure that it's one-to-one but it's defenitely a start :)

Suppose A={x1,x2,..,xn}
f(A)=(x1)^(0.n) + (x2)^(0.n) + ... + (xn)^(0.n)   (if |A|=5 then 0.n=0.5)
Of course 0.2=0.20 so lets asume that if number after decimal point is multiple
of ten, then it's converted to 0.nnn (so 0.30 will be 0.333). (When set size bound is 99 of course).
0
 
LVL 27

Expert Comment

by:Dabas
ID: 10816614
alex130:
My BA in Maths happened nearly 30 years ago... Can you please explain what the notation 0.n stands for?

Dabas
0
 

Author Comment

by:alex130
ID: 10818025
to Dabas:
0.n stand for a double (Real) number.
for example if n=5 then it is simply 0.5 (1/2).
So if A={x1,x2,..,xn} then it has n elements (|A|=n) so i would raise each element in power of 0.n and sum results.
For example if A={2, 3004, 4443} then |A|=3 and
   f(A)=2^0.3 + 3004^0.3 + 4443^0.3=24.70499967
So far I haven't neither proven that this function is one-to-one nor found a contradictory exmple. But anyway, even if this function is one-to-one it is too slow because it involves raising in power operation which is a very complex one, especially when raising in non integer power.
If you can come up with another one-to-one function which uses only primitive operations (+-,/*) it would be great! :)
0
 
LVL 84

Expert Comment

by:ozo
ID: 10818451
if f(A) is truncated to a 64 bit float, it will not be one to one
0

Featured Post

Courses: Start Training Online With Pros, Today

Brush up on the basics or master the advanced techniques required to earn essential industry certifications, with Courses. Enroll in a course and start learning today. Training topics range from Android App Dev to the Xen Virtualization Platform.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Using YubiKey with REST API application 2 115
oracle query help 18 111
Scripting vs. Programming languages 25 165
Base1 Encode/Decode 3 77
This is about my first experience with programming Arduino.
Although it can be difficult to imagine, someday your child will have a career of his or her own. He or she will likely start a family, buy a home and start having their own children. So, while being a kid is still extremely important, it’s also …
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …

785 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question