Stellen wir uns vor, wir haben eine endliche Menge positiver Ganzzahlen. Dieser Satz kann als eine Reihe von Punkten dargestellt werden, wobei jede in dem Satz vorhandene Ganzzahl wie eine Scantron- oder Lochkarte ausgefüllt wird . Zum Beispiel könnte die Menge {1,3,4,6}dargestellt werden als:
*.**.*
*repräsentiert ein Mitglied unserer Menge und .repräsentiert eine ganze Zahl, die kein Mitglied der Menge ist.
Diese Sätze haben "Faktoren". Lose x ist ein Faktor von y, wenn y aus Kopien von x aufgebaut werden kann. Strenger definieren wir Faktor wie folgt:
- x ist genau dann ein Faktor von y, wenn y die Vereinigung mehrerer disjunkter Mengen ist, die alle x mit einem Versatz sind.
Wir würden *.*einen Faktor von nennen, *.**.*weil er ganz klar aus zwei Kopien von *.*Ende zu Ende besteht.
*.**.*
------
*.*...
...*.*
Faktoren müssen nicht Ende zu Ende sein, wir würden auch sagen, das *.*ist ein Faktor von*.*.*.*
*.*.*.*
-------
*.*....
....*.*
Faktoren können sich auch überschneiden. Dies bedeutet *.*auch einen Faktor von****
****
----
*.*.
.*.*
Eine Zahl kann jedoch nicht mehrmals durch einen Faktor abgedeckt werden. Zum Beispiel *.*ist kein Faktor von *.*.*.
Hier ist ein komplizierteres Beispiel:
*..*.**..***.*.*
Dies ist *..*.*ein Faktor. Sie können das unten sehen, wo ich die drei Fälle von aufgereiht habe *..*.*.
*..*.**..***.*.*
----------------
*..*.*..........
......*..*.*....
..........*..*.*
Aufgabe
Bei einer Menge durch eine sinnvolle Darstellung werden alle Mengen ausgegeben, die Faktoren der Eingabe sind.
Sie können nach jedem Wert indizieren (dh Sie können eine kleinste Zahl auswählen, die in der Eingabe vorhanden sein kann). Sie können auch davon ausgehen, dass die Eingabemenge immer den kleinsten Wert enthält.
Dies ist eine Code-Golf- Frage, daher sollten Sie versuchen, dies in so wenigen Bytes wie möglich zu tun.
Testfälle
Diese Testfälle wurden von Hand durchgeführt. Bei den größeren Fällen kann es zu ein oder zwei Fehlern kommen
* -> *
*.*.* -> *, *.*.*
*.*.*.* -> *, *.*, *...*, *.*.*.*
****** -> *, **, *..*, ***, *.*.*, ******
*..*.**..***.*.* -> *, *..*.*, *.....*...*, *..*.**..***.*.*
*...*****.**.** -> *, *...**.**, *.....*, *...*****.**.**
quelle
[1,3,5,7]für*.*.*.*) nehmen, können wir annehmen, dass es sortiert ist?*.*.*=x+x^2+x^4, dann wäre1+x+x^2=***ein Teiler, richtig?x+x^2+x^4 = (1-x+x^2)(1+x+x^2)*als Faktor aufgeführt, der dieselbe Teilmenge wie*.oder darstellt*...Antworten:
Mathematica,
71-68BytesEingabe als
{1,3,5,7}(sortiert) und Ausgabe als{{1, 3, 5, 7}, {1, 3}, {1, 5}, {1}}. Die Funktion wirft eine Reihe von Nachrichten.Dies ist O (2 2 Nope ) (wobei N die Länge der Eingabe ist und o = p = e = 1 ...). Es generiert alle Teilmengen von Teilmengen und wählt dann diejenigen aus, die beim Zusammenfügen zum Senden der Eingabe führen (wobei sichergestellt ist, dass nur Partitionen berücksichtigt werden) und bei denen alle Elemente gleich sind, wenn der kleinste Wert jeder Teilmenge subtrahiert wird.
quelle
Gelee , 12 Bytes
Eingabe und Ausgabe verwenden
1und0anstelle von*und..Probieren Sie es online!
Wie es funktioniert
quelle