Bei einer gegebenen Liste von Listen finden Sie die kürzeste Liste, die eine zusammenhängende Unterliste von genau einer Liste ist.

Zum Beispiel, wenn wir hatten

[[1,2,3],
 [1,2,3,4],
 [2,4,5,6],
 [1,2,4,5,6]]

Die kürzeste zusammenhängende Unterliste wäre, [3,4]da sie nur in der zweiten Liste erscheint.

Wenn es keine eindeutige zusammenhängende Unterliste gibt (dies erfordert mindestens einen doppelten Eintrag), geben Sie eine leere Liste aus. Hier ist ein Beispiel

[[1,2,3],
 [1,2,3],
 [1,2]]

Wenn mehrere zusammenhängende Unterlisten von minimaler Größe vorhanden sind, können Sie eine beliebige oder eine alle enthaltende Liste ausgeben. Zum Beispiel, wenn die Eingabe war

[[1,2,3],[2],[1],[3]]

Sie könnten Ausgang entweder [1,2], [2,3]oder [[1,2],[2,3]]. Wenn Sie die letztere Option wählen, können Sie Singleton-Listen für die Fälle ausgeben, in denen es nur eine Lösung gibt.

Die Ausgabe kann in derselben Liste mehrmals vorkommen, solange sie in keiner anderen Liste enthalten ist. Beispielsweise

[[1,2,1,2],[2,1]]

sollte ausgegeben werden, [1,2]weil [1,2]es sich um eine Unterliste der ersten Liste handelt, aber nicht um die zweite, obwohl es sich auf zwei verschiedene Arten um eine Unterliste der ersten Liste handelt.

Als Eingabe können Sie eine Liste von Listen verwenden, die einen beliebigen Typ enthalten, sofern dieser Typ mehr als 100 mögliche Werte aufweist, dh keine Booleschen Werte.

Dies ist Codegolf, daher werden die Antworten in Bytes bewertet, wobei weniger Bytes besser sind.

Testfälle

[[1,1]] : [1]
[[1],[1]] : []
[[1,1],[1]] : [1,1]

Schale , 12 14 15 Bytes

+3 Bytes für Groß- und Kleinschreibung [[1,1]]

Ṡḟȯ¬€Ṡ-uÖLṁȯtuQ

Probieren Sie es online!

Erklärung

          ṁ      -- map and concatenate
           ȯt    --   all but the first
             u   --   unique elements of
              Q  --   contiguous sublist
        ÖL       -- sort by length
Ṡḟ               -- find the first element satisfying this predicate
  ȯ¬€            --   not an element of
     Ṡ-          --   the list of sublists minus
       u         --   its unique elements

Hinweis: Ṡ f g x = f (g x) xDies lässt sich mit der oben beschriebenen Methode nur schwer erklären.

Pyth, 15 Bytes

halDs-M.p.:R)QY

Testsuite

Zunächst generieren wir alle Teilstrings jeder Eingabeliste mit .:R)Q. Dann generieren wir alle möglichen Ordnungen dieser Teilzeichenfolgengruppen .p.

Nun zum kniffligen Teil: -M . Dies faltet die -Funktion über jede Bestellliste. Es beginnt mit der ersten Teilzeichenfolgenliste und filtert dann alle Insassen aller anderen Listen heraus.

Dann werden die Ergebnisse verkettet, geordnet nach Länge, a [] angehängt und dann das erste Element der resultierenden Liste mit extrahiert h.

Dies wäre 4 Bytes kürzer, wenn ich auf keinen eindeutigen Unterlisten Fehler machen könnte, anstatt eine leere Liste auszugeben.

Pyth - 20 Bytes

Ksm.:d)QhalDfq1/KTKY

Test Suite .

Haskell , 149 128 126 113 Bytes

import Data.List
f l=[x|x<-l,sum[1|y<-l,y==x]<2]
h[]=[]
h(x:y)=x
i=h.f.sortOn length.(>>=tail.nub.(>>=tails).inits)

Probieren Sie es online!

Dank Wheat Wizard, H.PWiz und Bruce Forte 21 Bytes gespart.

