Sparse Winkelmesser

12

nEntwerfen Sie bei einer positiven Ganzzahl einen Winkelmesser mit der geringsten Anzahl von Markierungen, mit dem Sie alle Winkel messen können, die ein ganzzahliges Vielfaches von 2π/n(jeweils in einer Messung) sind.

Einzelheiten

Als Ausgabe können Sie eine Liste von Ganzzahlen im Bereich 0bis n-1(oder 1bis n) ausgeben , die die Position jeder Marke darstellen. Alternativ können Sie eine Zeichenfolge / Liste nmit einer Länge #an der Position jeder Marke und einem _(Unterstrich) ausgeben, wenn keine vorhanden ist. (Oder zwei verschiedene Zeichen , wenn bequemer.)
Beispiel: Für n = 5Sie müssen genau drei Marken der Lage sein , alle Winkel zu messen , 2π/5, 4π/5, 6π/5, 8π/5, 2πindem (zum Beispiel) eine Markierung an 0, eine Markierung an 2π/5und eine Markierung an 6π/5. Wir können dies als Liste [0,1,3]oder als Zeichenfolge codieren ##_#_.

Beispiele

Beachten Sie, dass die Ausgaben nicht unbedingt eindeutig sind.

n:  output:
 1  [0]
 2  [0,1]
 3  [0,1]
 4  [0,1,2]
 5  [0,1,2]
 6  [0,1,3]
 7  [0,1,3]
 8  [0,1,2,4]
 9  [0,1,3,4]
10  [0,1,3,6]
11  [0,1,3,8]
20  [0,1,2,3,6,10]

PS: Dies ähnelt dem Problem mit dem spärlichen Lineal , aber anstelle einer linearen Skala (mit zwei Enden) wird eine kreisförmige (eckige) Skala betrachtet.

PPS: Dieses Skript sollte jeweils ein Beispiel für eine Reihe von Markierungen berechnen n. Probieren Sie es online!

PPPS: Wie @ngn hervorhob, entspricht dieses Problem dem Auffinden einer minimalen Differenzbasis einer zyklischen Ordnungsgruppe n. Die Mindestbestellmengen sind unter http://oeis.org/A283297 aufgeführt, und einige theoretische Grenzen finden Sie unter https://arxiv.org/pdf/1702.02631.pdf

Fehler
quelle
2
Verbunden.
Martin Ender
Borderline-Dupe , mit exakter Überlappung, wenn es n = q^2 + q + 1um Primärenergie geht q.
Peter Taylor
@PeterTaylor Ich verstehe nicht, warum du denkst, dass es ein Betrug ist. Und können Sie erläutern, inwiefern es zu einer "Überlappung" kommt? Obwohl es Ähnlichkeiten gibt, sind dies zwei sehr unterschiedliche Probleme. Außerdem ist dies Codegolf und die Herausforderung, die Sie verknüpft haben, bezieht nicht einmal die Größe des Programms in die Wertung ein.
Fehler
Das sind keine zwei sehr unterschiedlichen Probleme. Lesen Sie den OEIS-Link in Ihrer PPPS: Die "Differenzmenge von Singer", auf die dort Bezug genommen wird, ist genau das Golomb-Lineal, das durch die in meiner Antwort implementierte projektive Feldmethode erzeugt wurde. Ich gehe davon aus, dass die Bewertungsmethode anders ist.
Peter Taylor

Antworten:

4

Gelee , 13 Bytes

ŒPðṗ2I%QLðÐṀḢ

Probieren Sie es online!

Wie es funktioniert

ŒPðṗ2I%QLðÐṀḢ  Main link. Argument: n (integer)

ŒP             Powerset; generate all subsequences of [1, ..., n].
  ð       ÐṀ   Begin a dyadic chain. Call it with all subsequences S as left
               argument and n as right one. Return the array of all sequences for
               which the chain returns the maximal result, i.e., [0, ..., n-1].
   ṗ2              Cartesian power 2; generate all pairs of elements of S.
     I             Increments; map each pair [x, y] to [y-x].
      %            Map each [y-x] to [(y-x)%n].
       Q           Unique; deduplicate the array of modular difference singletons.
        L          Take the length.
         ð     Begin a new, dyadic chain.
               Left argument: S' (filted subsequences). Right argument: n
            Ḣ  Take the first element of S'.
               Since S was sorted by length, so is S', so the first element of S'
               is the shortest subsequence that satisfies the condition.
Dennis
quelle
4

MATL , 20 Bytes

:qGZ^!"G:q@&-G\m?@u.

Dies führt zu einem Speichermangel bei TIO für darüber hinausgehende Eingaben 8.

Probieren Sie es online!

Wie es funktioniert

Dies erzeugt die kartesische Potenz von [0 1 ... n-1]mit Exponent nund verwendet eine Schleife, um jedes kartesische Tupel zu testen. Der Test besteht in der Berechnung alle paarweise Unterschiede des Elements , wenn das Tupel, und zu sehen , ob diese Unterschiede Modulo numfassen alle Zahlen 0, 1, ..., n-1.

