Zadanie

• Otrzymujesz zmienny ciąg pasujący [a-z]+( [a-z]+)*.
• Musisz zmutować go do ciągu zawierającego te same słowa, ale w odwrotnej kolejności, aby „cześć wszyscy” zamieniło się w „wszyscy tam cześć”.
• Nie wolno używać więcej niż stałej ilości dodatkowej pamięci (więc nie kopiuj całego łańcucha lub jakiegokolwiek słowa do właśnie przydzielonego bufora).
• Nie ma ograniczeń czasowych. Bycie beznadziejnie nieefektywnym nie zaszkodzi twojemu wynikowi.
• Jeśli wybrany język nie pozwala na mutację łańcuchów, tablice znaków są akceptowalnym zamiennikiem.

Twój wynik

• Twój wynik jest liczony wyłącznie na podstawie liczby przypisań do elementów ciągów (najlepsze są małe wyniki). Jeśli użyjesz funkcji biblioteki, która zapisuje ciąg, jego zapisy również się liczą.
• Załóżmy, że liczba przypisań potrzebnych do wprowadzenia s wynosi n (s) . Zatem twój wynik jest maksymalny (pedantycznie, supremum) na wszystkich wejściach s (pasujących do wyrażenia regularnego określonego powyżej) n (s) / długości (s) . Jeśli nie możesz tego dokładnie obliczyć, możesz użyć najniższej górnej granicy, którą możesz udowodnić.
• Możesz zerwać remis, jeśli możesz udowodnić, że twój algorytm używa asymptotycznie mniej przydziałów (może się to zdarzyć, nawet jeśli masz ten sam wynik, patrz poniżej). Jeśli nie możesz tego zrobić, możesz zerwać remis, pokazując, że zużywasz mniej dodatkowej pamięci. Jednak pierwszy warunek rozstrzygnięcia zawsze ma pierwszeństwo.
• W przypadku niektórych danych wejściowych każda postać musi się zmienić, więc nie można zdobyć mniej niż 1.
• Mogę wymyślić prosty algorytm z wynikiem 2 (ale go nie wprowadzam).

Uwagi na temat supremy i więzi

• Supremum zbioru liczb jest najmniejszą liczbą, która nie jest mniejsza od żadnej z nich. Jest to bardzo podobne do maksimum zestawu, z tym wyjątkiem, że niektóre zestawy nieskończone, takie jak {2/3, 3/4, 4/5, 5/6, ...}, nie mają pojedynczego maksymalnego elementu, ale nadal będą miały supremum, w tym przypadku 1.
• Jeśli uda ci się „zapisać” tylko stałą liczbę zadań w moim algorytmie wyniku 2 (powiedzmy), twój wynik będzie nadal wynosił 2, ponieważ dowolnie zbliżysz się do 2, tym większy będzie twój wkład. Jeśli jednak do tego dojdzie, wygrywasz w dogrywce.

Python, wynik: 2 1,5 1,25

Jest to bezpośrednia kombinacja między odpowiedzią primo a moją odpowiedzią. Podziękowania dla niego także!

Dowód jest wciąż w toku, ale oto kod do zabawy! Jeśli możesz znaleźć przeciwny przykład wyniku większego niż 1,25 (lub jeśli występuje błąd), daj mi znać!

Obecnie najgorszym przypadkiem jest:

aa ... aa dcb ... cbd

gdzie jest dokładnie n każdej z liter „a”, „b”, „c” i „” (spacja) oraz dokładnie dwa „d”. Długość ciągu wynosi 4n + 2, a liczba zadań wynosi 5n + 2 , co daje wynik 5/4 = 1,25 .

Algorytm działa w dwóch krokach:

1. Znajdź ktakie, że string[k]i string[n-1-k]są granice słowo
2. Uruchom dowolny algorytm odwracania słów string[:k]+string[n-1-k:](tj. Łączenie pierwszego ki ostatniego kznaku) z niewielką modyfikacją.

gdzie njest długość łańcucha.

Ulepszenie, jakie daje ten algorytm, pochodzi z „małej modyfikacji” w kroku 2. Zasadniczo wiedza polega na tym, że w połączonym łańcuchu znaki w pozycji ki k+1granice słów (co oznacza, że ​​są spacjami lub pierwszym / ostatnim znakiem w słowie), dzięki czemu możemy bezpośrednio zastąpić znaki na miejscu ki k+1odpowiednim znakiem w ostatnim ciągu, zapisując kilka przypisań. To usuwa najgorszy przypadek z algorytmu odwracania słów hosta

Są przypadki, w których tak naprawdę nie możemy ich znaleźć k, w takim przypadku po prostu uruchamiamy „algorytm odwracania dowolnego słowa” na całym ciągu.

Kod długo obsługuje te cztery przypadki po uruchomieniu algorytmu odwracania słów w łańcuchu „konkatenowanym”:

1. Kiedy knie znaleziono ( f_long = -2)
2. Kiedy string[k] != ' ' and string[n-1-k] != ' '( f_long = 0)
3. Kiedy string[k] != ' ' and string[n-1-k] == ' '( f_long = 1)
4. Kiedy string[k] == ' ' and string[n-1-k] != ' '( f_long = -1)

Jestem pewien, że kod można skrócić. Obecnie jest długi, ponieważ na początku nie miałem wyraźnego obrazu całego algorytmu. Jestem pewien, że można zaprojektować go tak, aby był reprezentowany przez krótszy kod =)

