Reorder a string by half the character

This is an i开发者_开发百科nterview question.

Given a string such as: 123456abcdef consisting of n/2 integers followed by n/2 characters. Reorder the string to contain as 1a2b3c4d5e6f . The algortithm should be in-place.

The solution I gave was trivial - O(n^2). Just shift the characters by n/2 places to the left.

I tried using recursion as -

a. Swap later half of the first half with the previous half of the 2nd part - eg

123 456 abc def

123 abc 456 def

b. Recurse on the two halves.

The pbm I am stuck is that the swapping varies with the number of elements - for eg.

What to do next? 123 abc 12ab 3c

And what to do for : 12345 abcde 123abc 45ab

This is a pretty old question and may be a duplicate. Please let me know.. :)

Another example: Input: 38726zfgsa Output: 3z8f7g2s6a

Here's how I would approach the problem:

1) Divide the string into two partitions, number part and letter part
2) Divide each of those partitions into two more (equal sized)
3) Swap the second the third partition (inner number and inner letter)
4) Recurse on the original two partitions (with their newly swapped bits)
5) Stop when the partition has a size of 2

For example:

123456abcdef -> 123456 abcdef -> 123 456 abc def -> 123 abc 456 def

123abc -> 123 abc -> 12 3 ab c -> 12 ab 3 c

12 ab -> 1 2 a b -> 1 a 2 b

... etc

And the same for the other half of the recursion..

All can be done in place with the only gotcha being swapping partitions that aren't the same size (but it'll be off by one, so not difficult to handle).

It is easy to permute an array in place by chasing elements round cycles if you have a bit-map to mark which elements have been moved. We don't have a separate bit-map, but IF your characters are letters (or at least have the high order bit clear) then we can use the top bit of each character to mark this. This produces the following program, which is not recursive and so does not use stack space.

class XX
{
  /** new position given old position */
  static int newFromOld(int x, int n)
  {
    if (x < n / 2)
    {
      return x * 2;
    }
    return (x - n / 2) * 2 + 1;
  }
  private static int HIGH_ORDER_BIT = 1 << 15; // 16-bit chars
  public static void main(String[] s)
  {
    // input data - create an array so we can modify
    // characters in place
    char[] x = s[0].toCharArray();
    if ((x.length & 1) != 0)
    {
      System.err.println("Only works with even length strings");
      return;
    }
    // Character we have read but not yet written, if any
    char holding = 0;
    // where character in hand was read from
    int holdingPos = 0;
    // whether picked up a character in our hand
    boolean isHolding = false;
    int rpos = 0;
    while (rpos < x.length)
    { // Here => moved out everything up to rpos
      // and put in place with top bit set to mark new occupant
      if (!isHolding)
      { // advance read pointer to read new character
        char here = x[rpos];
        holdingPos = rpos++;
        if ((here & HIGH_ORDER_BIT) != 0)
        {
         // already dealt with
         continue;
        }
        int targetPos = newFromOld(holdingPos, x.length);
        // pick up char at target position
        holding = x[targetPos];
        // place new character, and mark as new
        x[targetPos] = (char)(here | HIGH_ORDER_BIT);
        // Now holding a character that needs to be put in its
        // correct place
        isHolding = true;
        holdingPos = targetPos;
      }
      int targetPos = newFromOld(holdingPos, x.length);
      char here = x[targetPos];
      if ((here & HIGH_ORDER_BIT) != 0)
      { // back to where we picked up a character to hold
        isHolding = false;
        continue;
      }
      x[targetPos] = (char)(holding | HIGH_ORDER_BIT);
      holding = here;
      holdingPos = targetPos;
    }
    for (int i = 0; i < x.length; i++)
    {
      x[i] ^= HIGH_ORDER_BIT;
    }
    System.out.println("Result is " + new String(x));
  }
}

These days, if I asked someone that question, what I'm looking for them to write on the whiteboard first is:

assertEquals("1a2b3c4d5e6f",funnySort("123456abcdef"));
...

and then maybe ask for more examples.

(And then, depending, if the task is to interleave numbers & letters, I think you can do it with two walking-pointers, indexLetter and indexDigit, and advance them across swapping as needed til you reach the end.)

