29

Let's say I have an array A with n unique elements on the range [0, n). In other words, I have a permutation of the integers [0, n).

Is possible to transform A into B using O(1) extra space (AKA in-place) such that B[A[i]] = i?

For example:

       A                  B
[3, 1, 0, 2, 4] -> [2, 1, 3, 0, 4]
9
  • Can we use the sign bit of your array entries to encode information or would that go against the idea of not using extra space?
    – Niklas B.
    Aug 2, 2015 at 15:18
  • @NiklasB. That would be 1 bit per entry - O(n) space. Not allowed.
    – orlp
    Aug 2, 2015 at 15:21
  • Well that really depends on the model. In the classical RAM model for example, we have log n < w and thus we don't "waste" space by using the rest of the w - log n bits. So what's your model?
    – Niklas B.
    Aug 2, 2015 at 15:22
  • 1
    @NiklasB. If you want to be specific, the transdichotomous model.
    – orlp
    Aug 2, 2015 at 15:29
  • 1
    This sounds as if it fits better at Computer Science
    – Bergi
    Aug 2, 2015 at 18:36

5 Answers 5

24

Yes, it is possible, with O(n^2) time algorithm:

Take element at index 0, then write 0 to the cell indexed by that element. Then use just overwritten element to get next index and write previous index there. Continue until you go back to index 0. This is cycle leader algorithm.

Then do the same starting from index 1, 2, ... But before doing any changes perform cycle leader algorithm without any modifications starting from this index. If this cycle contains any index below the starting index, just skip it.


Or this O(n^3) time algorithm:

Take element at index 0, then write 0 to the cell indexed by that element. Then use just overwritten element to get next index and write previous index there. Continue until you go back to index 0.

Then do the same starting from index 1, 2, ... But before doing any changes perform cycle leader algorithm without any modifications starting from all preceding indexes. If current index is present in any preceding cycle, just skip it.


I have written (slightly optimized) implementation of O(n^2) algorithm in C++11 to determine how many additional accesses are needed for each element on average if random permutation is inverted. Here are the results:

size accesses
2^10 2.76172
2^12 4.77271
2^14 6.36212
2^16 7.10641
2^18 9.05811
2^20 10.3053
2^22 11.6851
2^24 12.6975
2^26 14.6125
2^28 16.0617

While size grows exponentially, number of element accesses grows almost linearly, so expected time complexity for random permutations is something like O(n log n).

1
  • 2
    There's a proof of the Theta(n log n) expected complexity, where we show that iteration j makes about n / (j + 1) reads in expectation (that number is "with replacement"; I think that the correction term is low-order, though). Aug 3, 2015 at 18:13
0

Inverting an array A requires us to find a permutation B which fulfills the requirement A[B[i]] == i for all i.

To build the inverse in-place, we have to swap elements and indices by setting A[A[i]] = i for each element A[i]. Obviously, if we would simply iterate through A and perform aforementioned replacement, we might override upcoming elements in A and our computation would fail.

Therefore, we have to swap elements and indices along cycles of A by following c = A[c] until we reach our cycle's starting index c = i.

Every element of A belongs to one such cycle. Since we have no space to store whether or not an element A[i] has already been processed and needs to be skipped, we have to follow its cycle: If we reach an index c < i we would know that this element is part of a previously processed cycle.

This algorithm has a worst-case run-time complexity of O(n²), an average run-time complexity of O(n log n) and a best-case run-time complexity of O(n).

function invert(array) {
  main:
  for (var i = 0, length = array.length; i < length; ++i) {
    
    // check if this cycle has already been traversed before:
    for (var c = array[i]; c != i; c = array[c]) {
      if (c <= i) continue main;
    }
    
    // Replacing each cycle element with its predecessors index:
    var c_index = i, 
        c = array[i];
    do {
      var tmp = array[c];
      array[c] = c_index; // replace
      c_index = c; // move forward
      c = tmp;
    } while (i != c_index)
      
  }
  return array;
}
  
console.log(invert([3, 1, 0, 2, 4])); // [2, 1, 3, 0, 4]

Example for A = [1, 2, 3, 0] :

  1. The first element 1 at index 0 belongs to the cycle of elements 1 - 2 - 3 - 0. Once we shift indices 0, 1, 2 and 3 along this cycle, we have completed the first step.

  2. The next element 0 at index 1 belongs to the same cycle and our check tells us so in only one step (since it is a backwards step).

  3. The same holds for the remaining elements 1 and 2.

    enter image description here

In total, we perform 4 + 1 + 1 + 1 'operations'. This is the best-case scenario.

0

Implementation of this explanation in Python:

