Biorąc pod uwagę listę ciągów, s_0, s_1, ..., s_nznajdź najkrótszy ciąg, Sktóry zawiera każdy z nich s_0, s_1, ..., s_njako podłańcuch .

Przykłady :

• S('LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE')='SEDOLOREMAGNAD'
• S('ABCDE', 'BCD', 'C')='ABCDE'

Napisz najkrótszy program (lub funkcję), który rozwiązuje ten problem. Jeśli chcesz, możesz reprezentować ciągi jako tablice lub listy znaków / liczb całkowitych. Standardowe biblioteki są w porządku. Do wejścia / wyjścia można użyć cokolwiek bardziej dogodnego: STDIN / STDOUT, monit użytkownika, parametr / wartość zwracana funkcji itp.

Wydajność nie jest krytyczna - powiedzmy, że dla danych wejściowych o całkowitej długości <100 znaków wynik musi być obliczony średnio w <10 sekund przeciętnie nowoczesnego sprzętu.

Python 2, 170 153/157/159

Skrócone dzięki niektórym pomysłom Baptiste .

from itertools import*
print min((reduce(lambda s,w:(w+s[max(i*(s[:i]==w[-i:])for i in range(99)):],s)[w in s],p)
for p in permutations(input())),key=len)

Drugi podział linii nie jest potrzebny.

Wejście: 'LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE'
Wyjście:SEDOLOREMAGNAD

Nawet przy długich ciągach wejściowych, działa to w mniej niż 2 sekundy, jeśli jest co najwyżej 7 ciągów wejściowych (jak w podanym przykładzie, który działa na 1,7 1,5 sekundy na mojej maszynie). Przy 8 lub więcej ciągach wejściowych zajmuje to jednak więcej niż 10 sekund, ponieważ złożoność czasu jest O(n!).

Jak zauważył Baptiste, range(99)należy go zastąpić, range(len(w))jeśli należy obsługiwać dowolne długości wejściowe (łączna długość kodu to 157 znaków). Jeśli powinny być obsługiwane puste ciągi wejściowe, należy je zmienić na range(len(w)+1). Myślę jednak, że range(99)działa poprawnie dla dowolnej całkowitej długości wejściowej mniejszej niż 200.

Więcej testów:

>>> "AD", "DO", "DOLOR", "DOLORE", "LOREM", "MAGNA", "SED", "ORE",  "R"
SEDOLOREMAGNAD

>>> 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz', 'abcdefghijklmnopqrstuvw
... xyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstu
... vwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'ZOOM', 'aZ', 'Za', 'ZA'
aZABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZOOM

Mathematica 337 418 372

Po bezskutecznych próbach implementacji przy użyciu Mathematica LongestCommonSubsequencePositions, przeszedłem do dopasowywania wzorców.

v=Length;
p[t_]:=Subsets[t,{2}];
f[w_]:=Module[{c,x,s=Flatten,r={{a___,Longest[y__]},{y__,b___}}:>{{a,y},{y,b},{y},{a,y,b}}},
c=p@w;
x=SortBy[Cases[s[{#/.r,(Reverse@#)/.r}&/@c,1],{_,_,_,_}],v[#[[3]]]&][[-1]];
Append[Complement[w,{x[[1]],x[[2]]}],x[[4]]]]

g[r_]:=With[{h=Complement[r,Cases[Join[p@r,p@Reverse@r],y_/;!StringFreeQ@@y:>y[[2]]]]},
FixedPoint[f,Characters/@h,v@h-1]<>""]

Reguła dopasowywania wzorców,

r={{a___,Longest[y__]},{y__,b___}}:> {{a,y},{y,b},{y},{a,y,b}}},

pobiera uporządkowaną parę słów (przedstawionych jako listy znaków) i zwraca: (1) słowa, {a,y}a {y,b}następnie (2) wspólny podłańcuch y, który łączy koniec jednego słowa z początkiem drugiego słowa, i, wreszcie połączone słowo {a,y,b}, które zastąpi słowa wejściowe. Zobacz pokrewny przykład Belizariusza: /mathematica/6144/looking-for-longest-common-substring-solution

Trzy kolejne znaki podkreślenia oznaczają, że element jest sekwencją zero lub więcej znaków.

Reversejest zatrudniony później, aby zapewnić przetestowanie obu zamówień. Te pary, które mają wspólne litery, są zwracane w niezmienionej formie i ignorowane.

Edytuj :

Poniższe słowa usuwają z listy słowa, które są „zakopane” (tj. W pełni zawarte) w innym słowie (w odpowiedzi na komentarz @ flornquake).

h=Complement[r,Cases[Join[p@r,p@Reverse@r],x_/;!StringFreeQ@@x:> x[[2]]]]

Przykład :

 {{"D", "O", "L", "O", "R", "E"}, {"L", "O", "R", "E", "M"}} /. r

zwraca

{{„D”, „O”, „L”, „O”, „R”, „E”}, {„L”, „O”, „R”, „E”, „M”}, { „L”, „O”, „R”, „E”}, {„D”, „O”, „L”, „O”, „R”, „E”, „M”}}

Stosowanie

g[{"LOREM", "ORE", "R"}]

AbsoluteTiming[g[{"AD", "DO", "DOLOR", "DOLORE", "LOREM", "MAGNA", "SED", "ORE",  "R"}]]

„LOREM”

{0,006256, „SEDOLOREMAGNAD”}

GolfScript, 66 znaków

{.,1>{.`{[1$]-s:h;.,),\`{:g<`{\+.g?0<{;}*}+h%~}+/}+%.&}*}:s~{,}$0=

Dość krótki, ale ze względu na wykładniczą złożoność czasu (i GolfScript) naprawdę powolny, przekracza limit 10 sekund.

Przykłady:

['LOREM' 'DOLOR' 'SED' 'DO' 'MAGNA' 'AD' 'DOLORE']
{.,1>{.`{[1$]-s:h;.,),\`{:g<`{\+.g?0<{;}*}+h%~}+/}+%.&}*}:s~{,}$0=
# => SEDOLOREMAGNAD

