Inverse Permutation Question

[garu525]

Good day to all, I'm doing a project about inverse permutations from an array of permutations. It's my first time coding on permutations so I don't have any experience on this. So I came up with a solution to just swap the array and the element number as the inverted permutation. Here's my code by the way, I'm just wondering if the "seasoned" members here have any tips on doing an inverted permutation properly.

Please let me know if you guys have any advice. Thanks!

void inverse ( unsigned ip[], const unsigned p[], unsigned elements ) {
	unsigned tempArray = 0, tempIndex = 0;
	for (int i = 0; i < elements; i++ ) {
		tempIndex = i;
		tempArray = p[i];
		ip[tempArray] = tempIndex;
	}
	show ( ip, 5 );
}

[mrnutty]

I never heard of 'inverted premutation' but it looks like your reversing the key to value mapping into value to key mapping. The fastest way you can do this is in linear time, since you have to go through the whole array, which your function does. But there are some redundancies in your code and a possible bug.

The redudent code is your tempIndex, there is no need for it since you can simply use 'i' as it does not change in the body, until next iteration. And a possible bug is that you have no way of knowing whether 'ip' array is big enough, especially since the range p is huge. As a result of this, your program now suffers from buffer overflow and hackers can use this as a means to hack your program.

So to make your program more efficient in space,although you have to sacrifice time, you can do something like this,

//assume result size is same as mapping size
void inverse(const unsigned mapping, const unsigned size, unsigned result){
 for(unsigned i = 0; i < size; ++i){
   unsigned newKey = mapping[i];
   unsigned newKeyIndex = _getKeyIndex( result , newKey, size); //returns a unique index, via hashing
   result [ newKeyIndex ] = i;
}

The _getKeyIndex returns a index from [0,size) and it handles any collision. Google hashing for implementation. In theory the worst time for the above function is quadratic, because of the hashing, but the average case for hashing is constant.

So overall, you can decide from the requirements that whether space is an issue for you, I say this because the value of an unsigned can range from 0 to 4,294,967,295, that means your 'ip' array must be at least the maximum size, else your program will crash. If memory is an issue then you need to re-hash the index into proper index

[ravenous]

You can save some space by just losing all the temporary variables, but your basic algorithm is pretty much the fastest you can do in general. I'd probably just write:

void inverse ( unsigned *ip, unsigned *p, unsigned n )
{
   for ( unsigned i = 0; i < n; ++i )
      ip[ p[i] ] = i;
}

This still suffers from the possible buffer overflow problem that firstPerson described. You can use std::vector to avoid that problem:

void inverse ( const std::vector< unsigned >& p, std::vector< unsigned >& ip )
{
   ip.resize( p.size() );
   for ( unsigned i = 0; i < p.size(); ++i )
      ip[ p[i] ] = i;
}

Just my two cents :o)

Also, if you just want to do stuff with permutations and don't need to write your own, the GNU scientific library does basic permutation stuff (like next, prev, inverse etc. ).

[mrnutty]

>> ip.resize( p.size() );
>> ip[ p ] = i;

the problem as I mentioned is that the value of p can be much greater than p.size() therefore making the statement ip[ p ] a bug

[ravenous]

>> ip.resize( p.size() );
>> ip[ p ] = i;

the problem as I mentioned is that the value of p can be much greater than p.size() therefore making the statement ip[ p ] a bug

I guess that depends on what is meant by permutation. I take a permutation of size n to contain all values from 0 to n - 1 and to contain each value only once. So, for n = 5, say, a valid permutation would be:
$p = 0,4,3,1,2$
but something like:
$p = 0,4,3,1,16$
would be invalid.

For this definition, I guess you could put a bunch of checks in front of the actual inverting loop:

void inverse ( const std::vector< unsigned >& p, std::vector< unsigned >& ip )
{
   if ( p.empty() )
       return;

   /* Check validity of range */
   if ( *std::max_element( p.begin(), p.end() ) == p.size() - 1 ){
      /* Handle this error */
      return;
   }
   /* Check for repeated values */
   std::vector< bool > used( p.size(), false );
   for( unsigned i = 0; i < p.size(); ++i ){
      if ( used[ p[i] ){
           /* handle repeated number error */
           return;
      }
      used[ p[i] ] = true;
   }

   /* No need to check for unrepresented numbers, since this condition is */
   /* implied true if we get to this point, so by now the permutation is  */
   /* good for inversion.                                                 */
   
   ip.resize( p.size() );
   for ( unsigned i = 0; i < p.size(); ++i )
      ip[ p[i] ] = i;
}

Does that sound reasonable?

[garu525]

Wow thanks guys for the tips!

[mrnutty]

I guess that depends on what is meant by permutation. I take a permutation of size n to contain all values from 0 to n - 1 and to contain each value only once. So, for n = 5, say, a valid permutation would be:
$p = 0,4,3,1,2$
but something like:
$p = 0,4,3,1,16$
would be invalid.

For this definition, I guess you could put a bunch of checks in front of the actual inverting loop:

void inverse ( const std::vector< unsigned >& p, std::vector< unsigned >& ip )
{
   if ( p.empty() )
       return;

   /* Check validity of range */
   if ( *std::max_element( p.begin(), p.end() ) == p.size() - 1 ){
      /* Handle this error */
      return;
   }
   /* Check for repeated values */
   std::vector< bool > used( p.size(), false );
   for( unsigned i = 0; i < p.size(); ++i ){
      if ( used[ p[i] ){
           /* handle repeated number error */
           return;
      }
      used[ p[i] ] = true;
   }

   /* No need to check for unrepresented numbers, since this condition is */
   /* implied true if we get to this point, so by now the permutation is  */
   /* good for inversion.                                                 */
   
   ip.resize( p.size() );
   for ( unsigned i = 0; i < p.size(); ++i )
      ip[ p[i] ] = i;
}

Does that sound reasonable?

There is no specification that says permutation cannot contain any value from 0 to UNSIGNED_INT_MAX. Permutation is a concept hence it doesn't make sense to say permutation of size n. It needs to be taken generally. For example, the function could be called with an array that has all the permutation from 1,000,000 to 2,000,000 such that it satisfies some requirement, like is even and divisible by 5. The size of the permutation does not say anything about the permutation data it self

[mbundgaard]

This will not work in general. Counter-example:

(2, 0, 1, 3, 4)

Your algorithm gets stuck in a cycle in the first three elements, and, as a consequence, you will not traverse the entire array.

EDIT: STRIKE THAT. I MISREAD YOUR CODE AS DOING THE INVERTING IN-PLACE.