Przykładowy przebieg (pierwszy to mój, drugi to primo):

Wpisz ciąg: a bc def ghij
„ghij def bc a”: 9, 13, 0,692
„ghij def bc a”: 9, 13, 0,692
Wpisz ciąg: ab cdefghijklmnopqrstuvw xyz
„zyxwvutsrqponmlkjihgf edc ab”: 50, 50, 1.000
„zyxwvutsrqponmlkjihgf edc ab”: 51, 50, 1.020
Wpisz ciąg: abcdefg hijklmnopqrstuvwx
„hijklmnopqrstuvwx gfedcb a”: 38, 31, 1.226
„hijklmnopqrstuvwx gfedcb a”: 38, 31, 1.226
Wpisz ciąg: a bc de fg hi jk lm no pq rs tu vw xy zc
„zc xy vw tu rs pq no lm jk hi fg de bc a”: 46, 40, 1.150
„zc xy vw tu rs pq no lm jk hi fg de bc a”: 53, 40, 1.325
Wprowadź ciąg znaków: aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa dcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbd
"Dcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbd aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaa A": 502, 402, 1.249
"Dcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbd aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaa A": 502, 402, 1.249

Widać, że wynik jest prawie taki sam, z wyjątkiem najgorszego przypadku algorytmu odwracania słów hosta w trzecim przykładzie, dla którego moje podejście daje wynik mniejszy niż 1,25

DEBUG = False

def find_new_idx(string, pos, char, f_start, f_end, b_start, b_end, f_long):
    if DEBUG: print 'Finding new idx for s[%d] (%s)' % (pos, char)
    if f_long == 0:
        f_limit = f_end-1
        b_limit = b_start
    elif f_long == 1:
        f_limit = f_end-1
        b_limit = b_start+1
    elif f_long == -1:
        f_limit = f_end-2
        b_limit = b_start
    elif f_long == -2:
        f_limit = f_end
        b_limit = b_start

    if (f_start <= pos < f_limit or b_limit < pos < b_end) and char == ' ':
        word_start = pos
        word_end = pos+1
    else:
        if pos < f_limit+1:
            word_start = f_start
            if DEBUG: print 'Assigned word_start from f_start (%d)' % f_start
        elif pos == f_limit+1:
            word_start = f_limit+1
            if DEBUG: print 'Assigned word_start from f_limit+1 (%d)' % (f_limit+1)
        elif b_limit <= pos:
            word_start = b_limit
            if DEBUG: print 'Assigned word_start from b_limit (%d)' % b_limit
        elif b_limit-1 == pos:
            word_start = b_limit-1
            if DEBUG: print 'Assigned word_start from b_limit-1 (%d)' % (b_limit-1)
        i = pos
        while f_start <= i <= f_limit or 0 < b_limit <= i < b_end:
            if i==f_limit or i==b_limit:
                cur_char = 'a'
            elif i!=pos:
                cur_char = string[i]
            else:
                cur_char = char
            if cur_char == ' ':
                word_start = i+1
                if DEBUG: print 'Assigned word_start from loop'
                break
            i -= 1

        if b_limit <= pos:
            word_end = b_end
            if DEBUG: print 'Assigned word_end from b_end (%d)' % b_end
        elif b_limit-1 == pos:
            word_end = b_limit
            if DEBUG: print 'Assigned word_end from b_limit (%d)' % (b_limit)
        elif pos < f_limit+1:
            word_end = f_limit+1
            if DEBUG: print 'Assigned word_end from f_limit+1 (%d)' % (f_limit+1)
        elif pos == f_limit+1:
            word_end = f_limit+2
            if DEBUG: print 'Assigned word_end from f_limit+2 (%d)' % (f_limit+2)
        i = pos
        while f_start <= i <= f_limit or 0 < b_limit <= i < b_end:
            if i==f_limit or i==b_limit:
                cur_char = 'a'
            elif i!=pos:
                cur_char = string[i]
            else:
                cur_char = char
            if cur_char == ' ':
                word_end = i
                if DEBUG: print 'Assigned word_end from loop'
                break
            i += 1
    if DEBUG: print 'start, end: %d, %d' % (word_start, word_end)
    word_len = word_end - word_start
    offset = word_start-f_start
    result = (b_end-offset-(word_end-pos)) % b_end
    if string[result] == ' ' and (b_start == -1 or result not in {f_end-1, b_start}):
        return len(string)-1-result
    else:
        return result

def process_loop(string, start_idx, f_start, f_end, b_start, b_end=-1, f_long=-2, dry_run=False):
    assignments = 0
    pos = start_idx
    tmp = string[pos]
    processed_something = False
    count = 0
    while pos != start_idx or not processed_something:
        count += 1
        if DEBUG and count > 20:
            print '>>>>>Break!<<<<<'
            break
        new_pos = find_new_idx(string, pos, tmp, f_start, f_end, b_start, b_end, f_long)
        if DEBUG:
            if dry_run:
                print 'Test:',
            else:
                print '\t',
            print 'New idx for s[%d] (%s): %d (%s)' % (pos, tmp, new_pos, string[new_pos])
        if dry_run:
            tmp = string[new_pos]
            if new_pos == dry_run:
                return True
        elif pos == new_pos:
            break
        elif tmp == string[new_pos]:
            pass
        else:
            tmp, string[new_pos] = string[new_pos], tmp
            assignments += 1
        pos = new_pos
        processed_something = True
    if dry_run:
        return False
    return assignments

