Обратный порядок слов в строке на месте

17

Задание

  • Вам дана изменяемая строка, которая соответствует [a-z]+( [a-z]+)*.
  • Вы должны преобразовать его в строку, содержащую те же слова, но в обратном порядке, чтобы «всем привет всем» стало «всем привет».
  • Вам не разрешается использовать больше, чем постоянный объем дополнительной памяти (поэтому не следует копировать всю строку или любое целое слово в только что выделенный буфер).
  • Там нет ограничений по времени. Быть безнадежно неэффективным не повредит вашему счету.
  • Если выбранный вами язык не допускает мутации строк, массивы символов являются приемлемой заменой.

Твой счет

  • Ваша оценка рассчитывается исключительно по количеству назначений, которые вы делаете для строковых элементов (маленькие оценки лучше всего). Если вы используете библиотечную функцию, которая записывает в строку, ее число также учитывается.
  • Предположим, количество назначений, которые вам нужны для ввода s, равно n (s) . Тогда ваш результат является максимальным (педантично, супремум) по всем входам s (соответствует регулярному выражению, указанному выше), равному n (s) / length (s) . Если вы не можете рассчитать это точно, вы можете использовать нижнюю верхнюю границу, которую вы можете доказать.
  • Вы можете разорвать ничью, если докажете, что ваш алгоритм использует асимптотически меньшее количество назначений (это может произойти, даже если у вас одинаковый счет, см. Ниже). Если вы не можете сделать это, вы можете разорвать связь, показав, что вы используете меньше дополнительной памяти. Однако первое условие разрыва связи всегда имеет приоритет.
  • Для некоторых входных данных каждый символ должен измениться, поэтому невозможно набрать меньше 1.
  • Я могу придумать простой алгоритм со счетом 2 (но я не вхожу в него).

Заметки о супреме и связях

  • Супремум набора чисел - это наименьшее число, которое не меньше любого из них. Это очень похоже на максимум набора, за исключением того, что некоторые бесконечные наборы, такие как {2/3, 3/4, 4/5, 5/6, ...}, не имеют единственного элемента максимума, но все равно будут иметь супремум, в этом случае 1.
  • Если вам удастся «сохранить» только постоянное количество назначений по моему алгоритму оценки 2 (скажем), ваша оценка все равно будет 2, потому что вы будете сколь угодно приближаться к 2, чем больше будет ваш ввод. Тем не менее, вы выиграете на тай-брейке, если до этого дойдет.
code-challenge Бен Милвуд
источник
1
Мне было бы немного грустно, если бы все это сводилось к тому, что результаты их использования памяти были разрушены. Я в основном отвечал на этот вопрос, задаваясь вопросом, сможет ли кто-нибудь забить меньше 2.
Бен Милвуд
1
У меня нет формальных доказательств, но моя интуиция говорит мне, что с ограничением на постоянное пространство невозможно сделать лучше, чем 2. Если вы будете считать только объявления переменных для пробела, я мог бы обмануть и сделать рекурсивную функцию. но это только маскирует little-omega(1)пространство, помещая его в стек.
Мину
2
@bacchusbeale да, но это постоянная дополнительная память.
Мартин Эндер
4
Если вы строго соблюдаете правила, то написать такую ​​программу невозможно. Строка может быть произвольной длины, и вам понадобится хотя бы какая-то переменная, которая хранит индекс. Поэтому мне просто нужно сделать строку достаточно длинной, чтобы выйти за границы вашей переменной. Для успешного хранения хотя бы одного индекса ваша необходимая память будет увеличиваться с длиной строки.
IchBinKeinBaum
3
@IchBinKeinBaum прав, выполнить эту задачу с O(1)дополнительным пространством невозможно . Вам нужно O(log n)место для хранения позиции индекса, поскольку k-битное целое число может хранить в них только строки длиной до 2^k. Ограничение длины строк делает задачу довольно бессмысленной, так как каждый алгоритм требует O(1)места таким образом.
Денис

Ответы:

4

Python, оценка: 2 1,5 1,25

Это прямой комбинация ответа Примо и моего ответа. Так что кредиты ему тоже!

Доказательство еще в процессе, но вот код для игры! Если вы можете найти встречный пример оценки выше 1,25 (или если есть ошибка), дайте мне знать!

В настоящее время худший случай:

аа ... аа dcb ... cbd

где каждая буква «a», «b», «c» и «» (пробел) содержит ровно n букв, и ровно две буквы «d». Длина строки - 4n + 2, а количество назначений - 5n + 2 , что дает оценку 5/4 = 1,25. .

