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

Учитывая строку четного размера, скажем:

abcdef123456 

Как бы я чередовал две половины, чтобы одна и та же строка стала такой:

 a1b2c3d4e5f6 

Я попытался разработать алгоритм, но не смог. Кто-нибудь даст мне несколько советов о том, как действовать? Мне нужно сделать это, не создавая дополнительных строковых переменных или массивов. Одна или две переменные в порядке.

Мне просто не нужен рабочий код (или алгоритм), мне нужно разработать алгоритм и математически доказать его правильность.

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

 Want: abcdefgh12345678 -> a1b2c3d4e5f6g7h8 abcdefgh 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  #include  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; } 

Выход ( идеал ):

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

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

Циклы для перемежения на месте для 10 и 12 входных массивов

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

С циклом:

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

Несмотря на то, что следующая функция может быть реализована как некоторая относительно простая формула N, проблема откладывается, чтобы делать бухгалтерский учет того, какие индексы были заменены. В левом случае из 10 записей следует [быстро] найти начальные позиции циклов (они, например, 1 и 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` 

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

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

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

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

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

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

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

Длина – N.

k = N / 2 – 1.

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

2) -k. Is k == 0? Уволиться.

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

4) –k.

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

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