def reverse(string, f_start, f_end, b_start, b_end=-1, f_long=-2):
    if DEBUG: print 'reverse: %d %d %d %d %d' % (f_start, f_end, b_start, b_end, f_long)
    if DEBUG: print
    if DEBUG: print ''.join(string)
    assignments = 0
    n = len(string)
    if b_start == -1:
        for i in range(f_start, f_end):
            if string[i] == ' ':
                continue
            if DEBUG: print 'Starting from i=%d' % i
            if any(process_loop(string, j, f_start, f_end, -1, f_end, dry_run=i) for j in range(f_start, i) if string[j] != ' '):
                continue
            if DEBUG:
                print
                print 'Finished test'
            assignments += process_loop(string, i, f_start, f_end, -1, f_end)
            if DEBUG: print
            if DEBUG: print ''.join(string)
        for i in range(f_start, (f_start+f_end-1)/2):
            if (string[i] == ' ' and string[n-1-i] != ' ') or (string[i] != ' ' and string[n-1-i] == ' '):
                string[i], string[n-1-i] = string[n-1-i], string[i]
                assignments += 2
    else:
        for i in range(f_start, f_end)+range(b_start, b_end):
            if string[i] == ' ' and i not in {f_end-1, b_start}:
                continue
            if DEBUG: print 'Starting from i=%d' % i
            if any(process_loop(string, j, f_start, f_end, b_start, b_end, f_long, i) for j in range(f_start, f_end)+range(b_start, b_end) if j<i and (string[j] != ' ' or j in {f_end-1, b_start})):
                continue
            assignments += process_loop(string, i, f_start, f_end, b_start, b_end, f_long)
            if DEBUG: print
            if DEBUG: print ''.join(string)
        for i in range(f_start, f_end-1):
            if (string[i] == ' ' and string[n-1-i] != ' ') or (string[i] != ' ' and string[n-1-i] == ' '):
                string[i], string[n-1-i] = string[n-1-i], string[i]
                assignments += 2
    return assignments

class SuperList(list):
    def index(self, value, start_idx=0):
        try:
            return self[:].index(value, start_idx)
        except ValueError:
            return -1

    def rindex(self, value, end_idx=-1):
        end_idx = end_idx % (len(self)+1)
        try:
            result = end_idx - self[end_idx-1::-1].index(value) - 1
        except ValueError:
            return -1
        return result

def min_reverse(string):
    assignments = 0
    lower = 0
    upper = len(string)
    while lower < upper:
        front = string.index(' ', lower) % (upper+1)
        back = string.rindex(' ', upper)
        while abs(front-lower - (upper-1-back)) > 1 and front < back:
            if front-lower < (upper-1-back):
                front = string.index(' ', front+1) % (upper+1)
            else:
                back = string.rindex(' ', back)
            if DEBUG: print lower, front, back, upper
        if front > back:
            break
        if DEBUG: print lower, front, back, upper
        if abs(front-lower - (upper-1-back)) > 1:
            assignments += reverse(string, lower, upper, -1)
            lower = upper
        elif front-lower < (upper-1-back):
            assignments += reverse(string, lower, front+1, back+1, upper, -1)
            lower = front+1
            upper = back+1
        elif front-lower > (upper-1-back):
            assignments += reverse(string, lower, front, back, upper, 1)
            lower = front
            upper = back
        else:
            assignments += reverse(string, lower, front, back+1, upper, 0)
            lower = front+1
            upper = back
    return assignments

def minier_find_new_idx(string, pos, char):
    n = len(string)
    try:
        word_start = pos - next(i for i, char in enumerate(string[pos::-1]) if char == ' ') + 1
    except:
        word_start = 0
    try:
        word_end = pos + next(i for i, char in enumerate(string[pos:]) if char == ' ')
    except:
        word_end = n
    word_len = word_end - word_start
    offset = word_start
    result = (n-offset-(word_end-pos))%n
    if string[result] == ' ':
        return n-result-1
    else:
        return result

def minier_process_loop(string, start_idx, dry_run=False):
    assignments = 0
    pos = start_idx
    tmp = string[pos]
    processed_something = False
    while pos != start_idx or not processed_something:
        new_pos = minier_find_new_idx(string, pos, tmp)
        #print 'New idx for s[%d] (%s): %d (%s)' % (pos, tmp, new_pos, string[new_pos])
        if pos == new_pos:
            break
        elif dry_run:
            tmp = string[new_pos]
            if new_pos == dry_run:
                return True
        elif tmp == string[new_pos]:
            pass
        else:
            tmp, string[new_pos] = string[new_pos], tmp
            assignments += 1
        pos = new_pos
        processed_something = True
    if dry_run:
        return False
    return assignments

def minier_reverse(string):
    assignments = 0
    for i in range(len(string)):
        if string[i] == ' ':
            continue
        if any(minier_process_loop(string, j, dry_run=i) for j in range(i) if string[j] != ' '):
            continue
        assignments += minier_process_loop(string, i)
    n = len(string)
    for i in range(n/2):
        if string[i] == ' ' and string[n-i-1] != ' ':
            string[i], string[n-i-1] = string[n-i-1], string[i]
            assignments += 2
        elif string[n-i-1] == ' ' and string[i] != ' ':
            string[i], string[n-i-1] = string[n-i-1], string[i]
            assignments += 2
    return assignments