Алгоритм работает в два этапа:

  1. Найти kтакое что string[k]иstring[n-1-k] являются границами слова
  2. Запустить любой алгоритм обращения слов string[:k]+string[n-1-k:](т.е. объединение первого kи последнего kсимволов) с небольшой модификацией.

где nдлина строки.

Улучшение, которое дает этот алгоритм, происходит от «малой модификации» на шаге 2. По сути, это знание того, что в объединенной строке символы в позиции kи k+1границы слова (что означает, что они являются пробелами или первым / последним символом в слове), и поэтому мы можем напрямую заменить символы в позиции kи k+1соответствующими символами в последней строке, сохранив несколько назначений.Это удаляет наихудший случай из алгоритма обращения слов хоста

Существуют случаи, когда мы не можем на самом деле найти такое k, в этом случае мы просто запускаем «алгоритм обращения любого слова» для всей строки.

Код длинен, чтобы обрабатывать эти четыре случая при запуске алгоритма обращения слов в «объединенной» строке:

  1. Когда kне найден ( f_long = -2)
  2. Когда string[k] != ' ' and string[n-1-k] != ' '( f_long = 0)
  3. Когда string[k] != ' ' and string[n-1-k] == ' '( f_long = 1)
  4. Когда string[k] == ' ' and string[n-1-k] != ' '( f_long = -1)

Я уверен, что код может быть сокращен. В настоящее время это долго, потому что у меня не было четкой картины всего алгоритма в начале. Я уверен, что можно разработать его так, чтобы он был представлен более коротким кодом =)

Примерный прогон (первый мой, второй - primo):

Введите строку: bc def ghij
"ghij def bc a": 9, 13, 0,692
"ghij def bc a": 9, 13, 0,692
Введите строку: ab cdefghijklmnopqrstuvw xyz
"zyxwvutsrqponmlkjihgf edc ab": 50, 50, 1.000
"zyxwvutsrqponmlkjihgf edc ab": 51, 50, 1.020
Введите строку: abcdefg hijklmnopqrstuvwx
"hijklmnopqrstuvwx gfedcb a": 38, 31, 1,226
"hijklmnopqrstuvwx gfedcb a": 38, 31, 1,226
Введите строку: 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
Введите строку: 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

Вы можете видеть, что оценка почти одинакова, за исключением наихудшего случая алгоритма обращения слов в третьем примере, для которого мой подход дает оценку ниже 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, оценка: 1,5

Точное количество назначений можно аппроксимировать по формуле:

n <= 1,5 * длина (строка)

в худшем случае:

abcdefghi jklmnopqrstuvwxyzzz

с 55 назначениями на строку длиной 37.

Идея похожа на мою предыдущую, просто в этой версии я попытался найти префикс и суффикс на границах слов с разницей в длине не более 1. Затем я запустил свой предыдущий алгоритм с этим префиксом и суффиксом (представьте, что они объединены) , Затем перейдите к необработанной части.

Например, для предыдущего наихудшего случая:

аб | аб | с

сначала мы сделаем обращение слов «ab» и «c» (4 назначения):

с | абы | абы

Мы знаем, что на границе это было пространство (есть много случаев, которые нужно обрабатывать, но вы можете это сделать), поэтому нам не нужно кодировать пространство на границе, это главное улучшение по сравнению с предыдущим алгоритмом. ,

Затем, наконец, мы бежим по четырем средним символам, чтобы получить:

CBA AB

всего 8 назначений, оптимальных для этого случая, поскольку все 8 символов изменены.

Это устраняет наихудший случай в предыдущем алгоритме, поскольку наихудший случай в предыдущем алгоритме исключается.

Посмотрите пример прогона (и сравнение с ответом @ primo - его вторая строка):

