In-nơi interleaving của hai nửa của một chuỗi

Question

Cho một chuỗi các thậm chí kích thước, nói:

abcdef123456 

Làm thế nào tôi sẽ interleave hai nửa, như vậy mà cùng chuỗi sẽ trở thành này :

a1b2c3d4e5f6 

Tôi đã cố gắng phát triển thuật toán nhưng không thể. Có ai cho tôi một số gợi ý về cách tiến hành không? Tôi cần phải làm điều này mà không cần tạo thêm các biến chuỗi hoặc mảng. Một hoặc hai biến là tốt.

Tôi chỉ không muốn một mã làm việc (hoặc thuật toán), tôi cần phát triển một thuật toán và chứng minh tính chính xác về mặt toán học.

Answer 1

Ok cho phép bắt đầu lại. Dưới đây là những gì chúng tôi sẽ làm:

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 

Dưới đây là ví dụ về chương trình sẽ thực hiện. Chúng tôi sẽ sử dụng các biến số i, j, k. i và j sẽ là giới hạn dưới và trên tương ứng, trong đó k sẽ là chỉ mục mà tại đó chúng tôi trao đổi.

Ví dụ

`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 với chứng minh chương trình đúng đắn, xem link này. Nó giải thích làm thế nào để chứng minh điều này là chính xác bằng phương tiện của một bất biến vòng lặp.

Một bằng chứng thô sẽ là như sau:

1. Khởi tạo: Trước khi phiên đầu tiên của vòng lặp chúng ta có thể thấy rằng i được thiết lập để (length(string)/2) - 1. Chúng ta có thể thấy rằng tôi < = chiều dài (chuỗi) trước khi chúng ta nhập vòng lặp.
2. Bảo trì. Sau mỗi lần lặp lại, i bị giảm (i = i-1, i=i-2,...) và phải có một điểm tại đó i<length(string).
3. Chấm dứt: Vì i là một chuỗi giảm số nguyên dương, vòng lặp bất biến i > 0 cuối cùng sẽ tương đương với sai và vòng lặp sẽ thoát.

Answer 2

Giải pháp ở đây J. Ellis và M. Markov. Tại chỗ, ổn định sáp nhập bằng cách hoàn hảo shu ffl e. Tạp chí máy tính. 43 (1): 40-53, (2000).

Xem thêm các cuộc thảo luận khác nhau ở đây:

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.

Answer 3

Được rồi, đây là bản nháp thô.Bạn nói rằng bạn không chỉ muốn một thuật toán, nhưng bạn đang dùng những gợi ý, nên xem xét thuật toán này là một gợi ý:

Chiều dài là N.

k = N/2 - 1.

1) Bắt đầu ở giữa, và dịch chuyển (bằng cách hoán đổi liên tiếp các phần tử cặp lân cận) phần tử ở vị trí N/2 k ở bên trái (lần đầu tiên: '1' chuyển đến vị trí 1).

2) --k. Là k == 0? Bỏ đi.

3) Shift (bằng cách hoán đổi) phần tử tại N/2 (lần đầu tiên: 'f' chuyển đến vị trí N-1) k đặt ở bên phải.

4) --k.

Chỉnh sửa: Thuật toán trên là chính xác, như mã bên dưới hiển thị. Trên thực tế chứng minh rằng nó là chính xác là waaay ngoài khả năng của tôi, câu hỏi nhỏ vui vẻ mặc dù.

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

Answer 4

quát vấn đề đó là khá khó khăn - và nó làm giảm việc tìm chu kỳ hoán vị. Số lượng và độ dài của những thay đổi khá nhiều tùy thuộc vào độ dài.

Chu trình đầu tiên và cuối cùng luôn luôn biến đổi; mảng 10 entry có 2 chu kỳ có độ dài 6 và 2 và các mảng nhập 12 có một chu trình đơn có độ dài 10

Withing một chu kỳ một trong những hiện:

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

Mặc dù chức năng tiếp theo có thể được thực hiện như một số công thức tương đối dễ dàng của N, vấn đề được hoãn lại để làm kế toán sách của những chỉ số nào đã được hoán đổi. Trong trường hợp 10 mục nhập bên trái, bạn nên [nhanh chóng] tìm vị trí bắt đầu của các chu kỳ (ví dụ: 1 và 3).

Answer 5

Bạn có thể làm điều đó trong thời gian O (N * log (N)) thời gian:

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 

thực hiện trong 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<>(){}[]/\