def main():
    while True:
        str_input = raw_input('Enter string: ')
        string = SuperList(str_input)
        result = min_reverse(string)
        n = len(string)
        print '"%s": %d, %d, %.3f' % (''.join(string), result, n, 1.0*result/n)
        string = SuperList(str_input)
        result2 = minier_reverse(string)
        print '"%s": %d, %d, %.3f' % (''.join(string), result2, n, 1.0*result2/n)

if __name__ == '__main__':
    main()

Python, wynik: 1,5

Dokładną liczbę zadań można oszacować według wzoru:

n <= 1,5 * długość (ciąg)

w najgorszym przypadku:

abcdefghi jklmnopqrstuvwxyzzz

z 55 przypisaniami na sznurku o długości 37.

Pomysł jest podobny do mojego poprzedniego, po prostu w tej wersji próbowałem znaleźć prefiks i sufiks na granicach słów z różnicą długości co najwyżej 1. Następnie uruchamiam mój poprzedni algorytm na tym prefiksie i sufiksie (wyobraź sobie, że są one połączone) . Następnie przejdź do części nieprzetworzonej.

Na przykład w poprzednim najgorszym przypadku:

ab | ab | do

najpierw dokonamy zamiany słów na „ab” i „c” (4 przypisania), aby:

c | ab | ab

Wiemy, że na granicy była kiedyś spacja (istnieje wiele przypadków do załatwienia, ale można to zrobić), więc nie musimy kodować spacji na granicy, jest to główna poprawa w stosunku do poprzedniego algorytmu .

Następnie biegniemy na środkowych czterech postaciach, aby uzyskać:

cba ab

w sumie 8 zadań, co jest optymalne w tym przypadku, ponieważ wszystkie 8 znaków uległo zmianie.

Eliminuje to najgorszy przypadek w poprzednim algorytmie, ponieważ najgorszy przypadek w poprzednim algorytmie został wyeliminowany.

Zobacz przykładowy przebieg (i porównanie z odpowiedzią @ primo - jego to druga linia):

Wpisz ciąg: mogę zrobić wszystko
„cokolwiek mogę zrobić”: 20, 17
„cokolwiek mogę zrobić”: 17, 17
Wpisz ciąg: abcdef ghijklmnopqrs
„ghijklmnopqrs fedcb a”: 37, 25
„ghijklmnopqrs fedcb a”: 31, 25
Wpisz ciąg: abcdef ghijklmnopqrst
„ghijklmnopqrst fedcb a”: 38, 26
„ghijklmnopqrst fedcb a”: 32, 26
Wpisz ciąg: abcdefghi jklmnozzzzzzzzzzzzzzzzz
„jklmnozzzzzzzzzzzzzzzzz ihgfedcb a”: 59, 41
„jklmnozzzzzzzzzzzzzzzzz ihgfedcb a”: 45, 41
Wpisz ciąg: abcdefghi jklmnopqrstuvwxyzzz
„jklmnopqrstuvwxyzzz ihgfedcb a”: 55, 37
„jklmnopqrstuvwxyzzz ihgfedcb a”: 45, 37
Wpisz ciąg: ab ababababababac
„cababababababa ab”: 30, 30
„cababababababa ab”: 31, 30
Wpisz ciąg: ab abababababababc
„cbababababababa ab”: 32, 32
„cbababababababa ab”: 33, 32
Wpisz ciąg: abc d abc
„abc d abc”: 0, 9
„abc d abc”: 0, 9
Wpisz ciąg: abc dca
„acd abc”: 6, 9
„acd abc”: 4, 9
Wpisz ciąg: abc ababababababc
„cbabababababa abc”: 7, 29
„cbabababababa abc”: 5, 29

Odpowiedź primo jest na ogół lepsza, chociaż w niektórych przypadkach mogę mieć 1 punkt przewagi =)

Również jego kod jest znacznie krótszy niż mój, haha.

DEBUG = False

def find_new_idx(string, pos, char, f_start, f_end, b_start, b_end, f_long):
    if DEBUG: print 'Finding new idx for s[%d] (%s)' % (pos, char)
    if f_long == 0:
        f_limit = f_end-1
        b_limit = b_start
    elif f_long == 1:
        f_limit = f_end-1
        b_limit = b_start+1
    elif f_long == -1:
        f_limit = f_end-2
        b_limit = b_start
    elif f_long == -2:
        f_limit = f_end
        b_limit = b_start

    if (f_start <= pos < f_limit or b_limit < pos < b_end) and (char == ' ' or char.isupper()):
        word_start = pos
        word_end = pos+1
    else:
        if pos < f_limit+1:
            word_start = f_start
            if DEBUG: print 'Assigned word_start from f_start (%d)' % f_start
        elif pos == f_limit+1:
            word_start = f_limit+1
            if DEBUG: print 'Assigned word_start from f_limit+1 (%d)' % (f_limit+1)
        elif b_limit <= pos:
            word_start = b_limit
            if DEBUG: print 'Assigned word_start from b_limit (%d)' % b_limit
        elif b_limit-1 == pos:
            word_start = b_limit-1
            if DEBUG: print 'Assigned word_start from b_limit-1 (%d)' % (b_limit-1)
        i = pos
        if not (i < f_limit and b_limit < i):
            i -= 1
        while f_start <= i < f_limit or 0 < b_limit < i < b_end:
            if i!=pos:
                cur_char = string[i]
            else:
                cur_char = char
            if cur_char == ' ' or cur_char.isupper():
                word_start = i+1
                if DEBUG: print 'Assigned word_start from loop'
                break
            i -= 1

        if b_limit <= pos:
            word_end = b_end
            if DEBUG: print 'Assigned word_end from b_end (%d)' % b_end
        elif b_limit-1 == pos:
            word_end = b_limit
            if DEBUG: print 'Assigned word_end from b_limit (%d)' % (b_limit)
        elif pos < f_limit+1:
            word_end = f_limit+1
            if DEBUG: print 'Assigned word_end from f_limit+1 (%d)' % (f_limit+1)
        elif pos == f_limit+1:
            word_end = f_limit+2
            if DEBUG: print 'Assigned word_end from f_limit+2 (%d)' % (f_limit+2)
        i = pos
        if not (i < f_limit and b_limit < i):
            i += 1
        while f_start <= i < f_limit or 0 < b_limit < i < b_end:
            if i!=pos:
                cur_char = string[i]
            else:
                cur_char = char
            if cur_char == ' ' or cur_char.isupper():
                word_end = i
                if DEBUG: print 'Assigned word_end from loop'
                break
            i += 1
    if DEBUG: print 'start, end: %d, %d' % (word_start, word_end)
    word_len = word_end - word_start
    offset = word_start-f_start
    return (b_end-offset-(word_end-pos)) % b_end