['AB' 'BC' 'CA' 'BCD' 'CDE']
{.,1>{.`{[1$]-s:h;.,),\`{:g<`{\+.g?0<{;}*}+h%~}+/}+%.&}*}:s~{,}$0=
# => CABCDE

Python 2, 203 187 200

from itertools import permutations as p
def n(c,s=''):
 for x in c:s+=x[next((i+1 for i,l in [(j,x[:j+1])for j in range(len(x))][::-1]if s.endswith(l)),0):]
 return s
print min(map(n,p(input())),key=len)

Wejście: ['LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE']
Wyjście:SEDOLOREMAGNAD

Edytować

Używając reducei trochę brudnych sztuczek związanych z importowaniem, mogę to jeszcze bardziej zmniejszyć (i tylko do jednej linii!):

print min((reduce(lambda a,x:a+x[next((i+1 for i,l in [(j,x[:j+1])for j in range(len(x))][::-1]if a.endswith(l)),0):],P,'')for P in __import__('itertools').permutations(input())),key=len)

Edytuj 2

Jak zauważono trzęsienie ziemi, daje to nieprawidłowe wyniki, gdy jedno słowo jest zawarte w innym. Poprawka tego dodaje kolejne 13 znaków:

print min((reduce(lambda a,x:a+(x[next((i+1 for i,l in [(j,x[:j+1])for j in range(len(x))][::-1]if a.endswith(l)),0):],'')[x in a],P,'')for P in __import__('itertools').permutations(input())),key=len)

Oto oczyszczona wersja:

from itertools import permutations

def solve(*strings):
    """
    Given a list of strings, return the shortest string that contains them all.
    """
    return min((simplify(p) for p in permutations(strings)), key=len)

def prefixes(s):
    """
    Return a list of all the prefixes of the given string (including itself),
    in ascending order (from shortest to longest).
    """
    return [s[:i+1] for i in range(len(s))]
    return [(i,s[:i+1]) for i in range(len(s))][::-1]

def simplify(strings):
    """
    Given a list of strings, concatenate them wile removing overlaps between
    successive elements.
    """
    ret = ''
    for s in strings:
        if s in ret:
            break
        for i, prefix in reversed(list(enumerate(prefixes(s)))):
            if ret.endswith(prefix):
                ret += s[i+1:]
                break
        else:
            ret += s
    return ret

print solve('LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE')

Możliwe jest ogolenie kilku postaci kosztem poprawności teoretycznej za pomocą range(99)zamiast range(len(x))(kredyty do trzęsienia ziemi za myślenie o tym).

Python, 144 znaki

S=lambda A,s:min(S(A-set([a]),s+a[i:])for a in A for i in range(len(a)+1)if i==0 or s[-i:]==a[:i])if A else(len(s),s)
T=lambda L:S(set(L),'')[1]

Spobiera zestaw słów, Aktóre nadal wymagają umieszczenia, oraz ciąg szawierający słowa umieszczone do tej pory. Odbieramy pozostały słowo aod Ai pokrywają ją od 0do len(a)znaków z końcem s.

Podany przykład zajmuje tylko około 0,15 sekundy.

Haskell, 121

import Data.List
a p []=[(length p,p)]
a p s=[r|w<-s,t<-tails w,isInfixOf w$p++t,r<-a(p++t)(s\\[w])]
s=snd.minimum.a ""

Minus dwa, jeśli funkcja nie musi być powiązana z nazwą