in-place permutation of a array follows this rule

Question

Suppose there is an array, we want to find everything in the odd index (index starting with 0), and move it to the end. Everything in the even index move it to the beginning. The relative order of all odd index items and all even index items are preserved.

i.e. if the array is

a1 b1 a2 b2 ...  an bn    

after the operation it becomes

a1 a2 a3 ... an b1 b2 ... bn

Can this be done in-place and in O(n) time?

Answer 1

Well, let's look at this example:

0 1 2 3 4 5 6 7 8 9 10

0 2 4 6 8 10 1 3 5 7 9

First half of the result contains elements with their indices being i / 2 of the original index i, while the other half is i - n / 2 + 1, where n is the number of items in the array.

This is basically a special case of sorting algorithms, only with a special order being set.

So here is an idea to use a bubblesort algorithm to sort an array of integers. What we need is to pull the even values to the beginning leaving odd values behind:

0 1 2 3 4 5 6 7 8 9 10
  * *
0 2 1 3 4 5 6 7 8 9 10
      * *
0 2 1 4 3 5 6 7 8 9 10
    * *
0 2 4 1 3 5 6 7 8 9 10
          * *
0 2 4 1 3 6 5 7 8 9 10
        * *
...
0 2 4 6 1 3 5 7 8 9 10
              * *
...
0 2 4 6 8 1 3 5 7 9 10
                  * *

This will only work if you can preserve the indices (i.e. in this case indices correlate with array values), though. And bubblesort's performance is O(n^2) and memory usage is 1.

It cannot be accomplished in O(n) time and 1 memory [EDIT: using just generic sorting algoritms!], best generic sorting algorithms perform in O(nlog n):

http://en.wikipedia.org/wiki/Sorting_algorithm

To solve your problem, the best way would be to generate an array of indices matching your criterium:

size_t* indices = new size_t[n]; 

// n is the number of items in the original array
for (int i = 0; i < n; i++)
{
    if (i < n / 2)
    {
       indices[i] = i * 2;
    }
    else
    {
       indices[i] = i - n / 2 + 1;
    }
}

and then simply use it to map the items in the original array to new positions:

// i is the new index here, which makes it appear as if ValuesArray has been sorted
Type* getOddEvenValue(size_t newIndex)
{
     // ValuesArray and indices should be available in this scope, of course
     return ValuesArray[indices[newIndex]];
}

This thing would run in O(n) but would also require O(n) memory. But if the sizeof Type is much bigger than sizeof int, then it's still a gain in memory usage (as opposed to copying Type objects).

[EDIT2:]

Instead of the nice OOP code andand did, which also requires you to copy the original vector into your class' instance, you could simply write a function:

 size_t permuted_index(size_t i, size_t vecSize)
 {
    return ( i < vecSize/2 ? i * 2 : 2 * (i - vecSize/2) + 1);
 }

and use that whenever you need to get the permutted value. Indeed, this only requires O(n) time, since permutted_index would then be evaluated no more than n times for the given vector (in a full "for each" loop, at least).

Answer 2

It is possible, but it is very complicated! A simpler O(nlogn) and O(1) space solution might be better to code and in terms of cache.

We will solve a problem different from yours, but your problem is trivial to solve once we solve that problem.

Consider the array to be

b1, a1, b2, a2, ..., bn, an

and you have to convert this to

a1, a2, ..., an, b1, b2, ..., bn

Working with indices 1 to 2n,

we see that this is given by

i -> (n+1)*i (mod 2n+1).

---

An O(nlogn) time O(1) space solution

We can use divide and conquer as follows.

First for some m close to n/2 convert

b1, a1, ..., bn , an

to

a1,a2,...am, b1,b2, ..bm, a(m+1), ..., an, b(m+1), ... , bn

by recursively applying to first 2m elements, and then the remaining.

Now all we need to do this cyclic shift the middle array by m spots (this can be done in O(n) time and O(1) space)

to give

a1, a2, .., am , a(m+1), ..., an, b1, b2, ..., bm, b(m+1), ..., bn.

Of course, as IVlad pointed out, this needs O(logn) stack space. We can get around that by doing the following:

We have:

b1 a1, b2 a2, .. bm am, b(m+1) a(m+1), ..., bn an

