Re: [Boost-users] How to find a sorting permutation

From: Daniel Krügler (dsp_at_[hidden])
Date: 2008-08-21 02:35:15

Zeljko Vrba wrote:
> I have a vector of element V that needs to be sorted.  I want to also produce a
> permutation vector P which reflects the element's position in the original
> vector.  P is initialized with identity permutation (P[i] == i).
> 
> 1st possibility: code my own sorting algorithm, and swap elements of P along
> with swapping elements of V.  This I want to avoid, if at all possible.
> 
> 2nd possibility: copy elements of V into new vector V' holding pair<T, size_t>
> and sort that.  (pair holds the original element as well as its starting
> position in the vector, i.e. .second is again initialized to identity
> permutation.)  Drawback: extra space and time spent on copying to V'.
> 
> 3rd possibility: sort elements of P with less_than doing lookups into V to do
> its comparison.  Drawback: while P holds the correct result, V is left
> unsorted; I have to do another pass through V and swap elements according to
> the permutation recorded in P, which is not trivial to do in-place.

I don't see a particular problem with this approach. If you provide
a helper function, which ensures the following

a) Step 1: The permutation vector is sorted according to the
given predicate.
b) Step 2: The indirect sort algorithm is applied on the original
data sequence.

the user has to write one single line - no more and no less then
(s)he would need to write if (s)he would std::sort directly.

> Is there some non-obvious, efficient and elegant way of achieving what I want?

I don't know what you mean with "non-obvious" ;-)

Personally I suggest route (3) to go, because it has several
advantages:

1) By creating your sort information (permutation vector) you can 
*decide* whether you want to sort the original sequence or not -
this is a strong plus IMO.
2) Once you have the permutation vector available you can apply
it as often as you like for any other sequence of proper length.
The time complexity for this approach is amortized O(N) if you
can accept a space complexity of N size_t values for each call
(needed to copy the permutation vector).
3) You can nicely combine boost::permutation_iterator with
the permutation vector to support traversal along virtually
sorted sequences, even though the underlying sequences are not
sorted.

It's an easy thing to create a class (e.g. indirect_sorter or
permutation_sorter or index_sorter), which holds the state
(permutation vector) and provides these convenience functions.
To give you a rough idea, I propose to use something like John
Potter's indexStableSort described at:

http://preview.tinyurl.com/6ncfdh

During that time I (Daniel Spangenberg is me, I wasn't married
to that time) asked a similar question and his idea was a great
help for me. Thanks again, John Potter!

Btw.: It's not too hard to generalize this idea and to extend
it for other sort function (including templates and thus
including std::sort) instead of stable_sort.

HTH & Greetings from Bremen,

Daniel Krügler