Sie kennen den Mathematiker von Koch vielleicht an seiner berühmten Schneeflocke. Er hat jedoch interessantere Informatikprobleme im Ärmel. Schauen wir uns diese Vermutung an:

Gegeben ein Baum mit nKnoten (also n-1Kanten). Finden Sie einen Weg, um die Knoten von 1bis nund dementsprechend die Kanten von 1bis n-1so aufzulisten, dass für jede Kante kdie Differenz ihrer Knotennummern gleich ist k. Die Vermutung ist, dass dies immer möglich ist.

Hier ist ein Beispiel, um es klar zu machen:

DEINE AUFGABE

Ihr Code verwendet als Eingabe einen Baum. Sie können das gewünschte Format verwenden. Für die Testfälle werde ich den Baum anhand der Bögen und der Liste der Knoten bereitstellen.

Dies ist beispielsweise die Eingabe für den Baum im Bild:

[a,b,c,d,e,f,g]
d -> a
a -> b
a -> g
b -> c
b -> e
e -> f

Ihr Code muss den Baum mit nummerierten Knoten und Kanten zurückgeben. Sie können eine grafischere Ausgabe zurückgeben, aber ich werde diese Art von Ausgabe für die Testfälle bereitstellen:

[a7,b3,c6,d1,e5,f4,g2]
d -> a 6
a -> b 4
a -> g 5
b -> c 3
b -> e 2
e -> f 1

TESTFÄLLE

[a,b,c,d,e,f,g]             [a7,b3,c6,d1,e5,f4,g2]
d -> a                      d -> a 6
a -> b                      a -> b 4
a -> g             =>       a -> g 5
b -> c                      b -> c 3
b -> e                      b -> e 2
e -> f                      e -> f 1


[a,b,c,d]                   [a4,b1,c3,d2]
a -> b                      a -> b 3
b -> c            =>        b -> c 2
b -> d                      b -> d 1


[a,b,c,d,e]                [a2,b3,c1,d4,e5]
a -> b                      a -> b 1
b -> c                      b -> c 2
c -> d             =>       c -> d 3
c -> e                      c -> e 4

Dies ist Code-Golf, dies ist die kürzeste Antwort in Bytes Win!

Hinweis: Dies ist stärker als die Ringel-Kotzig-Vermutung , wonach jeder Baum eine anmutige Kennzeichnung hat. Da es in der Koch-Vermutung nicht möglich ist, Ganzzahlen für die Kennzeichnung zu überspringen, entgegen der anmutigen Kennzeichnung in der Ringel-Kotzig-Vermutung. Graceful Kennzeichnung wurde vor gefragt hier .

Gelee , 30 Bytes

JŒ!³,$€
ǵy⁴VIAµ€Q⁼$€TðḢịø³JŒ!

Probieren Sie es online aus! ( GṄ³çGAls Fußzeile verwenden, um die Ausgabe schöner zu gestalten.)

Eingaben ähnlich wie Beispiel, zB abcdefund[d,a],[a,b],[a,g],[b,c],[b,e],[e,f]

Gibt die Liste zB a,b,c,d,e,fin der Reihenfolge aus.

Hinweis: Mein Programm erzeugt andere Werte als die Testfälle, da es mehrere Möglichkeiten gibt, die alle gültig sind.

Erläuterung

JŒ!³,$€                - helper function, generates all possible numberings, input is e.g. 'abcd'
J                      - range(len(input)). e.g. [1,2,3,4]
 Œ!                    - all permutations of the range.
   ³,$                 - pair the input with ... 
      €                - each permutation. Sample element e.g. ['abcd',[3,1,2,4]]

ǵy⁴VIAµ€Q⁼$€TðḢịø³JŒ! - main dyadic link, input is e.g. 'abcd' and '[a,b],[b,c],[b,d]'
 µy                    - use a numbering as an element-wise mapping e.g. 'abcd'->[3,1,2,4]
   ⁴                   - apply this to the list of edges. e.g. '[3,1],[1,2],[1,4]'
    V                  - turn this into an internal list.
     IAµ€              - find absolute difference on each edge
         Q⁼            - Is this invariant under deduplication? Returns 1 if the numbering is valid; 0 otherwise.
Ç          $€          - apply this to all possible numberings
             Tð        - return the indices of all valid numberings
               Ḣ       - choose the first one and
                ị      - get the element corresponding to its index in 
                 ø³JŒ! - all possible numberings 

Sparen Sie 1 Byte, indem Sie alle möglichen Lösungen anzeigen:

JŒ!³,$€
ǵy⁴VIAµ€Q⁼$€Tðịø³JŒ!

Probieren Sie es online aus! ( GṄ³çG⁷³GAls Fußzeile verwenden, um die Ausgabe schöner zu gestalten)

Verwenden Sie den Konverter , um den Testfall in eine Eingabeliste zu kopieren und einzufügen.

Ruby, 108 Bytes

Die Lamba-Funktion akzeptiert ein Array von 2-Element-Arrays, die die Kanten enthalten (wobei jede Kante als Zahlenpaar ausgedrückt wird, das den relevanten Noten entspricht.)

->a{[*1..1+n=a.size].permutation.map{|i|k=a.map{|j|(i[j[0]-1]-i[j[1]-1]).abs}
(k&k).size==n&&(return[i,k])}}

Ungolfed im Testprogramm

f=->a{                                    #Accept an array of n tuples (where n is the number of EDGES in this case)
  [*1..1+n=a.size].permutation.map{|i|    #Generate a range 1..n+1 to label the nodes, convert to array, make an array of all permutations and iterate through it.
    k=a.map{|j|(i[j[0]-1]-i[j[1]-1]).abs} #Iterate through a, build an array k of differences between nodes per current permutation, as a trial edge labelling.
    (k&k).size==n&&(return[i,k])          #Intersect k with itself to remove duplicates. If all elements are unique the size will still equal n so
  }                                       #return a 2 element array [list of nodes, list of edges]
}

p f[[[4,1],[1,2],[1,7],[2,3],[2,5],[5,6]]]

p f[[[1,2],[2,3],[2,4]]]

p f[[[1,2],[2,3],[3,4],[2,5]]]

Ausgabe

Die Ausgabe ist ein Array mit 2 Elementen, das Folgendes enthält:

die neue Knotennummerierung

die Kantennummerierung.

Beispielsweise befindet sich die erste Kante des ersten Beispiels [4,1]zwischen den Knoten 6 und 1 unter der neuen Knotennummerierung und ist daher die Kante 6-1 = 5.

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

Tatsächlich gibt es für jeden Testfall mehrere Lösungen. Das returnstoppt die Funktion, sobald die erste gefunden wurde.