Now swap pairs in the latter part of the array to give

b1 a1, b2 a2, .. bm am, a(m+1) b(m+1), ..., an bn

Now cyclic shift the elements at odd position: b1, b2, .., bm, a(m+1), a(m+2) ..., a(n).

This gives something like

a(m+1) a1, a(m+2) a2, ..., a(2m) am, a(2m+1) b(m+1),...,an b(n-m), b1 b(n-m+1),...,bm bn

Now again swap the latter part of the array to give

a(m+1) a1, a(m+2) a2, ..., a(2m) am, b(m+1) a(2m+1),...,b(n-m) an,b(n-m+1) b1,..., bn bm

Now recursively solve the first part and second part to give

[a1 a2 ... am][a(m+1) ... a(2m)]   [a(2m+1) ...an b1 b2 .. bm][b(m+1) ... bn]

This works whether 2m >= n or not.

So, this is O(nlogn) time and O(1) space algorithm.

---

An O(n) time O(1) space solution.

The ideas used are similar to the ideas used in the following paper: A simple in-place algorithm for Inshuffle.

You would need to read that paper to understand the below. I suggest you also read: http://stackoverflow.com/questions/2352542/how-to-master-in-place-array-modification-algorithms

This is basically the inverse permutation of what is solved in the paper above.

It is enough to solve this when 2n+1 is a power of 3 = (3^m say), as we can use divide and conquer after that (like the O(nlogn) solution).

Now 2n+1 and n+1 are relatively prime, so working modulo 3^m, we see that n+1 must be some power of 2. (See that paper again to see why: basically any number modulo 3^m which is relative prime to 3^m is a power of 2, again modulo 3^m).

