Finden Sie alle eindeutigen Gozinta-Ketten

36

Gozinta-Ketten

(Inspiriert von Project Euler # 606 )

Eine Gozinta-Kette für n ist eine Folge, {1,a,b,...,n}bei der jedes Element das nächste korrekt teilt. Zum Beispiel gibt es acht verschiedene Gozinta-Ketten für 12:

{1,12}, {1,2,12}, {1,2,4,12}, {1,2,6,12}, {1,3,12}, {1,3,6,12}, {1,4,12} and {1,6,12}.

Die Herausforderung

Schreiben Sie ein Programm oder eine Funktion, die eine positive Ganzzahl ( n > 1) akzeptiert und alle eindeutigen Gozinta-Ketten für die angegebene Zahl ausgibt oder zurückgibt.

  1. Reihenfolge in den Ketten ist wichtig (aufsteigend), Reihenfolge der Ketten nicht.
  2. Wenn es keine Chance gibt, können Sie kein eingebautes System verwenden, das die Herausforderung löst.
  3. Das ist .

Bearbeiten: Entfernen 1als mögliche Eingabe.

Regenschirm
quelle
4
Willkommen bei PPCG. Schöne erste Frage!
AdmBorkBork
5
"Zufällig existiert es [(schaut dich an, Mathematica!)]"
Erik der Outgolfer
3
Wie AdmBorkBork sagte, werden Edge-Cases im Allgemeinen nur dann hinzugefügt, wenn sie für den Kern der Herausforderung von Bedeutung sind. Wenn Sie einen Grund dafür haben möchten, [[1]]würde ich sagen, dass wenn [1,1]ein Gozinta von 1dann [1,1,12]ein Gozinta von 12so ist, wie es ist, [1,1,1,12]und jetzt können wir nicht mehr "alle zurück ..."
Jonathan Allan
4
Sie sollten das Wortspiel in der Frage für diejenigen klarstellen, die es nicht kennen. 2|4wird gelesen "zwei geht in vier" aka "zwei gozinta vier".
mbomb007
1
Zweieinhalb Stunden reichen nicht aus, damit der Sandkasten funktioniert. Siehe die Sandbox-FAQ .
Peter Taylor

Antworten:

10

Python 3 , 68 65 Bytes

Edit: -3 Bytes dank @notjagan

f=lambda x:[y+[x]for k in range(1,x)if x%k<1for y in f(k)]or[[x]]

Probieren Sie es online!

Erläuterung

Jede Gozinta-Kette besteht aus der Nummer xam Ende der Kette mit mindestens einem Teiler links davon. Für jeden Divisor kvon xden Ketten [1,...,k,x]unterscheiden. Wir können daher für jeden Divisor kalle seine unterschiedlichen Gozinta-Ketten finden und xan deren Ende anhängen , um alle unterschiedlichen Gozinta-Ketten mit kdirekt links von zu erhalten x. Dies erfolgt rekursiv , bis x = 1wo [[1]]zurückgegeben wird, da alle gozinta Ketten mit 1 beginnen, was bedeutet , die Rekursion haben die Talsohle erreicht.

Der Code wird aufgrund des Verständnisses der Python-Liste so kurz, dass eine doppelte Iteration möglich ist. Dies bedeutet, dass die in gefundenen Werte f(k)für alle verschiedenen Teiler derselben Liste hinzugefügt werden können k.

Halvard Hummel
quelle
versuchte dies jetzt zu spät = /
Rod
3
Diese Antwort ist im Vergleich zu den bisherigen unglaublich schnell.
Ajc2000
-3 Bytes durch Entfernen der unnötigen Liste entpacken.
Notjagan
7

Schale , 13 Bytes

ufo=ḣ⁰…ġ¦ΣṖḣ⁰

Ein etwas anderer Ansatz als der von H.PWiz , wenn auch immer noch mit roher Gewalt. Probieren Sie es online!

Erläuterung

Die Grundidee ist, alle [1,...,n]Teilsequenzen zu verketten und das Ergebnis in Teillisten aufzuteilen, in denen jedes Element das nächste teilt. Von diesen behalten wir diejenigen, die mit beginnen 1, enden nund keine Duplikate enthalten. Dies geschieht mit der eingebauten Funktion "rangify" . Dann bleibt es, Duplikate zu verwerfen.

ufo=ḣ⁰…ġ¦ΣṖḣ⁰  Input is n=12.
           ḣ⁰  Range from 1: [1,2,..,12]
          Ṗ    Powerset: [[],[1],[2],[1,2],[3],..,[1,2,..,12]]
         Σ     Concatenate: [1,2,1,2,3,..,1,2,..,12]
       ġ¦      Split into slices where each number divides next: [[1,2],[1,2],[3],..,[12]]
 fo            Filter by
      …        rangified
   =ḣ⁰         equals [1,...,n].
u              Remove duplicates.
Zgarb
quelle
Ich vermute, es ist nicht kürzer, nach den Arrays im Powerset zu filtern, in denen jede Zahl die nächste teilt.
ETHproductions
@ETHproductions Nein, das ist ein Byte länger .
Zgarb
5

Gelee , 9 8 Bytes

ÆḌ߀Ẏ;€ȯ

Probieren Sie es online!

Verwendet eine ähnliche Technik wie meine Japt-Antwort und läuft daher bei größeren Testfällen sehr schnell.

Wie es funktioniert

ÆḌ߀Ẏ;€ȯ    Main link. Argument: n (integer)
ÆḌ          Yield the proper divisors of n.
       ȯ    If there are no divisors, return n. Only happens when n is 1.
  ߀        Otherwise, run each divisor through this link again. Yields
            a list of lists of Gozinta chains.
    Ẏ       Tighten; bring each chain into the main list.
     ;€     Append n to each chain.
ETHproductions
quelle
4

Mathematica, 77 Bytes

FindPath[Graph@Cases[Divisors@#~Subsets~{2},{m_,n_}/;m∣n:>m->n],1,#,#,All]&

Bildet eine Stelle, Graphan der die Scheitelpunkte Divisorsder Eingabe #sind und die Kanten die richtige Teilbarkeit darstellen, und findet dann AllPfade vom Scheitelpunkt 1zum Scheitelpunkt #.

Genisis
quelle
1
Woah, das ist ziemlich schlau!
JungHwan Min
3

Gelee , 12 Bytes

ŒPµḍ2\×ISµÐṀ

Ein monadischer Link, der eine Ganzzahl akzeptiert und eine Liste mit Ganzzahllisten zurückgibt.

Probieren Sie es online!

Wie?

Wir möchten, dass alle sortierten Listen eindeutiger Ganzzahlen zwischen eins und N so sind, dass die erste eine Eins ist, die letzte N ist und sich alle Paare teilen. Der Code erreicht diesen Filter, indem er überprüft, ob die paarweisen Teilungskriterien über die Potenzmenge des fraglichen Bereichs erfüllt sind, aber nur diejenigen auswählt, deren maximale inkrementelle Differenzsummen (die beide mit eins beginnen und mit N enden) eine Summe von inkrementellen Differenzen von N-1, andere haben weniger).

ŒPµḍ2\×ISµÐṀ - Link: number N
ŒP           - power-set (implicit range of input) = [[1],[2],...,[N],[1,2],[1,3],...,[1,N],[1,2,3],...]
          ÐṀ - filter keep those for which the result of the link to the left is maximal:
  µ      µ   - (a monadic chain)
    2\       -   pairwise overlapping reduce with:
   ḍ         -     divides? (1 if so, 0 otherwise)
       I     -   increments  e.g. for [1,2,4,12] -> [2-1,4-2,12-4] = [1,2,8]
      ×      -   multiply (vectorises) (no effect if all divide,
             -                          otherwise at least one gets set to 0)
        S    -   sum         e.g. for [1,2,4,12] -> 1+2+8 = 11 (=12-1)
Jonathan Allan
quelle
Warten Sie, es gibt n-weise Überlappung zu reduzieren? : o wie habe ich das nie gesehen: PI benutzte <slice>2<divisible>\<each>: P
HyperNeutrino
Mit der neuesten Änderung in Jellys Quick-Dateien können Sie Ɲanstelle von '2' für 11 Bytes verwenden .
Mr. Xcoder
3

Japt , 17 Bytes

⬣ßX m+S+UR÷ª'1

Online testen!

Seltsamerweise war das Generieren der Ausgabe als String viel einfacher als das Generieren als Array von Arrays ...

Erläuterung

 ⬠£  ßX m+S+URà ·  ª '1
Uâq mX{ßX m+S+UR} qR ||'1   Ungolfed
                            Implicit: U = input number, R = newline, S = space
Uâ                          Find all divisors of U,
  q                           leaving out U itself.
    mX{         }           Map each divisor X to
       ßX                     The divisor chains of X (literally "run the program on X")
          m    R              with each chain mapped to
           +S+U                 the chain, plus a space, plus U.
                  qR        Join on newlines.
                     ||     If the result is empty (only happens when there are no factors, i.e. U == 1)
                       '1     return the string "1".
                            Otherwise, return the generated string.
                            Implicit: output result of last expression
ETHproductions
quelle
Vermeidet Ihr Ansatz also, ungültige Ketten zu generieren und diese dann zu filtern, wie es bei anderen Ansätzen der Fall ist?
Umbrella
@Umbrella Nein, es werden nur die jeweils gültigen Divisoren generiert, weshalb es auch in Fällen wie 12000 blitzschnell funktioniert :-)
ETHproductions
Sehr gute Verwendung der Rekursion :) Und ich mache diesen ¬Trick fertig ! : p
Shaggy
@Shaggy ¬ist einer der Gründe, warum ich eine Reihe von Funktionen implementiert habe, die im Grunde genommen "do X ohne Argumente oder Y mit wahrheitsgemäßen Argumenten" lauten: P
ETHproductions
3

