Объединить две строки и создать лексикографическую наименьшую объединенную строку

Question

Я решал проблему, когда сталкивался с довольно простой проблемой. Учитывая две строки S1 и S2, merge(S1,S2) обозначает любую строку, полученную путем перемешивания двух строк S1 и S2, сохраняя порядок символов в обоих случаях, чтобы результирующая строка была лексикографически наименьшей.

Пример

S1 = abad 
S2 = bbde 
merge(S1, S2) = ababbdde 

Теперь, я попытался решить проблему путем применения жадного техники, начиная с первого элемента как строки, а затем ищет наименьшего элемента и добавить его к результату. Но вскоре я узнал, что это не всегда приводит к оптимальному решению. Код выглядел примерно так.

int n = a.size(), m = b.size(); 
int i =0, j=0, k=0; char array[n+m]; 
for(; i< n && j<n;) { 
    if(a[i] < b[j]) { 
     array[k] = a[i]; 
     ++i; 
    } 
    else { 
     array[k] = b[j]; 
     ++j; 
    } 
    ++k; 
} 

while(i<n) { 
    array[k] = a[i]; 
    ++i; 
    ++k; 
} 
while(j<m) { 

    array[k] = b[j]; 
    ++j; 
    ++k; 
} 
for (int i = 0; i < n+m; ++i) { 
    cout<<array[i]; 
} 
cout<<endl; 

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

int n = a.size(), m = b.size(); 
int i =n-1, j=m-1, k=n+m-1; char array[n+m]; 
for(; i>=0 && j>=0;) { 
    if(a[i] > b[j]) { 
     array[k] = a[i]; 
     --i; 
    } 
    else { 
     array[k] = b[j]; 
     --j; 
    } 
    --k; 
} 
while(i>=0) { 
    array[k] = a[i]; 
    --i; 
    --k; 
} 
while(j>=0) { 
    array[k] = b[j]; 
    --j; 
    --k; 
} 
for (int i = 0; i < n + m; ++i) { 
    cout<<array[i]; 
} 
cout<<endl; 

Но я не уверен, что всегда будет всегда предлагать оптимальное решение.

Является ли это решение правильным в первую очередь, и если да, то кто-то может дать мне небольшое доказательство того, почему это также создает оптимальное решение.

Answer 1

Жадный решит проблему. для решения этой проблемы вам обязательно придется посетить обе строки.

В вашем коде вам не хватает одного места, т. Е. Ваш первый цикл для петли if(a[i] < b[j]) должен быть if(a[i] <= b[j]). проверить код here

Answer 2

Полное решение основано на моем комментарии ранее.

import string 
import random 

global brute_force_lowest 
global almost_greedy_lowest 

global brute_force_calls 
global almost_greedy_calls 

def brute_force(p, a, b): 
    global brute_force_lowest 
    global brute_force_calls 

    brute_force_calls += 1 

    if len(a) > 0: brute_force(p + a[0], a[1:], b) 
    if len(b) > 0: brute_force(p + b[0], a, b[1:]) 

    if len(a) == 0 and len(b) == 0: 
    if p < brute_force_lowest: brute_force_lowest = p 


def almost_greedy(p, a, b): 
    global almost_greedy_lowest 
    global almost_greedy_calls 

    almost_greedy_calls += 1 

    if len(a) == 0 and len(b) == 0: 
    if p < almost_greedy_lowest: almost_greedy_lowest = p 
    elif len(b) == 0: 
    almost_greedy(p + a, '', '') 
    elif len(a) == 0: 
    almost_greedy(p + b, '', '') 
    elif a[0] < b[0]: 
    almost_greedy(p + a[0], a[1:], b) 
    elif a[0] > b[0]: 
    almost_greedy(p + b[0], a, b[1:]) 
    else: 
    almost_greedy(p + a[0], a[1:], b) 
    almost_greedy(p + b[0], a, b[1:]) 


for j in range(10000): 
    a = ''.join(random.choice(string.ascii_lowercase) for _ in range(random.randint(2, 10))) 
    b = ''.join(random.choice(string.ascii_lowercase) for _ in range(random.randint(2, 10))) 
    brute_force_lowest = a + b 
    brute_force_calls = 0 
    brute_force('', a, b) 
    almost_greedy_calls = 0 
    almost_greedy_lowest = a + b 
    almost_greedy('', a, b) 
    print('%s, %s -> %s vs. %s (%.3f)' % (a, b, brute_force_lowest, almost_greedy_lowest, float(almost_greedy_calls)/brute_force_calls)) 
    if almost_greedy_lowest != brute_force_lowest: print 'ERROR' 

Одна интересная статистика, что этот алгоритм работает примерно в десять раз быстрее, чем грубой силы алгоритм в среднем, если мы ограничиваем алфавит «аb».

UPDATE Некоторые оптимизации:

def prefix_length(a): 
    for i in range(len(a)): 
    if a[i] != a[0]: return i 
    return len(a) 

def almost_greedy(p, a, b): 
    global almost_greedy_lowest 
    global almost_greedy_calls 

    almost_greedy_calls += 1 

    if p > almost_greedy_lowest: return 

    if len(a) == 0 and len(b) == 0: 
    if p < almost_greedy_lowest: almost_greedy_lowest = p 
    elif len(b) == 0: 
    almost_greedy(p + a, '', '') 
    elif len(a) == 0: 
    almost_greedy(p + b, '', '') 
    elif a[0] < b[0]: 
    almost_greedy(p + a[0], a[1:], b) 
    elif a[0] > b[0]: 
    almost_greedy(p + b[0], a, b[1:]) 
    else: 
    la = prefix_length(a) 
    almost_greedy(p + a[0] * la, a[la:], b) 
    lb = prefix_length(b) 
    almost_greedy(p + b[0] * lb, a, b[lb:])