就地串的两半的交织 [英] In-place interleaving of the two halves of a string

问题描述

由于一串的甚至的尺寸，说：

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.

我只是不想工作code（或算法），我需要开发一种算法，并证明它的正确性数学。

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

推荐答案

您可能能够做到在O（N *日志（N））时间：

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

在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;
}

输出（ ideone ）：

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

这篇关于就地串的两半的交织的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！