Наложение на месте двух половин строки

Ответ 1

Возможно, вы сможете сделать это в O (N * log (N)):

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<>(){}[]/\

Ответ 2

В общем, эта проблема довольно сложная - и она сводится к поиску циклов перестановок. Количество и длина этих переменных сильно различаются в зависимости от длины.

Первый и последний циклы всегда вырождаются; 10-элементный массив имеет 2 цикла длин 6 и 2, а 12-элементный массив имеет один цикл длиной 10.

С помощью цикла:

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

Несмотря на то, что следующая функция может быть реализована как некоторая относительно простая формула N, проблема откладывается, чтобы делать бухгалтерский учет того, какие индексы были заменены. В левом случае из 10 записей следует [быстро] найти начальные позиции циклов (они, например, 1 и 3).

Ответ 3

Ok позволяет начать сначала. Вот что мы будем делать:

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

Вот пример того, что программа собирается делать. Мы будем использовать переменные i, j, k. i и j будут соответственно нижней и верхней границами, где k будет индексом, в котором мы поменяем.

Пример

`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`

Что касается проверки правильности программы, см. ссылку . Он объясняет, как доказать, что это правильно с помощью инварианта цикла.

Грубое доказательство было бы следующим:

• Инициализация: до первой итерации цикла мы видим, что i (length(string)/2) - 1. Мы можем видеть, что я <= length (string), прежде чем мы войдем в цикл.
• Обслуживание. После каждой итерации i уменьшается (i = i-1, i=i-2,...) и должна быть точка, в которой i<length(string).
• Termination: Поскольку i является уменьшающейся последовательностью положительных целых чисел, инвариант цикла i > 0 в конечном итоге будет равен false и цикл завершится.

Ответ 4

Решение здесь Дж. Эллис и М. Марков. In-situ, стабильное слияние в виде идеального shu ffl e. Компьютерный журнал. 43 (1): 40-53, (2000).

Также см. различные обсуждения здесь:

• https://cs.stackexchange.com/questions/332/in-place-algorithm-for-interleaving-an-array/400#400
• https://cstheory.stackexchange.com/questions/13943/linear-time-in-place-riffle-shuffle-algorithm.

Ответ 5

Хорошо, вот черновик. Вы говорите, что вам не нужен алгоритм, но вы принимаете намеки, поэтому рассмотрите этот алгоритм как подсказку:

Длина - N.

k = N/2 - 1.

1) Начните посередине и сдвиньте (путем последовательной замены соседних парных элементов) элемент в положении N/2 k помещается влево (первый раз: "1" переходит в положение 1).

2) - k. Is k == 0? Выход.

3) Сдвиг (путем замены) элемента в N/2 (первый раз: 'f' переходит в положение N-1) k помещается вправо.

4) --k.

Изменить: приведенный выше алгоритм верен, как показывает приведенный ниже код. Фактически доказывая, что это правильно, waaay вне моих возможностей, забавный маленький вопрос, хотя.

#include <iostream>
#include <algorithm>

int main(void)
{
    std::string s("abcdefghij1234567890");
    int N = s.size();
    int k = N/2 - 1;
    while (true)
    {

        for (int j=0; j<k; ++j)
        {
            int i = N/2 - j;
            std::swap(s[i], s[i-1]);
        }

        --k;

        if (k==0) break;

        for (int j=0; j<k; ++j)
        {
            int i = N/2 + j;
            std::swap(s[i], s[i+1]);
        }

        --k;
    }

   std::cout << s << std::endl;

   return 0;
}