def process_loop(string, start_idx, f_start, f_end, b_start, b_end=-1, f_long=-2, dry_run=False):
    assignments = 0
    pos = start_idx
    tmp = string[pos]
    processed_something = False
    count = 0
    while pos != start_idx or not processed_something:
        count += 1
        if count > 20:
            if DEBUG: print 'Break!'
            break
        new_pos = find_new_idx(string, pos, tmp, f_start, f_end, b_start, b_end, f_long)
        #if dry_run:
        #    if DEBUG: print 'Test:',
        if DEBUG: print 'New idx for s[%d] (%s): %d (%s)' % (pos, tmp, new_pos, string[new_pos])
        if pos == new_pos:
            break
        elif dry_run:
            tmp = string[new_pos]
            if new_pos == dry_run:
                return True
        elif tmp == string[new_pos]:
            pass
        elif tmp == ' ':
            if b_start!=-1 and new_pos in {f_end-1, b_start}:
                tmp, string[new_pos] = string[new_pos], tmp
            else:
                tmp, string[new_pos] = string[new_pos], '@'
            assignments += 1
        elif string[new_pos] == ' ':
            if b_start!=-1 and new_pos in {f_end-1, b_start}:
                tmp, string[new_pos] = string[new_pos], tmp
            else:
                tmp, string[new_pos] = string[new_pos], tmp.upper()
            assignments += 1
        else:
            tmp, string[new_pos] = string[new_pos], tmp
            assignments += 1
        pos = new_pos
        processed_something = True
    if dry_run:
        return False
    return assignments

def reverse(string, f_start, f_end, b_start, b_end=-1, f_long=-2):
    if DEBUG: print 'reverse: %d %d %d %d %d' % (f_start, f_end, b_start, b_end, f_long)
    if DEBUG: print
    if DEBUG: print ''.join(string)
    assignments = 0
    if b_start == -1:
        for i in range(f_start, (f_start+f_end)/2):
            if DEBUG: print 'Starting from i=%d' % i
            if any(process_loop(string, j, f_start, f_end, -1, f_end, dry_run=i) for j in range(f_start, i)):
                continue
            assignments += process_loop(string, i, f_start, f_end, -1, f_end)
            if DEBUG: print
            if DEBUG: print ''.join(string)
    else:
        for i in range(f_start, f_end):
            if DEBUG: print 'Starting from i=%d' % i
            if any(process_loop(string, j, f_start, f_end, b_start, b_end, f_long, i) for j in range(f_start, i)):
                continue
            assignments += process_loop(string, i, f_start, f_end, b_start, b_end, f_long)
            if DEBUG: print
            if DEBUG: print ''.join(string)
    for i in range(len(string)):
        if string[i] == '@':
            string[i] = ' '
            assignments += 1
        if string[i].isupper():
            string[i] = string[i].lower()
            assignments += 1
    return assignments

class SuperList(list):
    def index(self, value, start_idx=0):
        try:
            return self[:].index(value, start_idx)
        except ValueError:
            return -1

    def rindex(self, value, end_idx=-1):
        end_idx = end_idx % (len(self)+1)
        try:
            result = end_idx - self[end_idx-1::-1].index(value) - 1
        except ValueError:
            return -1
        return result

def min_reverse(string):
    # My algorithm
    assignments = 0
    lower = 0
    upper = len(string)
    while lower < upper:
        front = string.index(' ', lower) % (upper+1)
        back = string.rindex(' ', upper)
        while abs(front-lower - (upper-1-back)) > 1 and front < back:
            if front-lower < (upper-1-back):
                front = string.index(' ', front+1) % (upper+1)
            else:
                back = string.rindex(' ', back)
            if DEBUG: print lower, front, back, upper
        if front > back:
            break
        if DEBUG: print lower, front, back, upper
        if abs(front-lower - (upper-1-back)) > 1:
            assignments += reverse(string, lower, upper, -1)
            lower = upper
        elif front-lower < (upper-1-back):
            assignments += reverse(string, lower, front+1, back+1, upper, -1)
            lower = front+1
            upper = back+1
        elif front-lower > (upper-1-back):
            assignments += reverse(string, lower, front, back, upper, 1)
            lower = front
            upper = back
        else:
            assignments += reverse(string, lower, front, back+1, upper, 0)
            lower = front+1
            upper = back
    return assignments

