Dado un número entero positivo n, diseñe un transportador con el menor número de marcas que le permita medir todos los ángulos que sean un múltiplo integral de 2π/n(cada uno en una sola medición).

Detalles

Como salida, puede generar una lista de enteros en el rango 0de n-1(o 1a n) que representan la posición de cada marca. Alternativamente, puede generar una cadena / lista de longitud ncon un #en la posición de cada marca y un _(guión bajo) donde no hay ninguno. (O dos caracteres diferentes si es más conveniente).
Ejemplo: para n = 5que necesite exactamente 3 marcas para poder medir todos los ángulos 2π/5, 4π/5, 6π/5, 8π/5, 2πconfigurando (por ejemplo) una marca en 0, una marca en 2π/5y una marca en 6π/5. Podemos codificar esto como una lista [0,1,3]o como una cadena ##_#_.

Ejemplos

Tenga en cuenta que las salidas no son necesariamente únicas.

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]

PD: Esto es similar al problema de la regla dispersa , pero en lugar de una escala lineal (con dos extremos) consideramos una escala circular (angular).

PPS: este script debe calcular un ejemplo de un conjunto de marcas para cada uno n. Pruébalo en línea!

PPPS: como señaló @ngn, este problema es equivalente a encontrar una base de diferencia mínima de un grupo cíclico de orden n. Los pedidos mínimos se enumeran en http://oeis.org/A283297 y algunos límites teóricos se encuentran en https://arxiv.org/pdf/1702.02631.pdf

Jalea , 13 bytes

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

Pruébalo en línea!

Cómo funciona

Œ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.

MATL , 20 bytes

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

Esto se queda sin memoria en TIO para entradas más allá 8.

Pruébalo en línea!

Cómo funciona

Esto genera el poder cartesiano de [0 1 ... n-1]con exponente n, y utiliza un bucle para probar cada tupla cartesiana. La prueba consiste en calcular todas las diferencias por pares de elemento si la tupla, y ver si esas diferencias módulo nincluyen todos los números 0, 1, ..., n-1.

Tan pronto como se encuentra una tupla cartesiana que cumple la condición, se cierra el bucle y las entradas únicas en esa tupla se imprimen como la solución.

Esto funciona porque dado u > v , se garantiza que un conjunto suficiente de tuplas con entradas únicas u se probará antes que cualquier tupla con entradas únicas v . Un "conjunto suficiente" significa que si ninguna de las tuplas en ese conjunto es una solución, entonces ninguna otra tupla con el mismo número de entradas únicas es una solución.

Por ejemplo, para n = 3las tuplas cartesianas se muestran a continuación, donde cada fila es una tupla:

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

• La primera tupla, 0 0 0es la única tupla relevante con 1un valor único. Incluso si 1 1 1y 2 2 2aparecerá mucho más tarde, 0 0 0es una solución si y solo si esos son. Entonces, el conjunto singleton formado por la tupla 0 0 0es un conjunto suficiente para u = 1.
• La segunda y tercera tuplas, a saber, 0 0 1y 0 0 2, forman un conjunto suficiente para u = 2; es decir, cubren todos los casos con 2valores únicos. La cuarta tupla, 0 1 0nunca se seleccionará como solución, porque 0 0 1se habrá probado primero. Del mismo modo, la tupla 0 2 0nunca se seleccionará porque aparece más tarde que 0 0 2. Tuplas como 2 2 1nunca se seleccionarán como solución porque 0 0 1es equivalente (módulo ny hasta valores duplicados) y aparece primero.
• Etc.

Código comentado:

: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)

Stax , 26 21 bytes

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

¡Ejecute y depure en línea!

En este momento, la versión en línea falla para la entrada, 20pero este error se ha solucionado y aún no se ha implementado en el intérprete en línea Implementado. Tenga en cuenta que lleva un tiempo ejecutar el 20caso.

Explicación

Resulta que debido a la forma en pairwise diferencia se calcula, no tiene que preocuparse acerca de la equivalencia de las ky x-kaquí. Ahorro de 5 bytes.

Utiliza la versión desempaquetada para explicar.

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.

Al hacer cumplir el requisito de que 0y 1ser ambos miembros de la respuesta, podemos generar el powerset con [2..x]en lugar de [0..x]a continuación, añadir el 0y 1manualmente para cada elemento en el powerset. Es más eficiente pero necesita manejar la entrada 1especialmente y cuesta más bytes.

Jalea , 17 bytes

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

Pruébalo en línea!

-1 byte gracias al Sr. Xcoder

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

Pruébalo en línea!