def inverse_permutation_zero_based(A):
    """
    Swap elements and indices along cycles of A by following `c = A[c]` until we reach
    our cycle's starting index `c = i`.

    Every element of A belongs to one such cycle. Since we have no space to store
    whether or not an element A[i] has already been processed and needs to be skipped,
    we have to follow its cycle: If we reach an index c < i we would know that this
    element is part of a previously processed cycle.

    Time Complexity: O(n*n), Space Complexity: O(1)
    """

    def cycle(i, A):
        """
        Replacing each cycle element with its predecessors index
        """
        c_index = i
        c = A[i]

        while True:
            temp = A[c]
            A[c] = c_index  # replace
            c_index = c  # move forward
            c = temp

            if i == c_index:
                break

    for i in range(len(A)):
        # check if this cycle has already been traversed before
        j = A[i]

        while j != i:
            if j <= i:
                break
            j = A[j]
        else:
            cycle(i, A)

    return A

>>> inverse_permutation_zero_based([3, 1, 0, 2, 4])
[2, 1, 3, 0, 4]
0

This can be done in O(n) time complexity and O(1) space if we try to store 2 numbers at a single position.

First, let's see how we can get 2 values from a single variable. Suppose we have a variable x and we want to get two values from it, 2 and 1. So,
 
x = n*1 + 2 , suppose n = 5 here.
x = 5*1 + 2 = 7
Now for 2, we can take remainder of x, ie, x%5. And for 1, we can take quotient of x, ie , x/5

and if we take n = 3
x = 3*1 + 2 = 5

x%3 = 5%3 = 2
x/3 = 5/3 = 1

We know here that the array contains values in range [0, n-1], so we can take the divisor as n, size of array. So, we will use the above concept to store 2 numbers at every index, one will represent old value and other will represent the new value.

  A                   B

 0  1  2  3  4      0  1  2  3  4    
[3, 1, 0, 2, 4] -> [2, 1, 3, 0, 4]

.

a[0] = 3, that means, a[3] = 0 in our answer.
a[a[0]] = 2 //old
a[a[0]] = 0 //new
a[a[0]] = n* new + old = 5*0 + 2 = 2

a[a[i]] = n*i + a[a[i]]

And during array traversal, a[i] value can be greater than n because we are modifying it. So we will use a[i]%n to get the old value. So the logic should be

a[a[i]%n] = n*i + a[a[i]%n]

Array -> 13 6 15 2 24

Now, to get the older values, take the remainder on dividing each value by n, and to get the new values, just divide each value by n, in this case, n=5.

Array -> 2 1 3 0 4 
1
  • It's a nice idea, but only works if your data type is larger than necessary. E.g. for inverting an array of 256 uint8_ts in C it won't work.
    – orlp
    Jul 19, 2021 at 12:09
0

Following approach Optimizes the cycle walk if it is already handled. Also each element is 1 based. Need to convert accordingly while trying to access the elements in the given array.

#include <stdio.h>

#include <iostream>
#include <vector>
#include <bits/stdc++.h>

using namespace std;
 
 // helper function to traverse cycles
    void cycle(int i, vector<int>& A) {
        int cur_index = i+1, next_index = A[i];
        while (next_index > 0) {
            int temp = A[next_index-1];
            A[next_index-1] = -(cur_index);
            cur_index = next_index;
            next_index = temp;
            if (i+1 == abs(cur_index)) {
                break;
            }
        }
    }

void inverse_permutation(vector<int>& A) {
    
    for (int i = 0; i < A.size(); i++) {
        cycle(i, A);
    }
    for (int i = 0; i < A.size(); i++) {
        A[i] = abs(A[i]);
    }
    for (int i = 0; i < A.size(); i++) {
        cout<<A[i]<<" ";
    }
}
int main(){
  // vector<int> perm = {4,0,3,1,2,5,6,7,8};
    vector<int> perm = {5,1,4,2,3,6,7,9,8};
  //vector<int> perm =  { 17,2,15,19,3,7,12,4,18,20,5,14,13,6,11,10,1,9,8,16};
  
    // vector<int> perm = {4, 1, 2, 3};
    //   { 6,17,9,23,2,10,20,7,11,5,14,13,4,1,25,22,8,24,21,18,19,12,15,16,3 } =
    //          { 14,5,25,13,10,1,8,17,3,6,9,22,12,11,23,24,2,20,21,7,19,16,4,18,15 }

   // vector<int> perm = {6, 17, 9, 23, 2, 10, 20, 7, 11, 5, 14, 13, 4, 1, 25, 22, 8, 24, 21, 18, 19, 12, 15, 16, 3};
     inverse_permutation(perm);
     
    return 0;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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