def minier_find_new_idx(string, pos, char):
    n = len(string)
    try:
        word_start = pos - next(i for i, char in enumerate(string[pos::-1]) if char == ' ') + 1
    except:
        word_start = 0
    try:
        word_end = pos + next(i for i, char in enumerate(string[pos:]) if char == ' ')
    except:
        word_end = n
    word_len = word_end - word_start
    offset = word_start
    result = (n-offset-(word_end-pos))%n
    if string[result] == ' ':
        return n-result-1
    else:
        return result

def minier_process_loop(string, start_idx, dry_run=False):
    assignments = 0
    pos = start_idx
    tmp = string[pos]
    processed_something = False
    while pos != start_idx or not processed_something:
        new_pos = minier_find_new_idx(string, pos, tmp)
        #print 'New idx for s[%d] (%s): %d (%s)' % (pos, tmp, new_pos, string[new_pos])
        if pos == new_pos:
            break
        elif dry_run:
            tmp = string[new_pos]
            if new_pos == dry_run:
                return True
        elif tmp == string[new_pos]:
            pass
        else:
            tmp, string[new_pos] = string[new_pos], tmp
            assignments += 1
        pos = new_pos
        processed_something = True
    if dry_run:
        return False
    return assignments

def minier_reverse(string):
    # primo's answer for comparison
    assignments = 0
    for i in range(len(string)):
        if string[i] == ' ':
            continue
        if any(minier_process_loop(string, j, dry_run=i) for j in range(i) if string[j] != ' '):
            continue
        assignments += minier_process_loop(string, i)
    n = len(string)
    for i in range(n/2):
        if string[i] == ' ' and string[n-i-1] != ' ':
            string[i], string[n-i-1] = string[n-i-1], string[i]
            assignments += 2
        elif string[n-i-1] == ' ' and string[i] != ' ':
            string[i], string[n-i-1] = string[n-i-1], string[i]
            assignments += 2
    return assignments

def main():
    while True:
        str_input = raw_input('Enter string: ')
        string = SuperList(str_input)
        result = min_reverse(string)
        print '"%s": %d, %d' % (''.join(string), result, len(string))
        string = SuperList(str_input)
        result2 = minier_reverse(string)
        print '"%s": %d, %d' % (''.join(string), result2, len(string))

if __name__ == '__main__':
    main()

Python, wynik: asymptotycznie 2, w normalnym przypadku znacznie mniej

stary kod został usunięty z powodu ograniczenia miejsca

Chodzi o iterację po każdym indeksie, a dla każdego indeksu ibierzemy postać, obliczamy nową pozycję j, zapamiętujemy znak na pozycji j, przypisujemy znak ido ji powtarzamy ze znakiem na indeksie j. Ponieważ potrzebujemy informacji o spacji, aby obliczyć nową pozycję, koduję starą spację jako wielką wersję nowej litery, a nową spację jako „@”.

Perl, wynik 1,3̅

Dla każdego znaku spacji wykonywane jest jedno przypisanie, a dla każdego znaku spacji dwa przypisania. Ponieważ znaki spacji nie mogą przekraczać połowy całkowitej liczby znaków, najgorszy wynik to 1,5 .

Algorytm się nie zmienił, ale mogę udowodnić dolną górną granicę. Dokonajmy dwóch spostrzeżeń:

1. Przestrzenie bezpośrednio naprzeciwko nie muszą być zamieniane.
2. Słowa jednoznakowe bezpośrednio naprzeciwko spacji nie są zamieniane podczas fazy głównej, ale tylko raz na końcu.

Można wtedy zobaczyć, że teoretyczny „najgorszy przypadek” z asymptotycznie 1/2 spacjami wcale nie jest najgorszy: ab c d e f g h i ...

$ echo ab c d e f g h i j k l m n o p q r s t u v w x y z|perl reverse-inplace.pl
z y x w v u t s r q p o n m l k j i h g f e d c ab
swaps: 51; len: 50
ratio: 1.02

W rzeczywistości jest to całkiem niezły przypadek.

Aby zapobiec obserwacji pierwszego i drugiego powyżej, każde słowo składające się z jednego znaku musiałoby zostać umieszczone w środku słowa o długości trzech lub więcej znaków. Sugerowałoby to najgorszy przypadek zawierający asymptotycznie 1/3 spacji:a bcd a bcd a ... bc

$ echo a bcd a bcd a bcd a bcd a bcd a bc|perl reverse-inplace.pl
bc a bcd a bcd a bcd a bcd a bcd a
swaps: 45; len: 34
ratio: 1.32352941176471

Lub równoważnie tylko słowa dwuznakowe: a bc de fg hi jk ...

$ echo a bc de fg hi jk lm no pq rs tu vx xy|perl reverse-inplace.pl
xy vx tu rs pq no lm jk hi fg de bc a
swaps: 49; len: 37
ratio: 1.32432432432432

Ponieważ najgorszy przypadek zawiera asymptotycznie 1/3 spacji, najgorszy wynik wynosi 1,3̅ .

#!perl -l
use warnings;

$words = <>;
chomp($words);
$len = length($words);
$words .= ' ';
$spaces = 0;
# iterate over the string, count the spaces
$spaces++ while $words =~ m/ /g;

