In-place interleaving of the two halves of a string

Question

Given a string of even size, say:

abcdef123456

How would I interleave the two halves, such that the same string would become this:

a1b2c3d4e5f6

I tried attempting to develop an algorithm, but couldn't. Would anybody give me some hints as to how to proceed? I need to do this without creating extra string variables or arrays. One or two variable is fine.

I just don't want a working code (or algorithm), I need to develop an algorithm and prove it correctness mathematically.

Answer 1

You may be able to do it in O(N*log(N)) time:

Want: abcdefgh12345678 -> a1b2c3d4e5f6g7h8

a b c d e f g h
  1 2 3 4 5 6 7 8

  4 1-sized swaps:

a 1 c 3 e 5 g 7
  b 2 d 4 f 6 h 8

a1  c3  e5  g7
    b2  d4  f6  h8

  2 2-sized swaps:

a1  b2  e5  f6
    c3  d4  g7  h8

a1b2  e5f6
      c3d4  g7h8

  1 4-sized swap:

a1b2  c3d4
      e5f6  g7h8

a1b2c3d4
        e5f6g7h8

Implementation in C:

#include <stdio.h>
#include <string.h>

void swap(void* pa, void* pb, size_t sz)
{
  char *p1 = pa, *p2 = pb;
  while (sz--)
  {
    char tmp = *p1;
    *p1++ = *p2;
    *p2++ = tmp;
  }
}

void interleave(char* s, size_t len)
{
  size_t start, step, i, j;

  if (len <= 2)
    return;

  if (len & (len - 1))
    return; // only power of 2 lengths are supported

  for (start = 1, step = 2;
       step < len;
       start *= 2, step *= 2)
  {
    for (i = start, j = len / 2;
         i < len / 2;
         i += step, j += step)
    {
      swap(s + i,
           s + j,
           step / 2);
    }
  }
}

char testData[][64 + 1] =
{
  { "Aa" },
  { "ABab" },
  { "ABCDabcd" },
  { "ABCDEFGHabcdefgh" },
  { "ABCDEFGHIJKLMNOPabcdefghijklmnop" },
  { "ABCDEFGHIJKLMNOPQRSTUVWXYZ0<({[/abcdefghijklmnopqrstuvwxyz1>)}]\\" },
};

int main(void)
{
  unsigned i;

  for (i = 0; i < sizeof(testData) / sizeof(testData[0]); i++)
  {
    printf("%s -> ", testData[i]);
    interleave(testData[i], strlen(testData[i]));
    printf("%s\n", testData[i]);
  }

  return 0;
}

Output (ideone):

Aa -> Aa
ABab -> AaBb
ABCDabcd -> AaBbCcDd
ABCDEFGHabcdefgh -> AaBbCcDdEeFfGgHh
ABCDEFGHIJKLMNOPabcdefghijklmnop -> AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPp
ABCDEFGHIJKLMNOPQRSTUVWXYZ0<({[/abcdefghijklmnopqrstuvwxyz1>)}]\ -> AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz01<>(){}[]/\

Answer 2

Generically that problem is quite hard -- and it reduces to finding permutation cycles. The number and length of those varies quite a lot depending on the length.

The first and last cycles are always degenerate; the 10 entry array has 2 cycles of lengths 6 and 2 and the 12 entry array has a single cycle of length 10.

Withing a cycle one does:

 for (i=j; next=get_next(i) != j; i=next) swap(i,next);

Even though the function next can be implemented as some relatively easy formula of N, the problem is postponed to do book accounting of what indices have been swapped. In the left case of 10 entries, one should [quickly] find the starting positions of the cycles (they are e.g. 1 and 3).

Answer 3

Ok lets start over. Here is what we are going to do:

def interleave(string):
    i = (len(string)/2) - 1
    j = i+1

    while(i > 0):
        k = i
        while(k < j):
            tmp = string[k]
            string[k] = string[k+1]
            string[k+1] = tmp
            k+=2 #increment by 2 since were swapping every OTHER character
        i-=1 #move lower bound by one
        j+=1 #move upper bound by one

Here is an example of what the program is going to do. We are going to use variables i,j,k. i and j will be the lower and upper bounds respectively, where k is going to be the index at which we swap.

Example

`abcd1234`

i = 3 //got this from (length(string)/2) -1

j = 4 //this is really i+1 to begin with

k = 3 //k always starts off reset to whatever i is 

swap d and 1
increment k by 2 (k = 3 + 2 = 5), since k > j we stop swapping

result `abc1d234` after the first swap

i = 3 - 1 //decrement i
j = 4 + 1 //increment j
k= 2 //reset k to i

swap c and 1, increment k (k = 2 + 2 = 4), we can swap again since k < j
swap d and 2, increment k (k = 4 + 2 = 6), k > j so we stop
//notice at EACH SWAP, the swap is occurring at index `k` and `k+1`

result `ab1c2d34`

i = 2 - 1
j = 5 + 1
k = 1

swap b and 1, increment k (k = 1 + 2 = 3), k < j so continue
swap c and 2, increment k (k = 3 + 2 = 5), k < j so continue
swap d and 3, increment k (k = 5 + 2 = 7), k > j so were done

result `a1b2c3d4`

As for proving program correctness, see this link. It explains how to prove this is correct by means of a loop invariant.

A rough proof would be the following:

1. Initialization: Prior to the first iteration of the loop we can see that i is set to (length(string)/2) - 1. We can see that i <= length(string) before we enter the loop.
2. Maintenance. After each iteration, i is decremented (i = i-1, i=i-2,...) and there must be a point at which i<length(string).
3. Termination: Since i is a decreasing sequence of positive integers, the loop invariant i > 0 will eventually equate to false and the loop will exit.