Suppose i have a random permutation of 0,1,...., N-1. Now if i want to get the identity mapping from this can i do anything better than sorting?? I mean, sorting does not take into fact that all nos from 0 to N-1 are in the array or not. But in this case as we know that all the nos from 0 to N-1 are present...can I get a better algorithm and just sorting the array??
Please Help
From http://thesaurus.maths.org/mmkb/entry.html?action=entryById&id=3340:
The mapping which takes every element to itself; it leaves every element unchanged. It is sometimes written I, so that I(x)=x for all x in a particular domain.
May be you want to get reverse mapping or what else?..
I know what identity mapping is.
i.e. Array=i.
From the random permutation i can come to this stage by sorting.
My question if can i do any better?? i.e sorting algorithm does not take into fact that all nos are present. but since i already know that all nos are present..can i do anything better to solve the problem. Im looking for a better algorithm than sorting.
Alas, I can't understand your problem.
i already know that all nos are present..can i do anything better to solve the problem. Im looking for a better algorithm than sorting.
What's a problem? Why sorting? Is it a problem:
int i;
for (i = 0; i < N; ++i)
Array[i] = i;?
Is it a problem to force an open door?...
Lets say i hv the permutation
2,5,4,1,0,7,6,3.
Now i want to bring it to
0,1,2,3,4,5,6,7.
Sorting will easily do the thing for me.
But im looking for a better algorithm than sorting.
i.e. since sorting (any type) will bring nos say 1,9,6,7,0 to 0,1,6,7,9
It doesn't take into consideration that all nos from 0 to 9 are present or not.
But i know that all nos are from 0 to N -1 (N = 8 in given case) are present in the array.
So can i can i modify the sorting algorithm in any way such that the time complexity is reduced? i.e a better algorithm with the known given condition.
If you KNOW that it's 0..N-1 permutation, no need to sort these KNOWN values at all. But the 2nd example {1,9,6,7,0} => {0,1,6,7,9} is NOT 0..N-1 permutation so it's another story...
The only non-trivial case with 0..N-1 permutation is: 0..N-1 are sorting keys of records (structures, for example). In that case you need rearrange an array of structures. You know right place of every record of source permutation so sort algorithm is a simple rearrangement of all records to its key positions. It's an optimal (and well-known) sort algorithm for this case.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.