In your recursive solution why don't you just make a test if n/2 % 2 == 0 (n%4 ==0 ) and treat the 2 situations differently

As templatetypedef commented your recursion cannot be in-place.

But here is a solution (not in place) using the way you wanted to make your recursion :

def f(s):
    n=len(s)
    if n==2:  #initialisation
        return s
    elif n%4 == 0 :  #if n%4 == 0 it's easy
        return f(s[:n/4]+s[n/2:3*n/4])+f(s[n/4:n/2]+s[3*n/4:])
    else:  #otherwise, n-2 %4 == 0
        return s[0]+s[n/2]+f(s[1:n/2]+s[n/2+1:])

Here we go. Recursive, cuts it in half each time, and in-place. Uses the approach outlined by @Chris Mennie. Getting the splitting right was tricky. A lot longer than Python, innit?

/* In-place, divide-and-conquer, recursive riffle-shuffle of strings;
 * even length only.  No wide characters or Unicode; old school. */

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

void testrif(const char *s);
void riffle(char *s);
void rif_recur(char *s, size_t len);
void swap(char *s, size_t midpt, size_t len);
void flip(char *s, size_t len);
void if_odd_quit(const char *s);

int main(void)
{
    testrif("");
    testrif("a1");
    testrif("ab12");
    testrif("abc123");
    testrif("abcd1234");
    testrif("abcde12345");
    testrif("abcdef123456");

    return 0;
}

void testrif(const char *s)
{
    char mutable[20];

    strcpy(mutable, s);
    printf("'%s'\n", mutable);
    riffle(mutable);
    printf("'%s'\n\n", mutable);
}

void riffle(char *s)
{
    if_odd_quit(s);
    rif_recur(s, strlen(s));
}

void rif_recur(char *s, size_t len)
{
    /* Turn, e.g., "abcde12345" into "abc123de45", then recurse. */

    size_t pivot = len / 2;
    size_t half = (pivot + 1) / 2;
    size_t twice = half * 2;

    if (len < 4)
        return;

    swap(s + half, pivot - half, pivot);
    rif_recur(s, twice);
    rif_recur(s + twice, len - twice);
}

void swap(char *s, size_t midpt, size_t len)
{
    /* Swap s[0..midpt] with s[midpt..len], in place. Algorithm from
     * Programming Pearls, Chapter 2. */

    flip(s, midpt);
    flip(s + midpt, len - midpt);
    flip(s, len);
}

void flip(char *s, size_t len)
{
    /* Reverse order of characters in s, in place. */

    char *p, *q, tmp;

    if (len < 2)
        return;

    for (p = s, q = s + len - 1; p < q; p++, q--) {
        tmp = *p;
        *p = *q;
        *q = tmp;
    }
}

void if_odd_quit(const char *s)
{
    if (strlen(s) % 2) {
        fputs("String length is odd; aborting.\n", stderr);
        exit(1);
    }
}

By comparing 123456abcdef and 1a2b3c4d5e6f we can note that only the first and the last characters are in their correct position. We can also note that for each remaining n-2 characters we can compute their correct position directly from their original position. They will get there, and the element that was there surely was not in the correct position, so it will have to replace another one. By doing n-2 such steps all the elements will get to the correct positions:

 void funny_sort(char* arr, int n){
    int pos = 1;    // first unordered element
    char aux = arr[pos];
    for (int iter = 0; iter < n-2; iter++) { // n-2 unordered elements
        pos = (pos < n/2) ? pos*2 : (pos-n/2)*2+1;// correct pos for aux
        swap(&aux, arr + pos);
    }
}

Score each digit as its numerical value. Score each letter as a = 1.5, b = 2.5 c = 3.5 etc. Run an insertion sort of the string based on the score of each character.

[ETA] Simple scoring won't work so use two pointers and reverse the piece of the string between the two pointers. One pointer starts at the front of the string and advances one step each cycle. The other pointer starts in the middle of the string and advances every second cycle.

123456abcdef
 ^    ^

1a65432bcdef
  ^   ^

1a23456bcdef
   ^   ^

1a2b6543cdef
    ^  ^