Say n+1 = 2^k (we don't know k yet and note this is modulo 3^m).

A way to find out k, compute powers of n+1 modulo 3^m, till it becomes 1. This gives us k (and is O(n) time at most).

Now we can see that the cycles of the permutation (see above paper/stackoverflow link for what that is) start at

2^a*3^b

where 0 <= a < k, and 0 <= b < m.

So you start with each possible pair (a,b) and follow the cycles of the permutation, and this gives an O(n) time, in-place algorithm, as you touch each element no more than a constant number of times!

This was a bit brief(!) and if you need more info, please let me know.

Answer 3

What you have is an N X 2 matrix represented in a one dimentional array that you want transposed into a 2 X N array.

For example your list:

a₁, b₁, a₂, b₂, ... a_n, b_n

can just as well be represented as the matrix:

x_1,1, x_1,2, x_2,1, x_2,2, ... x_n,1, x_n,2

Which you want to transpose to become:

x_1,1, x_2,1, ... x_n,1, x_1,2, x_2,2, ... x_n,2

The in place matrix transposition algorithm will do the job.

EDIT

Ok let me spell it out. Try the following bit of code:

i = 0                /* linear array index */
do j = 1 to c        /* j = 1 to virtural columns */
  do k = 1 to r      /* k = 1 to virtural rows */
    i = i + 1
    sp = (k - 1) * c + j
    do while sp < i
      ct = (sp - 1) % r + 1
      rt = sp - (ct - 1) * r
      sp = (rt - 1) * c + ct
    end
    if i \= sp then say 'swap('i',' sp')'   /* swap elements */
  end
end

This will print out the array elements that need to be swapped. This will work for any sized matrix represented in a linear array where the elements are arranged by column then row. Using an N X 2 martix, the elements would be arranged as follows:

x_1,1, x_1,2, x_2,1, x_2,2, ... x_n,1, x_n,2

The algorithm prints out the elements that need to be swapped to yield an array orderd as follows:

x_1,1, x_2,1, ... x_n,1, x_1,2, x_2,2, ... x_n,2

For example, start with r = 4, c = 2 and the array:

 A1, B1, A2, B2, A3, B3, A4, B4

Requires the following swaps:

swap(2, 3)
swap(3, 5)
swap(4, 7)
swap(6, 7)

to become:

 A1, A2, A3, A4, B1, B2, B3, B4

This algorithm is efficient in both space and time.

Big-O

My O-foo is not great but I will give it a shot...

The matrix contains 2 columns ('A' and 'B') and 'M' rows. To represent this as a linear array we need 2M elements. Lets call that number N (the size of the linear array).

The algorithm has two iteration loops, one for 'r' (rows) and one for 'c' (columns). Total iterations is then r * c which in our case comes down to 2M = N. So far so good.

The wild card is the inner DO WHILE loop. How many iterations does it require for a given number of rows? The answer may be: Quite a few. Based on some empirical results (shown below) it looks like the number of DO WHILE iterations is a complex function involving 'r' when 'c' = 2 (or probably any value of 'c'). I do not have enough O-foo to figure out exactly what this function is. However, it should not get any worse than N³ (one complete 'chase' through the matrix, N², times every element, N). Not a good picture - in theory. So I guess that makes it O(N³)? This may be a non O(N) algorithm, but in practical terms appears to perform close to O(N) given the bits of empirical data below. I'm kind of lost at this point - comments welcome!

One observation about the DO WHILE loop though: It is using integer based math on simple variables (no array references required). If you are going non-linear this has got to be the 'cheapest' place to do it!

How many swaps are required? The number of swaps is limited to one per iteration through the outer two loops, which is at most N times. The number of swaps is in line with an O(N) performance.

My guess is that this is a non O(N) algorithm, but does appear to have reasonable behavior for 2 column matrices of moderate size.

Here are some empirical results for various 2 column matrix sizes:

      Rows Loops per row
========== =============
       500             9
     1,000            19
     1,500            21
     2,000            12
     2,500            18
     3,000            23
     3,500            26
 1,000,000            30
 2,000,000            40
 3,000,000            45
10,000,000            59
20,000,000            39
30,000,000            60

The 'loops per row' grow with row count, but not at an alarming rate. The danger is of hitting some 'sweet' spot where it goes exponential - but I don't know if it really has that potential.

My advice to Mgccl would be to benchmark this algorithm over the range of row counts that are typical in his application then decide if it would yield an acceptable performance relative to other algorithm benchmarks. Big-O analysis is interesting, but results over an operational range of data are what count.

Last kick at the can: Why does this algorithm work?

Transpose a matrix represented in linear form:

Given matrix X having M rows and N columns.

Lay X out into a linear array in row major order. The array will be organized as follows:

11, 12, 13, ... 1N, 21, 22, 23, ... 2N, ... M1, M2, M3 ... MN

A notation describing each element in the linear array is:

    X[i,r,c] 

where: i is the linear array index for element X 
       r is the row number for element X
       c is the column number for element X. 

Using this notation, an array in row major order can be generated as:

i = 0
for j = 1 to M    /* Row counter */
  for k = 1 to N  /* Column counter */
    i = i + 1     /* array index of element j, k */
    say 'X['i','j',k']'
  end
end

Note that given values for j (row) and k (column), i may be calculated as:

i = (j - 1) * N + k

The transpose of matrix X is constructed by exchanging the elements X[i,r,c] with X[t,c,r] over the range of r and c. In essence we exchange all row variables for column variables. Using the notation described above, this amounts to exchanging linear array elements:

    exchange(X[i,r,c], X[t,c,r])

where: i = (r - 1) * N + c
       t = (c - 1) * M + i

The number of exchanges required to transpose the matrix will be less than M * N because at most one exchange is ever required to place an element into its correct position. In some cases an exchange will not be required because the element is already 'in place'. For example the first and last elements of X never need exchanging.

By proceeding through the linear array by increasing i, we know that as long as none of the exchanges involve elements where i > t, the matrix will be in column major order for all elements having indexes less than or equal to i.

Whenever i > t, it means that a prior exchange took place at index t. The element at t was exchanged as indicated above placing it at some new position t'. Given an index t, we may calculate the row major index t' as well as the row and column numbers associate with it as follows:

 c' = (t - 1) % M + 1
 r' = t - (c' - 1) * M
 t' = (r' - 1) * N + c'

Again, if t' is less than i, it means that this element was exchanged too and we must continue with another round of calculations. Set t to the calculated t' and repeat. Eventually, i will become <= t and the exchange may be done. Basically we 'chase' the element through all of its prior exchanges until we find it at i or to the right of i in the linear array.

Repeat this cycle for each element in the linear array and the matrix will have been transposed.