$origin = 0;
$o = vec($words, $origin, 8);
$cycle_begin = $origin;
$swaps = 0;

# this possibly terinates one iteration early,
# if the last char is a one-cycle (i.e. moves to its current location)
# one-cycles previous to the last are iterated, but not swapped.
while ($i++ < $len - $spaces || !$was_cycle) {
  $w_start = rindex($words, ' ', $origin);
  $w_end = index($words, ' ', $origin);
  $pos = ($origin - $w_start) - 1;
  $target = $len - ($w_end - $pos);
  $t = vec($words, $target, 8);

  if ($t == 32) {
    $target = $len - $target - 1;
    $t = vec($words, $target, 8);
  }

  # char is already correct, possibly a one-cycle
  if ($t != $o) {
    $swaps += 1;
    vec($words, $target, 8) = $o;
  }

  $origin = $target;
  $o = $t;
  if ($origin == $cycle_begin) {
    if ($i < $len - $spaces) {
      # backtrack through everything we've done up to this point
      # to find the next unswapped char ...seriously.
      $origin += 1;
      if (vec($words, $origin, 8) == 32) {
        $origin += 1;
      }
      $bt_origin = 0;
      $bt_cycle_begin = 0;
      while ($bt_cycle_begin < $origin) {
        $w_start = rindex($words, ' ', $bt_origin);
        $w_end = index($words, ' ', $bt_origin);
        $pos = ($bt_origin - $w_start) - 1;
        $target = $len - ($w_end - $pos);
        $t = vec($words, $target, 8);

        if ($t == 32) {
          $target = $len - $target - 1;
          $t = vec($words, $target, 8);
        }

        if ($target == $bt_cycle_begin) {
          $bt_origin = ++$bt_cycle_begin;
          if (vec($words, $bt_origin, 8) == 32) {
            $bt_origin = ++$bt_cycle_begin;
          }
        } else {
          $bt_origin = $target;
        }

        if ($target == $origin) {
          $origin += 1;
          if (vec($words, $origin, 8) == 32) {
            $origin += 1;
          }
          $bt_origin = $bt_cycle_begin = 0;
        }
      }
    }

    $cycle_begin = $origin;
    $o = vec($words, $origin, 8);
    $was_cycle = 1;
  } else {
    $was_cycle = 0;
  }
}

for $i (0..$len/2-1) {
  $mirror = $len - $i - 1;
  $o = vec($words, $i, 8);
  $m = vec($words, $mirror, 8);
  # if exactly one is a space...
  if (($o == 32) ^ ($m == 32)) {
    $swaps += 2;
    vec($words, $mirror, 8) = $o;
    vec($words, $i, 8) = $m;
  }
}

chop($words);
print $words;
print "swaps: $swaps; len: $len";
print 'ratio: ', $swaps/$len;

Edycja: Dodano licznik swapów i współczynnik.

Dane wejściowe są pobierane ze standardowego wejścia. Przykładowe użycie:

$ echo where in the world is carmen sandiego|perl reverse-inplace.pl
sandiego carmen is world the in where
swaps: 35; len: 37
ratio: 0.945945945945946

metoda

Aby rozpocząć, pierwszy znak ciągu zostaje przeniesiony do miejsca docelowego. Właśnie zastąpiona postać jest następnie przenoszona do miejsca docelowego itp. Trwa to do momentu spełnienia jednego z dwóch warunków:

1. Postać powinna zostać zamieniona spacją.
   Kiedy tak się dzieje, postać jest nie zamieniana z przestrzenią, ale raczej na pozycję lustrzaną przestrzeni. Algorytm kontynuuje od tej pozycji.
2. Cykl został osiągnięty.
   Gdy cel powróci do początkowej pozycji bieżącego cyklu, należy znaleźć następny niezmieniony znak (a raczej każdy niezamieniony znak). Aby to zrobić przy stałych ograniczeniach pamięci, wszystkie zamiany dokonane do tego momentu są śledzone wstecz.

Po tej fazie każda postać niebędąca spacją została przesunięta co najwyżej raz. Aby zakończyć, wszystkie znaki spacji są zamieniane na znaki w ich pozycjach lustrzanych, co wymaga dwóch operacji przypisania na spację.

Ruby, ocena 2

Na początek bardzo podstawowy algorytm. Najpierw odwraca cały ciąg, a następnie ponownie odwraca każde słowo w ciągu. W najgorszym przypadku (jedno słowo, parzysta liczba znaków) wynik wynosi 2.

def revstring(s, a, b)
  while a<b
    h = s[a]
    s[a] = s[b]
    s[b] = h
    a += 1
    b -= 1
  end
  s
end

def revwords(s)
  revstring(s, 0, s.length-1)
  a = 0
  while a<s.length
    b = a+1
    b += 1 while b<s.length and s[b]!=" "
    revstring(s, a, b-1)
    a = b+1
  end
  s
end

Stosowanie:

> revwords("hello there everyone")
"everyone there hello"

C ++: wynik 2

#include<iostream>
#include<algorithm>

void rev(std::string& s)
{
    std::reverse(s.begin(),s.end());
    std::string::iterator i=s.begin(),j=s.begin();
    while(i!=s.end())
    {
        while(i!=s.end()&&(*i)==' ')
            i++;
        j=i;
        while(i!=s.end()&&(*i)!=' ')
            i++;
        std::reverse(j,i);
    }
}