Mathematica, 60 Bytes

Cases[Subsets@Divisors@#,x:{1,___,#}/;Divisible@@Reverse@{x}]&

Verwendet die ohne Papiere Multi arg Form Divisible, wo Divisible[n1,n2,...]Renditen , Truewenn n2∣n1, n3∣n2und so weiter, und aus Falseanderen Gründen . Wir nehmen die gesamte SubsetsListe Divisorsder Eingaben #und geben dann die Casesder Form zurück {1,___,#}, Divisibledie Truefür die Reversed-Folge von Teilern gilt.

Genisis
quelle
Also, Divisibleist es im Grunde genommen eine eingebaute Funktion, um eine Gozinta-Kette zu verifizieren?
Regenschirm
@Umbrella Es wird nicht die richtige Teilbarkeit überprüft.
Genisis
3

Haskell, 51 Bytes

f 1=[[1]]
f n=[g++[n]|k<-[1..n-1],n`mod`k<1,g<-f k]

Finden Sie rekursiv Gozinta-Ketten der richtigen Teiler und hängen Sie an n.

Probieren Sie es online!

Christian Sievers
quelle
Ich bin der Meinung, dass für eine ordnungsgemäße Handhabung zusätzliche Gutschrift erforderlich ist 1. Können 1Sie 10 Byte einsparen, indem Sie diesen Fall entfernen, da wir gemeinsam eine Ausnahme beschlossen haben?
Regenschirm
@Umbrella 1ist kein Sonderfall für diesen Algorithmus, sondern wird als Basisfall für die Rekursion benötigt. Die zweite definierende Gleichung kann für sich genommen nur die leere Liste zurückgeben.
Christian Sievers
Aha. Meine (noch nicht hochgeladene) Lösung dient auch [[1]]als Basis.
Regenschirm
3

Haskell (Lambdabot), 92 85 Bytes

x#y|x==y=[[x]]|1>0=(guard(mod x y<1)>>(y:).map(y*)<$>div x y#2)++x#(y+1)
map(1:).(#2)

Benötigt Lambdabot Haskell da guarderfordert Control.Monadimportiert werden. Die Hauptfunktion ist eine anonyme Funktion, von der mir gesagt wurde, dass sie zulässig ist und ein paar Bytes abschneidet.

Vielen Dank an Laikoni für das Speichern von sieben Bytes.

Erläuterung:

Monaden sind sehr praktisch.

x # y

Dies ist unsere rekursive Funktion, die die gesamte eigentliche Arbeit erledigt. xist die Zahl, über die wir akkumulieren (das Produkt der Divisoren, die im Wert verbleiben), und yist die nächste Zahl, die wir versuchen sollten, darin zu dividieren.

 | x == y = [[x]]

Wenn xgleich, ydann sind wir mit der Rekursion fertig. Verwenden Sie es einfach xals Ende der aktuellen Gozinta-Kette und senden Sie es zurück.

 | 1 > 0 =

Haskell Golf-Ismus für "True". Das heißt, dies ist der Standardfall.

(guard (mod x y < 1) >>

Wir arbeiten jetzt in der Listenmonade. Innerhalb der Listenmonade haben wir die Möglichkeit, mehrere Entscheidungen gleichzeitig zu treffen. Dies ist sehr hilfreich, wenn Sie durch Erschöpfung "alles Mögliche" für etwas finden. In der guardAnweisung heißt es: "Betrachten Sie die folgende Auswahl nur, wenn eine Bedingung erfüllt ist." Berücksichtigen Sie in diesem Fall nur die folgende Auswahl, wenn ydividiert wird x.

(y:) . map (y *) <$> div x y#2)

Wenn ysich teilt x, haben wir die Wahl y, die Gozinta-Kette zu ergänzen. In diesem Fall rufen Sie rekursiv (#)beginnend y = 2mit xgleich auf x / y, da wir "herausrechnen" möchten, was ywir gerade zur Kette hinzugefügt haben. Unabhängig vom Ergebnis dieses rekursiven Aufrufs multiplizieren Sie dann die Werte, indem Sie die Gozinta-Kette offiziell ausklammern yund ergänzen y.

++

Betrachten Sie auch die folgende Auswahl. Dies addiert einfach die beiden Listen, aber wir können uns das monadisch so vorstellen, als ob wir "wählen, ob wir dieses Ding oder dieses andere Ding machen".

x # (y + 1)

Die andere Möglichkeit besteht darin, einfach weiter zu rekursieren und den Wert nicht zu verwenden y. Wenn ysich nicht teilt, xist dies die einzige Option. Wenn dies der yFall ist, xwird diese Option ebenso wie die andere Option verwendet und die Ergebnisse werden kombiniert.

map (1 :) . (# 2)

Dies ist die Hauptfunktion von gozinta. Es beginnt die Rekursion, indem es (#)mit seinem Argument aufruft . A 1wird jeder gozinta-Kette vorangestellt, weil die (#)Funktion niemals eine in die Ketten einfügt .

Silvio Mayolo
quelle
1
Tolle Erklärung! Sie können einige Bytes sparen, indem Sie die Pattern-Guards in eine Zeile setzen. mod x y==0kann auf gekürzt werden mod x y<1. Da anonyme Funktionen erlaubt sind, kann Ihre Hauptfunktion als frei geschrieben werden map(1:).(#2).
Laikoni,
3

Haskell, 107 100 95 Bytes

f n=until(all(<2).map head)(>>=h)[[n]]
h l@(x:_)|x<2=[l]|1<2=map(:l)$filter((<1).mod x)[1..x-1]

Vielleicht gibt es eine bessere Kündigungsbedingung (probiert so etwas wie

f n=i[[n]]
i x|g x==x=x|1<2=i$g x
g=(>>=h)

aber es ist länger). Die Überprüfung auf 1erscheint sinnvoll, da das Löschen von Wiederholungen 1oder Duplikaten ( nubnicht in Prelude) mehr Bytes umfasst.

Probieren Sie es online aus.

Leif Willerts
quelle
3
(>>=h)für(concatMap h)
Michael Klein
95 Bytes
Cristian Lupascu
Heiliger Mist, bin ich dumm wegen u...
Leif Willerts
3

JavaScript (Firefox 30-57), 73 Byte

f=n=>n>1?[for(i of Array(n).keys())if(n%i<1)for(j of f(i))[...j,n]]:[[1]]

Günstigerweise n%0<1ist falsch.

Neil
quelle
2

Gelee , 17 Bytes

ḊṖŒP1ppWF€ḍ2\Ạ$Ðf

Probieren Sie es online!

Erik der Outgolfer
quelle
Das war beeindruckend schnell. Ihr Ergebnis für 1ist jedoch unerwartet. Ich habe es nicht geschafft, ein endgültiges Ergebnis für zu finden 1, aber ich nahm an, es war [[1]]. Ich kann nicht sicher sagen, dass [1,1]das falsch ist, außer dass alle anderen Ergebnisse aufsteigende Sequenzen sind. Gedanken?
Umbrella
@Umbrella Vielleicht möchten Sie die Antworten für 1.
Mr. Xcoder
@Umbrella Wenn es ein Problem ist ich kann es fix für 2 (ersetzen ;€mit ;Q¥€).
Erik der Outgolfer
2

Mathematica, 104 Bytes

(S=Select)[Rest@S[Subsets@Divisors[t=#],FreeQ[#∣#2&@@@Partition[#,2,1],1>2]&],First@#==1&&Last@#==t&]&
J42161217
quelle
FreeQ[...]kann werdenAnd@@BlockMap[#∣#2&@@#&,#,2,1]
JungHwan Min
Sehr schön! aber ich bekomme eine extra Meldung DeveloperPartitionMap :: nlen: - Meldungstext nicht gefunden - >> `warum ist das so?
J42161217
BlockMapVerwendet die Developer`PartitionMapFunktion intern. Da es sich jedoch um eine Entwicklerfunktion handelt, werden keine Fehlermeldungen angezeigt. Der Fehler wird durch die Listen mit 1 oder 0 Elementen verursacht, mit denen Sie keine 2-Partitionen erstellen können.
JungHwan Min
2

Mathematica, 72 Bytes

Cases[Subsets@Divisors@#,{1,___,#}?(And@@BlockMap[#∣#2&@@#&,#,2,1]&)]&

Erläuterung

Divisors@#

Finde alle Teiler der Eingabe.

Subsets@ ...

Generieren Sie alle Untergruppen dieser Liste.

Cases[ ... ]

Wählen Sie alle Fälle aus, die dem Muster entsprechen ...

{1,___,#}

Beginnend mit 1 und endend mit <input>...

?( ... )

und erfüllt die Bedingung ...

And@@BlockMap[#∣#2&@@#&,#,2,1]&

Das linke Element teilt das rechte Element für alle 2-Partitionen der Liste, Offset 1.

JungHwan min
quelle
2

TI-BASIC, 76 Bytes

Input N
1→L1(1
Repeat Ans=2
While Ans<N
2Ans→L1(1+dim(L1
End
If Ans=N:Disp L1
dim(L1)-1→dim(L1
L1(Ans)+L1(Ans-(Ans>1→L1(Ans
End

Erläuterung

Input N                       Prompt user for N.
1→L1(1                        Initialize L1 to {1}, and also set Ans to 1.

Repeat Ans=2                  Loop until Ans is 2.
                              At this point in the loop, Ans holds the
                              last element of L1.

While Ans<N                   While the last element is less than N,
2Ans→L1(1+dim(L1              extend the list with twice that value.
End

If Ans=N:Disp L1              If the last element is N, display the list.

dim(L1)-1→dim(L1              Remove the last element, and place the new
                              list size in Ans.

L1(Ans)+L1(Ans-(Ans>1→L1(Ans  Add the second-to-last element to the last
                              element, thereby advancing to the next
                              multiple of the second-to-last element.
                              Avoid erroring when only one element remains
                              by adding the last element to itself.

End                           When the 1 is added to itself, stop looping.

Ich könnte weitere 5 Bytes einsparen, wenn es erlaubt ist, mit einem Fehler statt ordnungsgemäß zu beenden, indem die Ans> 1-Prüfung und die Schleifenbedingung entfernt werden. Aber ich bin nicht sicher, ob das erlaubt ist.

calc84maniac
quelle
Hast du das in deinen Taschenrechner eingegeben? Weil das unerwartet und etwas beeindruckend ist.
Regenschirm
Ja! Das Knifflige an TI-BASIC ist, dass es nur globale Variablen gibt. Daher musste ich die Liste selbst effektiv als meinen Rekursionsstapel verwenden.
calc84maniac
2

Mathematica 86 77 Bytes

Select[Subsets@Divisors@#~Cases~{1,___,#},And@@BlockMap[#∣#2&@@#&,#,2,1]&]&

Brute Force nach Definition.

Ich wünschte, es gäbe eine kürzere Möglichkeit, einen paarweisen Vergleich von Elementen einer Liste durchzuführen.

Vielen Dank an @Jenny_mathy und @JungHwanMin für die Vorschläge zur Einsparung von 9 Bytes

Kelly Lowder
quelle
1
Mit FreeQ[#∣#2&@@@Partition[#,2,1],1>2]&](als zweites Argument) können Sie zu 82 Bytes
wechseln
@Jenny_mathy Oder besserAnd@@BlockMap[#∣#2&@@#&,#,2,1]
JungHwan Min
1

Schale , 17 16 Bytes

-1 Byte, danke an Zgarb

foEẊ¦m`Je1⁰Ṗthḣ⁰

Probieren Sie es online!

H.PWiz
quelle
Kurz, aber langsam. Ich habe 50den Eingang eingegeben und es ist abgelaufen. Was ist der Kern Ihres Ansatzes?
Umbrella
Es versucht im Wesentlichen alle möglichen Ketten und wählt diejenigen, die der Spezifikation entsprechen
H.PWiz
@Umbrella TIO hat ein Timeout von 60 Sekunden, es ist nicht die Schuld des Programms.
Erik der Outgolfer
o`:⁰:1kann sein`Je1⁰
Zgarb
@Zgarb Noch einmal ...
H.PWiz
0

PHP 147 141

Bearbeitet, um einen redundanten Test zu entfernen

function g($i){$r=[[1]];for($j=2;$j<=$i;$j++)foreach($r as$c)if($j%end($c)<1&&$c[]=$j)$r[]=$c;foreach($r as$c)end($c)<$i?0:$R[]=$c;return$R;}

Erklärt:

function g($i) {

15 Zeichen Boilerplate :(

    $r = [[1]];

Initialisieren Sie die Ergebnismenge auf, [[1]]da jede Kette mit 1 beginnt. Dies führt auch zur Unterstützung von 1 als Eingabe.

    for ($j = 2; $j <= $i; $j++) {
        foreach ($r as $c) {
            if ($j % end($c) < 1) {
                $c[] = $j;
                $r[] = $c;
            }
        }
    }

Für jede Zahl von 2 bis $iwerden wir jede Kette in unserer Menge um die aktuelle Zahl verlängern, wenn dies möglich ist. Fügen Sie dann die verlängerte Kette zu unserer Ergebnismenge hinzu.

    foreach ($r as $c) {
        end($c) < $i ? 0 : $R[] = $c;
    }

Filtern Sie unsere Zwischenketten heraus, die es nicht geschafft haben $i

    return $R;
}

10 Zeichen Boilerplate :(

Regenschirm
quelle
-1

Mathematica

f[1] = {{1}};
f[n_] := f[n] = Append[n] /@ Apply[Join, Map[f, Most@Divisors@n]]

Die Antwort wird für weitere Anrufe zwischengespeichert.

BoLe
quelle
1
Willkommen auf der Seite! Dies ist ein Code-Golf, also sollten Sie Ihre Byteanzahl angeben und zusätzlich versuchen, alle zusätzlichen Leerzeichen zu entfernen, von denen ich vermute, dass Sie welche haben.
Wheat Wizard