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 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

Date: Wed, 20 Aug 2008 16:29:08 +0200 From: zvrba@ifi.uio.no To: boost-users@lists.boost.org Subject: [Boost-users] How to find a sorting permutation

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).

If you haven't looked already, I would always suggest citeseer if for nothing else than benchmarks and tests of whatever you decide to do. A quick naive keyword search is as follows, http://citeseerx.ist.psu.edu/search?q=sort+permutation+order&sort=rel I think all of the papers are available free full text. _________________________________________________________________ Get ideas on sharing photos from people like you. Find new ways to share. http://www.windowslive.com/explore/photogallery/posts?ocid=TXT_TAGLM_WL_Phot...