Eine Reihe n
positiver Zahlen enthält 2^n
Teilmengen. Wir nennen eine Menge "nice", wenn keine dieser Teilmengen dieselbe Summe hat. {2, 4, 5, 8}
ist so ein schönes Set. Da keine der Teilmengen dieselbe Summe hat, können wir die Teilmengen nach Summe sortieren:
[{}, {2}, {4}, {5}, {2, 4}, {2, 5}, {8}, {4, 5}, {2, 8}, {2, 4, 5}, {4, 8}, {5, 8}, {2, 4, 8}, {2, 5, 8}, {4, 5, 8}, {2, 4, 5, 8}]
Wenn wir die Zahlen in aufsteigender Reihenfolge [2, 4, 5, 8]
mit den Symbolen beschriften [a, b, c, d]
, erhalten wir die folgende abstrakte Reihenfolge:
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}]
Ein anderer netter Satz positiver Zahlen kann dieselbe oder eine andere abstrakte Reihenfolge haben. Ist zum Beispiel [3, 4, 8, 10]
ein schönes Set mit einer anderen abstrakten Reihenfolge:
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}]
In dieser Herausforderung müssen Sie die Anzahl der eindeutigen abstrakten Anordnungen von netten Sätzen n
positiver Zahlen zählen. Diese Sequenz ist OEIS A009997 , und die bekannten Werte, beginnend mit n=1
, sind:
1, 1, 2, 14, 516, 124187, 214580603
Zum Beispiel sind n=3
die folgenden zwei möglichen abstrakten Ordnungen:
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}]
Im n=4
Folgenden sind die 14 möglichen abstrakten Ordnungen sowie ein Beispielsatz mit dieser Ordnung aufgeführt:
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}, {d}, {a, d}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 4, 2, 1]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {d}, {a, b, c}, {a, d}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 6, 3, 2]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 7, 4, 2]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {d}, {a, d}, {b, c}, {a, b, c}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 4, 1]
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 8, 4, 3]
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {a, d}, {b, c}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 7, 4, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}, {d}, {a, d}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 4, 3, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {d}, {a, b, c}, {a, d}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 4, 3, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 5, 4, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {a, d}, {b, c}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 7, 6, 2]
[{}, {a}, {b}, {c}, {a, b}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 4, 3]
[{}, {a}, {b}, {c}, {a, b}, {d}, {a, c}, {a, d}, {b, c}, {b, d}, {a, b, c}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 8, 6, 3]
[{}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {b, c}, {a, d}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 5, 4]
[{}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [7, 6, 5, 3]
Folgendes ist keine gültige abstrakte Reihenfolge:
{}, {a}, {b}, {c}, {d}, {a,b}, {e}, {a,c}, {b,c}, {a,d}, {a,e}, {b,d}, {b,e}, {c,d}, {a,b,c}, {a,b,d}, {c,e}, {d,e}, {a,b,e}, {a,c,d}, {a,c,e}, {b,c,d}, {b,c,e}, {a,d,e}, {b,d,e}, {a,b,c,d}, {c,d,e}, {a,b,c,e}, {a,b,d,e}, {a,c,d,e}, {b,c,d,e}, {a,b,c,d,e}
Diese Bestellung impliziert, dass:
d < a + b
b + c < a + d
a + e < b + d
a + b + d < c + e
Die Summe dieser Ungleichungen ergibt:
2a + 2b + c + 2d + e < 2a + 2b + c + 2d + e
Das ist ein Widerspruch. Ihr Code darf diese Bestellung nicht mitzählen. Solche Gegenbeispiele tauchen zunächst bei auf n=5
. Beispiel aus diesem Artikel , Beispiel 2.5 auf Seite 3.
Diese Reihenfolge ist ungültig , trotz der Tatsache , dass A < B
das bedeutet A U C < B U C
, für jeden C
disjunkt A
und B
.
Ihr Code oder Programm muss schnell genug sein, damit Sie es bis zur Fertigstellung ausführen können, n=4
bevor Sie es senden.
Einsendungen können wie gewohnt Programme, Funktionen usw. sein.
Standardlücken sind wie immer verboten. Dies ist Codegolf, daher gewinnt die kürzeste Antwort in Bytes. Fühlen Sie sich frei, in den Kommentaren klärende Fragen zu stellen.
quelle
Antworten:
Python 3 + SciPy,
396390385351336355 BytesProbieren Sie es online!
Dies dauert nun n = 5 in ca. 5 Sekunden. Das
if~-(v in u):
kann für −18 Bytes entfernt werden, ist aber eine enorme Leistungseinbuße.Wenn Sie alle abstrakten Ordnungen drucken möchten, anstatt sie nur zu zählen, fügen Sie sie
if c:print(s.x.round(),y)
vor derfor
Schleife hinzu. (Teilmengen werden durch binäre Ganzzahlen dargestellt, wobei jedes Bit dem Vorhandensein oder Fehlen eines Elements entspricht: { a , c , d } ↔ 1101₂ = 13.)Wie es funktioniert
f
zählt rekursiv die abstrakten Ordnungen, die eine gegebene Liste von Beschränkungen erfüllen. Wir beginnen mit den Bedingungen n ≤ a , a + n ≤ b , b + n ≤ c , c + n ≤ d . Mit linearer Programmierung finden wir eine Lösung für die Einschränkungen (oder geben 0 zurück, wenn es keine gibt) - in diesem Fall erhalten wir a = 4, b = 8, c = 12, d = 16. Wir runden die Lösung auf ganze Zahlen Berechnen Sie dann eine Referenzreihenfolge, indem Sie alle Teilmengen nach ihrer Summe sortieren:{ a }, { b }, { c }, { a , b }, { d }, { a , c }, { a , d }, { b , c }, { b , d }, { a , b , c }, { c , d }, { a , b , d }, { a , c , d }, { b , c , d }, {a , b , c , d }
Die Rundung kann nicht dazu führen, dass Einschränkungen um mehr als n / 2 verletzt werden. Aus diesem Grund haben wir einen Rand von n hinzugefügt .
Da Python's
sorted
stabil ist, werden alle Bindungen zwischen den Teilmengen in derselben umgekehrten lexikografischen Reihenfolge unterbrochen, in der wir sie generiert haben. Wir könnten uns also vorstellen, { a , b , c , d } durch { a · 2 ^ n + 2 ^ 0, b · 2 ^ n + 2 ^ 1, c · 2 ^ n + 2 ^ 2, d · 2 ^ zu ersetzen n + 2 ^ 3}, um die gleiche Bestellung ohne Krawatten zu erhalten.Es ist geplant, alle anderen abstrakten Sortierungen anhand einer Fallanalyse zu kategorisieren, basierend darauf, wo sie zuerst mit der Referenzsortierung nicht übereinstimmen:
Entweder { a }> { b }
oder { a } <{ b }> { c }
oder { a } <{ b } <{ c }> { a , b }
oder { a } <{ b } < { c } <{ a , b }> { d },
⋮
In jedem Fall fügen wir diese neuen Bedingungen mit einem Rand von n hinzu und rufen sie rekursiv
f
mit den neuen hinzugefügten Bedingungen auf.Anmerkungen
Für eine Weile vermutete ich (aber ging nicht davon aus), dass die linearen Programmlösungen mit Rand 1 für die Einschränkungen immer ganze Zahlen sein werden. Dies stellt sich als falsch heraus: Ein Gegenbeispiel mit n = 7 ist {2,5, 30, 62,5, 73,5, 82, 87,5, 99,5}.
Python, 606 Bytes (schneller, keine externen Bibliotheken)
Probieren Sie es online!
Dies dauert n = 5 in einer Viertelsekunde und n = 6 in 230 Sekunden (75 Sekunden in PyPy).
Es enthält einen handcodierten linearen Programmierlöser, der Ganzzahl-Mathematik in homogenen Koordinaten verwendet, um Gleitkomma-Rundungsprobleme zu vermeiden.
quelle
options={'tol':.1}
, das scheint das Problem zu lösen.Ruby, 308 Bytes, viel schneller
Läuft der Fall 4 in ~ 150ms. Es wird keine Spezialbibliothek verwendet.
Es durchsetzt beispielsweise rekursiv das Ergebnis eines kleinen Falls
Mit den entsprechenden Teilmengen, denen ein zusätzliches Element hinzugefügt wurde, muss die relative Reihenfolge beibehalten werden. Außerdem wird sichergestellt, dass der neue Singleton nach allen vorherigen Singletons hinzugefügt wird.
Der Teil, der die Konformität überprüft, ist derselbe wie zuvor, aber die zu testenden Kombinationen sind viel weniger.
Erweiterte und kommentierte Version:
Ruby, 151 Bytes, ziemlich langsam
(Der Fall von drei Elementen dauert << 1s, der Fall von vier Elementen läuft noch)
Es funktioniert mit der Bitfelddarstellung der Teilmengen, daher muss man möglicherweise die Ausgabe massieren, um die Teilmengen selbst anzuzeigen.
formatiert:
quelle
...x-1
=>..x-2
,.select{...}.count
=>.count{...}
,|(x,y)|
=>|x,y|
,x&~y==0||y&~x!=0
=>x&~y<1||y&~x>0
daa&~b
kann nicht negativ sein, wenn ich mich nicht irren=5
gerade hinzugefügte Gegenbeispiel an. Wenn ich mich nicht irre, würde Ihr Code dies akzeptieren.P
, die nicht anonym sein kann. Außerdem denke ich, dass es aufgrund des von mir geposteten Gegenbeispiels immer noch fehlschlägt.P=
) angeben müssen . Außerdem denke ich, dass Sie eine Nummer zurückgeben müssen, damit Sie sie möglicherweise.size
irgendwo einfügen müssen.