In-luogo interleaving delle due metà di una stringa

Question

Data una serie di anche dimensioni, dicono:

abcdef123456 

Come avrei interleave le due metà, in modo tale che la stessa stringa sarebbe diventato questo :

a1b2c3d4e5f6 

Ho provato a provare a sviluppare un algoritmo, ma non ci sono riuscito. Qualcuno mi darebbe qualche suggerimento su come procedere? Devo farlo senza creare variabili o array di string aggiuntivi. Una o due variabili vanno bene.

Solo che non voglio un codice funzionante (o algoritmo), ho bisogno di sviluppare un algoritmo e dimostrarlo matematicamente correttezza.

Answer 1

OK consente di ricominciare. Ecco cosa faremo:

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 

Ecco un esempio di ciò che il programma sta per fare. Utilizzeremo le variabili i, j, k. i e j corrisponderanno rispettivamente al limite inferiore e superiore, dove k sarà l'indice al quale scambiamo.

Esempio

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

Quanto a dimostrare la correttezza del programma, vedere questo link. Spiega come dimostrare che questo è corretto per mezzo di un ciclo invariante.

Una prova ruvida sarebbe il seguente:

1. Inizializzazione: Prima della prima iterazione del ciclo possiamo vedere che i è impostato (length(string)/2) - 1. Possiamo vedere che i < = lunghezza (stringa) prima di entrare nel ciclo.
2. Manutenzione. Dopo ogni iterazione, i viene decrementato (i = i-1, i=i-2,...) e deve essere presente un punto al quale .
3. Terminazione: poiché i è una sequenza decrescente di numeri interi positivi, il ciclo invariante i > 0 alla fine equivarrà a falso e il ciclo uscirà.

Answer 2

La soluzione è qui J. Ellis e M. Markov. In-situ, fusione stabile per mezzo di una perfetta fusione. The Computer Journal. 43 (1): 40-53, (2000).

puoi anche consultare i vari dibattiti qui:

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

OK, ecco una bozza di massima.Tu dici che non si limitano a voler un algoritmo, ma si sta prendendo suggerimenti, in modo da considerare questo algoritmo un suggerimento:

lunghezza è N.

k = N/2 - 1.

1) Inizia nel mezzo e sposta (per lo scambio successivo di elementi di coppia adiacenti) l'elemento in posizione N/2 k si posiziona a sinistra (prima volta: '1' va in posizione 1).

2) --k. È k == 0? Smettere.

3) Spostare (scambiando) l'elemento su N/2 (1a volta: 'f' va in posizione N-1) k posiziona a destra.

4) --k.

Modifica: l'algoritmo sopra riportato è corretto, come illustrato nel seguente codice. In realtà dimostrando che è corretto è mooolto oltre le mie capacità, divertente piccola domanda però.

#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

Genericamente che il problema è molto difficile - e riduce di trovare cicli di permutazione. Il numero e la lunghezza di questi varia molto a seconda della lunghezza.

Il primo e l'ultimo cicli sono sempre degeneri; la matrice 10 voce ha 2 cicli di lunghezze 6 e 2 e l'entrata matrice 12 presenta un unico ciclo di lunghezza 10.

withing un ciclo si fa:

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

Anche se la funzione successiva possono essere implementate come una formula relativamente facile di N, il problema viene posticipato per fare contabilità contabile di quali indici sono stati scambiati. Nel caso a sinistra di 10 voci, si dovrebbe [rapidamente] trovare le posizioni iniziali dei cicli (sono ad esempio 1 e 3).

Answer 5

Si può essere in grado di farlo in O (N * log (N)) tempo:

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 

Implementazione in 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; 
} 

uscita (ideone):

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