Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need an algorithm which has the following property:

  • $f(x)$ will lie between $[a, b]$ (both integers) when $x$ is an element of $[a, b]$

  • There should be no collisions i.e. $f(x)$ should always be unique for unique $x$

The simplest function is $f(x) = x$. Can there be a family of such functions? How can I mathematically represent it?

In simple words - I want a function which can distribute all numbers between $[a,b]$ in the output set which is also $[a,b]$.

Sorry I am not a mathematician :) So this is the best I can do to express what I need :)

share|improve this question
    
If $[a,b]$ contains $n$ numbers, there are $n!$ such functions, called permutations. –  Hagen von Eitzen Jan 12 '13 at 14:06
    
How do I get the inverse function family which can give me these permutations? –  MathOldTimer Jan 12 '13 at 14:10
    
The inverse of a premutation is also a permutation. A generic way to describe apermutation is via a lookup table. –  Hagen von Eitzen Jan 12 '13 at 14:13
    
If $x$ is not necessarily an integer, then, taking $a=0$, $b=1$ for simplicity, $\{f_n:x\mapsto x^n\}$ is another family of functions satisfying your requirements. –  Eckhard Jan 12 '13 at 17:18

1 Answer 1

From the title of your question I surmise that you are thinking about functions $f$ mapping the set $\{a,a+1,a+2,\ldots, b\}$ one-one onto itself. We may as well assume that $S:=\{1,2,3,\ldots,n\}$ for some given natural number $n$.

Maps of this sort are called permutations of $S$; there are exactly $$n!:=n\cdot(n-1)\cdot(n-2)\cdot\ldots\cdot2\cdot 1$$ of them. Any such map can be obtained in the following way: Choose arbitrarily $f(1)\in S$; there are $n$ possibilities for this. Then choose arbitrarily $f(2)\in S\setminus \{f(1)\}$; there are $n-1$ choices left for this. And so on, until there remains a single element to pick as $f(n)$. The resulting $f$ can be encoded as a list $$\bigl(f(1),f(2),f(3),\ldots, f(n)\bigr)\tag{1}$$ containing $n$ different entries $f(k)\in \{1,2,3,\ldots,n\}$.

The set or family of all $f$ that can be constructed in this way is called the symmetric group on $S$, and is denoted by ${\cal S}_n$ (or similar).

If you need an algorithm that systematically produces all $n!$ lists $(1)$ of such $f\in{\cal S}_n$, let us know.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.