int main()
{
    std::string s;
    getline(std::cin,s);
    rev(s);
    std::cout<<s;
}

Rebol

reverse-words: function [
    "Reverse the order of words. Modifies and returns string (series)"
    series [string!] "At position (modified)"
  ][
    first-time: on
    until [
        reverse/part series f: any [
            if first-time [tail series]
            find series space
            tail series
        ]
        unless first-time [series: next f]
        first-time: off
        tail? series
    ]

    series: head series
]

Nie jestem pewien co do punktacji w tym zakresie. W tym kodzie nie ma bezpośredniego przypisania ciągu. Wszystko jest obsługiwane przez ten, reverse/partktóry dokonuje cofania w miejscu wewnątrz i początkowo na całym łańcuchu.

Niektóre szczegóły dotyczące kodu:

• Pętlę przez string ( series), aż dojdzie dotail?

• Pierwszy raz w pętli wykonaj pełne odwrócenie łańcucha - reverse/part series tail series(który jest taki sam jakreverse series )

• Następnie odwróć każde słowo znalezione w kolejnych iteracjach - reverse/part series find series space

• Gdy wyczerpane słowo znajdzie, następnie wróć, tail seriesaby odwrócić ostatnie słowo w ciągu -reverse/part series tail series

Rebol umożliwia przemierzanie łańcucha za pomocą wewnętrznego wskaźnika . Możesz to zobaczyć w series: next f(przesuń wskaźnik na za spacją, więc początek następnego słowa) iseries: head series (resetuje wskaźnik z powrotem do głowy).

Widzieć uzyskać więcej informacji, Seria .

Przykład użycia w konsoli Rebol:

>> reverse-words "everyone there hello"
== "hello there everyone"

>> x: "world hello"
== "world hello"

>> reverse-words x
== "hello world"

>> x
== "hello world"

>> reverse-words "hello"
== "hello"

C: Wynik 2

To tylko odwraca cały łańcuch, a następnie odwraca każde słowo.

#include <stdio.h>
#include <string.h>

void reverse(char *s,unsigned n){
    char c;
    unsigned i=0,r=1;
    while(i < n){ //no swap function in C 
        c=s[i];
        s[i++]=s[n];
        s[n--]=c;
    }
}

unsigned wordlen(char *s){
    unsigned i=0;
    while (s[i] != ' ' && s[i]) ++i;
    return i;
}

int main(int argc, char **argv) {
    char buf[]="reverse this also";
    char *s=buf;
    unsigned wlen=0,len=strlen(s)-1;
    reverse(s,len);  //reverse entire string
    while(wlen<len){  // iterate over each word till end of string
      wlen=wordlen(s);
      reverse(s,wlen-1);
      s+=wlen+1;
      len-=wlen;
    }
    printf("%s\n",buf);
    return 0;
}

Python: wynik 2

Prawie identyczny z algorytmem Howarda, ale wykonuje kroki odwrotne w odwrotnej kolejności (najpierw odwraca słowa, a następnie odwraca cały łańcuch). Dodatkowa pamięć stosuje się 3 zmienne bajt rozmiar: i, j, it . Techniczniefind i lenużywają niektórych zmiennych wewnętrznych, ale równie dobrze mogłyby ponownie użyć ilubj bez utraty funkcji.

szybka edycja: zapisywanie przypisań ciągów poprzez zamianę tylko wtedy, gdy znaki się różnią, więc mogę zdobyć dodatkowe punkty z uwagi nr 2.

from sys import stdin

def word_reverse(string):
    # reverse each word
    i=0
    j=string.find(' ')-1
    if j == -2: j=len(string)-1
    while True:
        while i<j:
            if string[i] != string[j]:
                t = string[i]
                string[i] = string[j]
                string[j] = t
            i,j = i+1,j-1
        i=string.find(' ', i)+1
        if i==0: break
        j=string.find(' ', i)-1
        if j == -2: j=len(string)-1
    # reverse the entire string
    i=0
    j=len(string)-1
    while i<j:
        if string[i] != string[j]:
            t = string[i]
            string[i] = string[j]
            string[j] = t
        i,j = i+1,j-1
    return string

for line in stdin.readlines():
    # http://stackoverflow.com/a/3463789/1935085
    line = line.strip() # no trailing newlines ore spaces to ensure it conforms to '[a-z]+( [a-z]+)*'
    print word_reverse(bytearray(line))

Partia

Przyznaję, że nie do końca rozumiem punktację (myślę, że to dwa) .. ale powiem - robi to .

@echo off

setLocal enableDelayedExpansion
set c=
set s=

for %%a in (%~1) do set /a c+=1 & echo %%a >> f!c!

for /L %%a in (!c!, -1, 1) do (
    set /p t=<f%%a
    set s=!s!!t!
    del f%%a
)

echo !s!

Dane wejściowe są traktowane jako pierwsza standardowa wartość wejściowa, dlatego muszą być otoczone znakami cudzysłowu -
wywołanie:script.bat "hello there everyone"
out:everyone there hello .

Może ktoś inny może mnie zdobyć (zakładając, że nie zdyskwalifikowałem się w inny sposób).

JavaScript

function reverseWords(input) {
    if (input.match(/^[a-z]+( [a-z]+)*$/g)) {
        return input.split(' ').reverse().join(' ');
    }
}

Stosowanie:

> reverseWords('hello there everyone');
'everyone there hello'

Mam dziwne wrażenie, że coś przeoczyłem ...