Введите строку: я могу сделать все, что угодно
«Все, что я могу сделать»: 20, 17
«все, что я могу сделать»: 17, 17
Введите строку: abcdef ghijklmnopqrs
"ghijklmnopqrs fedcb a": 37, 25
"ghijklmnopqrs fedcb a": 31, 25
Введите строку: abcdef ghijklmnopqrst
"ghijklmnopqrst fedcb a": 38, 26
"ghijklmnopqrst fedcb a": 32, 26
Введите строку: abcdefghi jklmnozzzzzzzzzzzzzzzzz
"jklmnozzzzzzzzzzzzzzzzz ihgfedcb a": 59, 41
"jklmnozzzzzzzzzzzzzzzzz ihgfedcb a": 45, 41
Введите строку: abcdefghi jklmnopqrstuvwxyzzz
"jklmnopqrstuvwxyzzz ihgfedcb a": 55, 37
"jklmnopqrstuvwxyzzz ihgfedcb a": 45, 37
Введите строку: ab ababababababac
"cababababababa ab": 30, 30
"cababababababa ab": 31, 30
Введите строку: ab ababababababcc
"cbababababababa ab": 32, 32
"cbababababababa ab": 33, 32
Введите строку: abc d abc
"abc d abc": 0, 9
"abc d abc": 0, 9
Введите строку: abc dca
"acd abc": 6, 9
"acd abc": 4, 9
Введите строку: abc abababababcc
"cbabababababa abc": 7, 29
"cbabababababa abc": 5, 29

Ответ primo, как правило, лучше, хотя в некоторых случаях я могу иметь преимущество в 1 балл =)

Также его код намного короче моего, хаха.

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, оценка: асимптотически 2, в обычном случае гораздо меньше

старый код удален из-за нехватки места

Идея заключается в том , чтобы перебирать каждый индекс, и для каждого индекса i, мы берем характер, вычислить новое положение j, запомните символ в позиции j, присвоить символ , iчтобы j, и повторите с символом с индексом j. Поскольку для вычисления новой позиции нам нужна информация о пробелах, я кодирую старый пробел как заглавную версию новой буквы, а новый пробел - как @.

justhalf
источник
Если вы можете уменьшить количество слов в худшем случае до длины строки (скажем, чтобы length(string)/3заставить каждое слово в худшем случае как минимум иметь длину 2), тогда оценка будет меньше 2 (в приведенном выше примере это будет 1,67)
полугодие
1
Я добавил своп счетчик к моему; Ваш действительно побеждает мой в худшем случае (но не в общем случае). Нужно найти способ это исправить;)
primo
Строка 127: if any(process_loop(...) for j in range(...))не нужно ли подсчитывать назначения из этих циклов процесса?
Примо
Это не делает никакого назначения. Если вы видите, dry_runпараметр имеет ненулевое значение (значение i). Внутри process_loop, если dry_runон не равен нулю, он не будет выполнять никаких заданий.
полугодие
1
Я думаю, что теперь у меня есть лучшая картина. По сути, два разных метода с различным поведением в наихудшем случае объединяются, чтобы исключить наихудший случай для обоих. Мне это нравится. В целом, я думаю, что это может быть лучшим подходом, хотя, скорее всего, два (или более) совершенно разных метода могут быть объединены, чтобы еще больше сократить наихудший случай.
Примо
14

Perl, оценка 1.3̅

Для каждого непробельного символа выполняется одно назначение, а для каждого пробельного символа два назначения. Поскольку пробельные символы не могут превышать половины общего числа символов, наихудший результат равен 1,5 .

Алгоритм не изменился, но я могу доказать нижнюю верхнюю границу. Давайте сделаем два замечания:

  1. Пробелы прямо напротив пробелов не нужно менять местами.
  2. Односимвольные слова прямо напротив пробелов не меняются во время основной фазы, а только один раз в конце.

Затем можно увидеть, что теоретический «наихудший случай» с асимптотически 1/2 пробелом не является наихудшим случаем вообще: 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

На самом деле, это довольно хороший случай.

Чтобы не допустить наблюдения одного и двух выше, каждое односимвольное слово должно быть перемещено в середину слова длиной три или более символов. Это предполагает наихудший случай, содержащий асимптотически 1/3 пробела: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

Или, что то же самое, только двухсимвольные слова: 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

Поскольку наихудший случай содержит асимптотически 1/3 пробела, наихудший случай становится 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;

Изменить: Добавлен счетчик свопов и соотношение.

Ввод взят из стандартного ввода. Пример использования:

$ 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

метод

Для начала первый символ строки перемещается в конечный пункт назначения. Только что замененный персонаж перемещается к месту назначения и т. Д. Это продолжается до тех пор, пока не будет выполнено одно из двух условий:

  1. Персонаж должен поменяться местами.
    Когда это происходит, персонаж не заменяется пробелом, а скорее на зеркальную позицию пробела. Алгоритм продолжается с этой позиции.
  2. Цикл был достигнут.
    Когда цель возвращается в начальную начальную позицию текущего цикла, необходимо найти следующий символ без отмены (или, скорее, любой символ без отмены). Чтобы сделать это при постоянных ограничениях памяти, все перестановки, сделанные до этого момента, отслеживаются в обратном направлении.