Sobald ein kartesisches Tupel gefunden wird, das die Bedingung erfüllt, wird die Schleife verlassen und die eindeutigen Einträge in diesem Tupel werden als Lösung gedruckt.

Dies funktioniert , weil gegeben u > v , einen ausreichenden Satz von Tupeln mit u eindeutigen Einträgen sind garantiert wird getestet früher als jedes Tupel mit v eindeutigen Einträgen. Eine "ausreichende Menge" bedeutet, dass, wenn keines der Tupel in dieser Menge eine Lösung ist, kein anderes Tupel mit der gleichen Anzahl eindeutiger Einträge eine Lösung ist.

Für n = 3die kartesischen Tupel gilt beispielsweise Folgendes:

0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
 ···
2 2 1
2 2 2
  • Das erste Tupel 0 0 0ist das einzige relevante Tupel mit einem 1eindeutigen Wert. Auch wenn 1 1 1und 2 2 2wird viel später erscheinen, 0 0 0ist eine Lösung, wenn und nur wenn diese sind. Die vom Tupel gebildete Singletonmenge 0 0 0ist also eine ausreichende Menge für u = 1.
  • Das zweite und dritte Tupel, nämlich 0 0 1und 0 0 2, bilden eine ausreichende Menge für u = 2; Das heißt, sie decken alle Fälle mit 2eindeutigen Werten ab. Das vierte Tupel 0 1 0wird niemals als Lösung ausgewählt, da 0 0 1es zuerst getestet wurde. Ebenso wird das Tupel 0 2 0nie ausgewählt, da es später als angezeigt wird 0 0 2. Tupel wie 2 2 1werden niemals als Lösung ausgewählt, da sie 0 0 1äquivalent sind (Modulo nund bis zu duplizierten Werten) und zuerst erscheinen.
  • Etc.

Kommentierter Code:

:q         % Push [0 1 ... n-1], where n is the input (implicit)
GZ^        % Cartesian power with exponent n. Gives an (n^n) × n matrix
           % where each row is a Cartesian tuple
!          % Transpose. Now each Cartesian tuple is a column
!"         % For each column (that is, each Cartesian tuple)
  G:q      %   Push [0 1 ... n-1] (*)
  @        %   Push current column
  &-       %   Matrix of pairwise differences (**)
  G\       %   Modulo n, element-wise
  m        %   Ismember function: for each entry in (*), gives true iff
           %   it is present in (**)
  ?        %   If all entries are true
    @      %     Push current column
    u      %     Unique entries. This is the solution
    .      %     Break loop
           %   End (implicit)
           % End (implicit)
           % Display (implicit)
Luis Mendo
quelle
3

Stax , 26 21 Bytes

Åæ4&╕u◙╩►s∙Φ▬═(0~ d+Q

Online ausführen und debuggen!

Momentan schlägt die Online-Version für Eingaben fehl, 20aber dieser Fehler wurde behoben und muss noch für den Online-Interpreter Deployed bereitgestellt werden . Beachten Sie, dass das Ausführen des 20Falls einige Zeit dauert .

Erläuterung

Es stellt sich heraus, dass aufgrund der Art und Weise, wie die paarweise Differenz berechnet wird, ich mich nicht um die Äquivalenz von kund x-khier kümmern muss . 5 Bytes sparen.

Verwendet die entpackte Version, um zu erklären.

rS{%o~{;i@c:2{E-x%mu%x<wm
r                            [0..`x`], where `x` is input
 S                           Powerset
  {%o~                       Sort by length
      {;i@             w     For each element in the powerset
          c:2                All pairs
             {    m          Map each pair `[p,q] to
              E-                 `q-p`
                x%               `(q-p)%x`
                   u%        Count of unique modulo differences
                     x<      Loop until the count of unique modulo differences is larger than the input(`n`)
                             Now we have found a valid set in the powerset
                        m    Output the members of the set,one element per line.

Durch die Durchsetzung der Forderung , dass 0und 1beide Mitglieder der Antwort sein, können wir die Powerset mit erzeugen [2..x]statt [0..x]und fügen Sie dann das 0und 1manuell auf jedes Element in der Powerset. Es ist effizienter, muss aber 1speziell mit der Eingabe umgehen und kostet mehr Bytes.

Weijun Zhou
quelle
2

Gelee , 17 Bytes

_þ¹F%³³Ḷ¤ḟ
ŒPÇÐḟḢ

Probieren Sie es online!

-1 Byte danke an Herrn Xcoder

HyperNeutrino
quelle
Sie brauchen nicht die Führung R.
Mr. Xcoder
@ Mr.Xcoder oh richtig, danke!
HyperNeutrino
0

Python 2 , 148 Bytes

from itertools import*
def f(n):
 r=range(n)
 for i in r:
  for p in combinations(r,i+1):
   if all(any((y+x)%n in p for y in p)for x in r):return p

Probieren Sie es online!

TFeld
quelle