Hintergrund

Ich war inspiriert von 3Blue1Brown ‚s jüngsten Video über die Halskette Spaltung Problem (oder , wie er es nennt, das gestohlene Halskette Problem) und seine Beziehung zum Borsuk-Ulam .

In diesem Problem haben zwei Diebe eine wertvolle Halskette gestohlen, die aus verschiedenen Arten von Juwelen besteht. Es gibt eine gerade Anzahl von Juwelen jeder Art, und die Diebe möchten jede Juwelenart gleichmäßig auf die beiden aufteilen. Der Haken ist, dass sie dies tun müssen, indem sie die Kette in eine Anzahl zusammenhängender Segmente aufteilen und die Segmente auf die beiden verteilen.

Hier ist ein Beispiel mit vier jewel Typen bezeichnet S, E, D, und R(für Saphir, Smaragd, Diamanten und Rubin, jeweils). Angenommen, die Halskette sieht wie folgt aus:

[S,S,S,E,S,D,E,R,S,R,E,S,S,S,D,R,E,E,R,E,D,E,R,R,D,E,E,E]

Es gibt 8Saphire, 10Smaragde, 4Diamanten und 6Rubine. Wir können die Kette wie folgt aufteilen:

[[S],[S],[S,E,S,D,E,R,S],[R,E,S,S,S,D,R,E,E,R,E,D,E],[R,R,D,E,E,E]]

Wenn wir dann das erste, dritte und fünfte Segment einem Dieb und das zweite und vierte Segment dem anderen Dieb geben, wird jedes mit 4Saphiren, 5Smaragden, 2Diamanten und 3Rubinen enden :

[S],    [S,E,S,D,E,R,S],                            [R,R,D,E,E,E]
    [S],                [R,E,S,S,S,D,R,E,E,R,E,D,E],

Mit 0-indexing werden diese Schnitte an den Indizes ausgeführt [1,2,9,22].

Tor

Es stellt sich heraus, dass eine solche faire Aufteilung immer mit höchstens nSchnitten durchgeführt werden kann, wobei ndie Anzahl der Edelsteintypen angegeben ist. Ihre Aufgabe ist es, ein komplettes Programm oder eine komplette Funktion zu schreiben, die eine Kette als Eingabe verwendet und eine minimale Teilung (die geringste Anzahl von Schnitten) ausgibt.

Eingang

Die Eingabe kann in einem beliebigen Format erfolgen. Die Kette sollte eine Abfolge von Juwelen sein und nichts weiter; zB eine Liste von ganzen Zahlen, ein Wörterbuch mit Schlüsseln, die die Edelsteintypen und -werte darstellen, wobei es sich um Listen von Indizes handelt. Sie können optional die Länge der Halskette oder die Anzahl der verschiedenen Edelsteintypen angeben, sollten jedoch keine weiteren Eingaben vornehmen.

Sie können davon ausgehen, dass die Eingabehalskette gültig ist. Sie müssen nicht mit dem Fall umgehen, in dem eine ungerade Anzahl von Juwelen eines bestimmten Typs vorhanden ist oder die Halskette leer ist.

Ausgabe

Auch hier kann die Ausgabe in jedem geeigneten Format erfolgen. zB eine Liste von Segmenten, eine Liste von Schnittpositionen, ein Wörterbuch mit Schlüsseln, die die beiden Diebe darstellen, und Werte, die Listen von Segmenten sind usw. Segmente können durch ihren Startindex, Endindex, Liste von aufeinanderfolgenden Indizes, Liste von Juwelen, ihre Länge usw. Sie können 0- oder 1- indizieren. Wenn die Reihenfolge für Ihr Format nicht von Bedeutung ist, kann die Ausgabe in beliebiger Reihenfolge erfolgen. Hier ist die obige Ausgabe in verschiedenen Formaten:

list of segments: [[S],[S],[S,E,S,D,E,R,S],[R,E,S,S,S,D,R,E,E,R,E,D,E],[R,R,D,E,E,E]]
list of cuts:     [1,2,9,22]
list of lengths:  [1,1,7,13,6]
dictionary:       {'thief1' : [(R,R,D,E,E,E),(S),(S,E,S,D,E,R,S)], 'thief2' : [(S),(R,E,S,S,S,D,R,E,E,R,E,D,E)]}