Zwei weitere Bytes dank H.PWiz gespeichert.

13 Bytes dank nimi gespart.

BEARBEITEN Dies war die ursprüngliche Erklärung:

• a ist eine Verknüpfung zum Verbinden von Listen.

• sberechnet alle fortlaufenden Unterlisten (alle tailsvon allen inits). Beachten Sie, dass nubnur das erste Vorkommen jedes Elements beibehalten wird, sodass taildie leere Liste aus den Unterlisten entfernt wird.

• g Führt alle Unterlisten aus allen angegebenen Listen in einer großen Liste von Unterlisten zusammen und sortiert sie nach Länge.

• f f ist ein Filter für Elemente, die in der großen Liste nur einmal vorkommen

• h ist eine sichere Version von head

• i ist der Kleber

Ziemlich unelegant! Es sollte eine bessere Lösung geben ...

Java 8, 251 + 19 = 270 Bytes

Ein sehr grobes Lambda von, minimal, List<List>bis List(am besten, um es zu werfen, Function<List<List<Integer>>, List<Integer>>obwohl). Es ist eine Brute-Force-Lösung, die Chunk-Längen von 1 bis zur Größe der größten Liste iteriert. Dabei wird jeweils jeder Chunk dieser Länge in jeder Liste durchlaufen und jeder solche Chunk mit jedem Chunk gleicher Größe in jeder anderen Liste verglichen.

Fürchte mich, Müllmann.

import java.util.*;

i->{int x,l=x=0,s,t;for(List z:i)x=Math.max(x,z.size());List r=i;while(l++<=x)for(List a:i)c:for(s=0;s<=a.size()-l;s++){for(List b:i)for(t=0;t<=b.size()-l;)if(b.subList(t,l+t++).equals(r=a.subList(s,s+l))&a!=b)continue c;return r;}return new Stack();}

Ungolfed Lambda

i -> {
    int
        x,
        l = x = 0,
        s, t
    ;
    for (List z : i)
        x = Math.max(x, z.size());
    List r = i;
    while (l++ <= x)
        for (List a : i)
            c: for (s = 0; s <= a.size() - l; s++) {
                for (List b : i)
                    for (t = 0; t <= b.size() - l; )
                        if (b.subList(t, l + t++).equals(r = a.subList(s, s + l)) & a != b)
                            continue c;
                return r;
            }
    return new Stack();
}

Probieren Sie es online

Java 8, 289 + 45 = 334 Bytes

Dies ist ein funktionalerer Ansatz, bei dem Streams verwendet werden. Wenn es eine Methode gäbe Stream, die auf nur einmal auftretende Elemente reduziert, hätte diese Lösung die oben beschriebene übertroffen. Weisen Sie den gleichen Typ wie oben zu.

import java.util.*;import java.util.stream.*;

l->{List<List>o=l.stream().flatMap(a->IntStream.range(1,a.size()+1).boxed().flatMap(n->IntStream.range(0,a.size()-n+1).mapToObj(k->a.subList(k,k+n)))).collect(Collectors.toList());o.sort((a,b)->a.size()-b.size());for(List a:o)if(o.indexOf(a)==o.lastIndexOf(a))return a;return new Stack();}

Ungolfed Lambda

l -> {
    List<List> o = l.stream()
        .flatMap(a -> IntStream.range(1, a.size() + 1)
            .boxed()
            .flatMap(n -> IntStream.range(0, a.size() - n + 1)
                .mapToObj(k -> a.subList(k, k + n))
            )
        )
        .collect(Collectors.toList())
    ;
    o.sort((a, b) -> a.size() - b.size());
    for (List a : o)
        if (o.indexOf(a) == o.lastIndexOf(a))
            return a;
    return new Stack();
}

Probieren Sie es online

Gelee , 15 Bytes

Ẇ€Q€ẎɓċỊµÐf⁸LÐṂ

Probieren Sie es online!

-3 Bytes dank Jonathan Allan

05AB1E , 15 Bytes

εŒÙ}€`{γʒg}€`éн

Probieren Sie es online!

Pyth, 14 Bytes

sfq1lT.gksm{.:

Probieren Sie es hier aus.