После этой фазы каждый непробельный символ перемещается не более одного раза. Чтобы закончить, все пробелы поменялись местами с символами в их положениях зеркала, требуя две операции присваивания за пробел.

Примо
источник
Ух ты, круто. Можете ли вы объяснить, почему размещение символа в зеркальной позиции пространства дает правильный ответ?
полугодие
1
@ Никлас, я не думаю, что это возможно. Потому что для возврата вам нужна информация о положении в пространстве. Если вы переопределите эту информацию, вы не сможете вернуться.
полугодие
1
Я сравниваю свой алгоритм в своем ответе здесь: codegolf.stackexchange.com/a/26952/16337
justhalf
1
@justhalf В последней строке все пробелы будут в зеркальном положении. Поэтому мы можем смело использовать эту позицию для хранения символа, заменяющего пробел, и переключать их в конце.
Примо
1
Отлично сработано. У меня была похожая идея, но я не думал просто оставить места на месте и затем отразить их.
IchBinKeinBaum
7

Рубин, оценка 2

Как стартер очень простой алгоритм. Сначала он переворачивает всю строку, а затем снова переворачивает каждое слово в строке. В худшем случае (одно слово, четное количество символов) счет становится равным 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

Использование:

> revwords("hello there everyone")
"everyone there hello"
Говард
источник
Почему вы не использовали встроенную функцию Ruby для обращения строки? Это изменит счет?
AL
используйте, s [a], s [b] = s [b], s [a]
Thaha kp
5

C ++: оценка 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;
}
Анмол Сингх Джагги
источник
2
Я проверял это. Работает хорошо!
bacchusbeale
2

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
]

Мне неясно на счет для этого. В этом коде нет прямого назначения строки. Все обрабатывается тем, reverse/partкоторый выполняет реверсирование внутри и изначально на всей цепочке.

Некоторые подробности о коде:

  • Цикл по строке ( series), пока не достигнетtail?

  • Первый раз в цикле сделать полный оборот строки - reverse/part series tail series(что так же, как reverse series)

  • Затем поменяйте местами каждое найденное слово на следующих итерациях - reverse/part series find series space

  • Когда найденное слово будет найдено, вернитесь tail seriesназад, чтобы оно перевернуло последнее слово в строке -reverse/part series tail series

Rebol позволяет обойти строку через внутренний указатель . Вы можете увидеть это в series: next f(переместить указатель на пробел, чтобы начало следующего слова) иseries: head series (сбросить указатель на голову).

Смотрите серию для получения дополнительной информации.

Пример использования в консоли 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"
draegtun
источник
На первом проходе каждый символ перемещается один раз, а на втором проходе каждый непробельный символ снова перемещается. Для произвольно большого ввода с относительно небольшим количеством пробелов оценка приближается к 2.
primo
2

C: оценка 2

Это просто переворачивает всю строку один раз, а затем переворачивает каждое слово.

#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;
}
technosaurus
источник
3
Это только кодовый ответ. Попробуйте добавить объяснение того, что происходит в вашем коде.
Джастин
1

Питон: оценка 2

Почти идентичен алгоритму Говарда, но делает шаги обращения в обратном порядке (сначала переворачивает слова, затем переворачивает всю строку). Дополнительные б памяти 3 переменные байты размера: i, jи t. Технически, findи lenиспользуют некоторые внутренние переменные, но они могут также легко использоваться повторно iили jбез потери функции.

быстрое редактирование: сохранение строковых назначений только путем замены, когда символы различаются, поэтому я могу получить некоторые дополнительные точки из заметки № 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))
wrongu
источник
1

партия

Я признаю, что не полностью понимаю оценку (я думаю, что это два) .., но я скажу - это делает вещь .

@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!

Ввод принимается как первое стандартное входное значение и поэтому должен быть заключен в кавычки -
вызов: script.bat "hello there everyone"
из: everyone there hello.

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

unclemeat
источник
-2

Javascript

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

Использование:

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

У меня странное чувство, что я что-то пропустил ...

Spedwards
источник
3
Да, это не так, потому что вы не изменяете входную строку. Поскольку в JavaScript это невозможно, вам нужно эмулировать строки с помощью массива символов (то есть целых чисел кодовой точки или односимвольных строк).
Мартин Эндер
Более того, он использует много-много дополнительного пространства.
Бен Милвуд,