Beachten Sie, dass die Reihenfolge in der Liste der Segmente (Segmente wechseln sich zwischen den Dieben ab) und der Liste der Längen (um die Segmente zu identifizieren) wichtig ist, nicht jedoch in der Liste der Schnitte oder im Wörterbuch. Edit: Greg Martin wies darauf hin, dass dies keine gültigen Ergebnisse sind, da eine faire Aufteilung in zwei Teile erzielt werden kann

Testfälle

[1,2,1,2,1,3,1,3,3,2,2,3] -> [[1,2,1],[2,1,3,1],[3,3,2],[2,3]]
[1,1,1,1,2,2,3,3,3,3,3,3] -> [[1,1],[1,1,2],[2,3,3,3],[3,3,3]]
[1,1,1,1,1,1,1,1,1,1,1,1] -> [[1,1,1,1,1,1],[1,1,1,1,1,1]]
[1,1,1,1,2,3,4,2,3,4,2,2] -> [[1,1],[1,1,2,3,4,2],[3,4,2,2]]

Anmerkungen

1. Standardlücken sind verboten.
2. Das ist Code-Golf ; kürzeste Antwort (in Bytes) gewinnt.

Brachylog , 13 Bytes

~c.ġ₂z₁Ċcᵐoᵛ∧

Probieren Sie es online!

Hinweis: Das Metapredikat ᵛist neuer als diese Herausforderung.

Erläuterung

~c.ġ₂z₁Ċcᵐoᵛ∧  Input is a list, say L = [1,2,2,2,1,2,3,3]
~c.            Output is a partition of the input: [[1,2,2],[2,1,2],[3],[3]]
  .ġ₂          Split the output into chunks of length 2: [[[1,2,2],[2,1,2]],[[3],[3]]]
     z₁        Zip (transpose) the chunks: [[[1,2,2],[3]],[[2,1,2],[3]]]
       Ċ       This is a 2-element list (forbid the trivial partition).
        cᵐ     Concatenate both: [[1,2,2,3],[2,1,2,3]]
          oᵛ   If you sort both lists, they are equal.
            ∧  Don't unify with the output.

Die Partitionen werden in aufsteigender Reihenfolge der Anzahl der Blöcke aufgelistet, damit das Ergebnis so wenig Blöcke wie möglich enthält.

Jelly , 18 Bytes

s2ZFṢ$€E¬,L
ŒṖṖÇÞḢ

Probieren Sie es online!

Nicht effizient - das Beispiel hat 28 Juwelen, die ohne große Ressourcen nicht funktionieren, da der erste Schritt dieser Implementierung darin besteht, eine Liste der 2 ²⁷ zu erstellen möglichen Partitionen .

Gibt eine Liste von Listen zurück - die Segmente in der Reihenfolge, in der sie zwischen alternativen Dieben aufgeteilt werden. (Bezüglich der TIO-Ausgabe: Wenn eine Liste nur ein einzelnes Element enthält, stört der implizite Ausdruck die Klammern nicht. [])

Wie?

s2ZFṢ$€E¬,L - Link 1, get (isUnfair, Slices): A possible partition
s2          - split into slices of length 2 (any odd one on it's own at the end)
  Z         - transpose (first item is one thief's slices, second is the others)
     $€     - last two links as a monad for €ach
   F        -     flatten
    Ṣ       -     sort
       E    - equal? (theif1's jewels == theif2's jewels)
        ¬   - not
          L - length (number of slices in the partition)
         ,  - pair

ŒṖṖÇÞḢ - Main link: necklace
ŒṖ     - all partitions
  Ṗ    - pop, we must remove the rightmost one...
              because Link 1 will say it is fair, and it will have length 1!
              (a list of one thing has all entries equal)
    Þ  - sort by
   Ç   -     last link (1) as a monad
     Ḣ - head (get the first one, i.e. minimal isUnfair, then minimal length)

Mathematica, 118 Bytes

Fast geschlagen Jelly ... nur 1 aus;)

SelectFirst[l_±c_:=Append[-#±Most@c,#2]&@@l~TakeDrop~Last@c;l_±{}:={l};i=#;(i±#)&/@Range@#2~Subsets~#3,Tr[Tr/@#]==0&]&

Reine Funktion mit drei Argumenten: Die Kette als Liste von Token wie {A, A, A, A, B, C, D, B, C, D, B, B}; die Länge der Kette; und die Anzahl der verschiedenen Juwelen. Es wird eine Liste der Unterlisten im Formular zurückgegeben{{A, A}, {-A, -A, -B, -C, -D, -B}, {C, D, B, B}} , in der die Token ohne negative Vorzeichen an einen Dieb und die Token mit negativen Vorzeichen an den anderen Dieb gehen. (Obwohl dies redundante Informationen sind, führt der Algorithmus zu dieser Darstellung, und das Entfernen der negativen Vorzeichen würde mehrere Bytes kosten.)

Zuerst müssen wir eine Funktion implementieren, die eine Liste und eine Menge von nAusschnitten verwendet und die Liste der n+1Unterlisten zurückgibt, die durch Ausschneiden der Eingabeliste an diesen nAusschnitten erhalten werden. Der binäre Infix-Operator ±wird für diesen Zweck verwendet und durch rekursiv definiert l_±c_:=Append[-#±Most@c,#2]&@@l~TakeDrop~Last@c;l_±{}:={l};. Aufgrund des negativen Vorzeichens direkt danach Appendist das Ergebnis, dass die Unterlisten abwechselnd negative Vorzeichen haben und nicht mit jedem Token verbunden sind.

Dann generieren wir alle möglichen Cut-Place-Sets, deren Länge höchstens der Anzahl der Jewel-Typen entspricht, Range@#2~Subsets~#3und i=#;(i±#)&/@wenden den ±Operator (mit der eingegebenen Jewel- Liste) nacheinander auf jedes dieser Cut-Place-Sets an.

Zum Schluss SelectFirst[...,Tr[Tr/@#]==0&]&wird die erste der resultierenden Collier-Divisionen ausgewählt, die fair ist. Dies geschieht durch buchstäbliches Aufsummieren aller Elemente in allen Unterlisten. Mathematica ist klug genug, die positiven und negativen Kopien jedes Tokens auf offensichtliche Weise zu löschen.

Pyth, 16 Bytes

hfqFSMsM.TcT2t./

Probieren Sie es online aus: Demo oder Test Suite

Erläuterung:

hfqFSMsM.TcT2t./Q   implicit Q (=input) at the end
              ./Q   create all partitions of the input list 
                    (they are already sorted by number of cuts)
             t      remove the partition with zero splits
 f                  filter for partitions T, which satisfy:
          cT2          chop into pieces of length 2
        .T             transpose to get the pieces of each thieve
    SMsM               combine all pieces for each thieve and sort the results
  qF                   check if they got the same jewels
h                   print the first such partition

05AB1E , 14 Bytes

.œ¨ʒ2ôζε˜{}Ë}¤

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Erläuterung:

.œ                # All partitions of the (implicit) input
                  #  i.e. [2,3,2,1,3,1]
                  #   → [[[2],[3],[2],[1],[3],[1]],[[2],[3],[2],[1],[3,1]],
                  #      ...,[[2,3,2,1,3,1]]]
  ¨               # Remove the last one
   ʒ        }     # Filter this list by:
    2ô            # Split it into parts of 2
                  #  i.e. [[2,3],[2],[1],[3,1]] → [[[2,3],[2]],[[1],[3,1]]]
                  #  i.e. [[2,3,2],[1,3],[1]] → [[[2,3,2],[1,3]],[[1]]]
      ζ           # Swap rows and columns (using space as filler if necessary)
                  #  i.e. [[[2,3],[2]],[[1],[3,1]]] → [[[2,3],[1]],[[2],[3,1]]]
                  #  i.e. [[[2,3,2],[1,3]],[[1]]] → [[[2,3,2],[1]],[[1,3]," "]]
       ε  }       # Map each inner list to:
        ˜         # Flatten the list
                  #  i.e. [[2,3],[1]] → [2,3,1]
                  #  i.e. [[1,3]," "] → [1,3," "]
         {        # Sort the list
                  #  i.e. [2,3,1] → [1,2,3]
                  #  i.e. [1,3," "] → [1,3," "]
           Ë      # Check if both sorted lists are equal
                  # (if not, remove them from the partitions)
             ¤    # After filtering, take the last one as result (and output implicitly)
                  #  i.e. [[[2],[3,2],[1,3],[1]],[[2,3],[2],[1],[3,1]]]
                  #   → [[2,3],[2],[1],[3,1]]