Listas mod-balanceadas

14

Introducción

Supongamos que tengo una lista de enteros, digamos L = [-1,2,2,1,2,7,1,4] . Me gusta tener equilibrio en mi vida, así que estoy feliz de ver que tiene tantos elementos extraños como elementos pares. Además, también tiene el mismo número de elementos en todas las clases de módulo de 3 que tiene elementos en:

         [-1,2,2,1,2,7,1,4]
0 mod 3:
1 mod 3:         1   7 1 4
2 mod 3:  -1 2 2   2

Lamentablemente, para las clases de módulo de 4 esto ya no es válido. En general, decimos que una lista no vacía es un módulo equilibrado N si tiene el mismo número de elementos en todas las clases de módulos de N para las cuales este número no es 0. La lista anterior L es un módulo equilibrado 2 y 3, pero un módulo no equilibrado 4)

La tarea

Su entrada es una lista no vacía L de enteros tomados en cualquier formato razonable. Su salida es la lista de esos enteros N ≥ 2, de modo que L está equilibrado módulo N , nuevamente en cualquier formato razonable. El orden de la salida no importa, pero no debe contener duplicados.

Se garantiza que solo hay un número finito de números en la salida, lo que significa precisamente que no todos los elementos de L aparecen en la misma cantidad de veces. Ejemplos de entradas inválidas son [3] , [1,2] y [0,4,4,0,3,3] . Observe que el número más grande en la salida es como máximo max (L) - min (L) .

El conteo de bytes más bajo en cada idioma gana, y se aplican las reglas estándar de .

Casos de prueba

[1,1,2] -> []
[1,1,5] -> [2,4]
[1,1,24] -> [23]
[1,2,3,2] -> [2]
[12,12,-4,20] -> [2,3,4,6,8,12,24]
[1,1,12,12,-3,7] -> [3,10]
[-1,2,2,1,2,7,1,4] -> [2,3]
[4,-17,-14,-18,-18,3,5,8] -> []
[-18,0,-6,20,-13,-13,-19,13] -> [2,4,19]
[-11,-19,-19,3,10,-17,13,7,-5,16,-20,20] -> []
[3,0,1,5,3,-6,-16,-20,10,-6,-11,11] -> [2,4]
[-18,-20,14,13,12,-3,14,6,7,-19,17,19] -> [2,3]
[-16,-9,6,13,0,-17,-5,1,-12,-4,-16,-4] -> [3,9]
[-97,-144,3,53,73,23,37,81,-104,41,-125,70,0,111,-88,-2,25,-112,54,-76,136,-39,-138,22,56,-137,-40,41,-141,-126] -> [2,3,6]
Zgarb
fuente
(?) Brachylog quizá algunos idiomas que calculan automáticamente el límite superior tendrán una ventaja ...
user202729

Respuestas:

4

05AB1E , 11 bytes

ÄOL¦ʒ%{γ€gË

Pruébalo en línea!

ÄOL¦ʒ%{γ€gË  | Full program.

Ä            | Absolute value (element-wise).
 O           | Sum.
  L          | 1-based inclusive range.
   ¦         | Remove the first element (generates the range [2 ... ^^]).
    ʒ        | Filter / Select.
     %       | Modulo of the input with the current integer (element-wise).
      {      | Sort.
       γ     | Group into runs of adjacent elements.
        €g   | Get the length of each.
          Ë  | Are all equal?
Sr. Xcoder
fuente
4

Wolfram Language (Mathematica) , 56 52 bytes

Gracias a Not a tree por guardar 4 bytes.

Cases[Range[2,#.#],n_/;Equal@@Last/@Tally[#~Mod~n]]&

Pruébalo en línea!

El principal truco de golf es usar la suma de valores absolutos (o la suma de 1 norma) de valores al cuadrado, calculados como un producto puntual consigo mismo, como el límite superior en lugar de Max@#-Min@#. De lo contrario, solo implementa la especificación muy literalmente.

Martin Ender
fuente
3

Perl 6 ,  52  48 bytes

{grep {[==] .classify(*X%$^a).values},2.. .max-.min}

Pruébalo

{grep {[==] bag($_ X%$^a).values},2.. .max-.min}

Pruébalo

Expandido:

{  # bare block lambda with implicit parameter 「$_」

  grep

    {  # bare block lambda with placeholder parameter 「$a」

      [==]           # reduce with &infix:«==» (are the counts equal to each other)

        bag(         # group moduluses together

          $_ X% $^a  # find all the moduluses using the current divisor 「$a」

        ).values     # the count of each of the moduluses
    },

    2 .. .max - .min # all possible divisors
}
Brad Gilbert b2gills
fuente
3

Haskell , 85 84 bytes

f l=[n|n<-[2..sum$abs<$>l],all.(==)=<<head$[r|m<-[0..n],_:r<-[[0|x<-l,mod x n==m]]]]

Pruébalo en línea! Utiliza la suma de valores absolutos como máximo de la respuesta de Martin Ender .

Editar: -1 byte gracias a Ørjan Johansen.

Explicación:

f l=                             -- Given a list of numbers l,
  [n|n<-                       ] -- return a list of all numbers n of the range
    [2..sum$abs<$>l],            -- from 2 to the sum of the absolute values of l
      all.(==)=<<head$           -- for which all elements of the following list are equal:
        [r|m<-[0..n],         ]  -- A list r for each number m from 0 to n, where
          _:r<-[             ]   -- r is the tail of a list (to filter out empty lists)
          [0|x<-l,mod x n==m]    -- of as many zeros as elements of l mod n equal m.
Laikoni
fuente
2

R , 75 72 bytes

function(L){for(x in 2:(max(L)-min(L)))F=c(F,!sd(table(L%%x)))
which(F)}

Pruébalo en línea!

Se utiliza tablepara calcular los recuentos de cada módulo entero x. La desviación estándar sdde un conjunto de números es cero si todos son iguales, y positiva de lo contrario. Por !sd(table(L%%x))lo tanto, es TRUEdonde Lsea ​​mod mod equilibrado xy falso de lo contrario. Estos valores se concatenan en F.

whichluego devuelve los índices de valores verdaderos de la función. Dado que R usa indexación basada en 1 e Finicialmente es un vector de longitud uno con valor FALSE, esto devolverá correctamente los valores que comienzan con2 .

Uno podría esperar que la función incorporada rangecalcule el rango de un conjunto de datos , es decir max(D)-min(D), pero lamentablemente calcula y devuelve el vector c(min(D), max(D)).

Giuseppe
fuente
2

Limpiar , 121 bytes

Utiliza el truco de la suma de los absolutos de la respuesta de Martin Ender.

Golfizado:

import StdEnv   
f l=[n\\n<-[2..sum(map abs l)]|length(removeDup[length[m\\m<-[(e rem n+n)rem n\\e<-l]|m==c]\\c<-[0..n]])<3]

Legible:

import StdEnv
maximum_modulus l = sum (map abs l)
// mod, then add the base, then mod again (to fix issues with negative numbers)
list_modulus l n = [((el rem n) + n) rem n \\ el <- l]
// count the number of elements with each mod equivalency
equiv_class_count l n = [length [m \\ m <- list_modulus l n | m == c] \\ c <- [0..n]]
// for every modulus, take where there are only two quantities of mod class members
f l=[n \\ n <- [2..maximum_modulus l] | length (removeDup (equiv_class_count l n)) < 3]

Pruébalo en línea!

Οurous
fuente
1

Jalea , 12 bytes

⁹%LƙE
ASḊçÐf

Pruébalo en línea!

Gracias a user202729 por guardar un byte y Martin Ender (indirectamente) por guardar un byte.

Cómo funciona

⁹%LƙE ~ Helper link. Let's call the argument N.

⁹%    ~ Modulo the input by N (element-wise).
  Lƙ  ~ Map with length over groups formed by consecutive elements.
    E ~ All equal?

ASḊçÐf ~ Main link.

AS     ~ Absolute value of each, sum.
  Ḋ    ~ Dequeue (create the range [2 ... ^]).
   çÐf ~ Filter by the last link called dyadically.

¡Se puede probar en línea una alternativa de una línea de 12 bytes !

Sr. Xcoder
fuente
Borro mi respuesta porque ahora es redundante. Gracias Martin por AS( Sum de Absolutes) también.
user202729
1
Como referencia para futuros lectores, aclaré por qué ḟ0no es necesario en el chat .
Sr. Xcoder
1

Python 3, 120 102 bytes

No es muy golfoso.

-18 bytes gracias al Sr. Xcoder .

f=lambda a,i=2:[]if i>max(a)-min(a)else(len({*map([k%i for k in a].count,range(i)),0})<3)*[i]+f(a,i+1)

Pruébalo en línea!

Colera Su
fuente
1

MATL , 19 bytes

-4 bytes gracias a Luis Mendo!

S5L)d:Q"G@\8#uZs~?@

Pruébalo en línea!

Puerto de mi respuesta en R .

Suppose we have input [12,12,-4,20]
         # (implicit input), stack: [12,12,-4,20]
S        # sort the list, stack: [-4, 12, 12, 20]
5L       # push [1 0], stack: [[-4, 12, 12, 20]; [1 0]]
)        # 1-based modular index, stack: [-4, 20]
d        # successive differences, stack: [24]
:        # generate 1:(max(data)-min(data)), stack: [[1...24]]
Q        # increment to start at 2, stack: [[2...25]]
"        # for each element in [2...25]
 G       # push input, stack: [[12,12,-4,20]]
 @       # push loop index, stack: [[12,12,-4,20], 2]
 \       # compute modulo, stack: [[0,0,0,0]]
 8#      # use alternate output spec, unique has 4 outputs, so 8 keeps only the 4th
 u       # unique. 4th output is the counts of each unique value, stack: [4]
 Zs      # compute standard deviation, stack: [0]
 ~       # logical negate, stack: [T]
 ?       # if true,
  @      # push loop index
         # (implicit end of if)
         # (implicit end of for loop)
         # (implicit output of stack as column vector

Giuseppe
fuente
Puede acortar un poco usando en S5L)dlugar de X>GX<-y en 8#ulugar deFFFT#u
Luis Mendo
@LuisMendo No pude encontrar la manera de empujar [1 0](pero sabía que era posible) así que 5Les útil, y yo *still* really need to go and properly read the docs for # `:( ¡pero gracias!
Giuseppe
Para #, especificar un número mayor que el número máximo de salidas solo selecciona salidas individuales. Con función, uel máximo es 4, así 5#ues T#u, 6#ues FT#uetc.
Luis Mendo
0

JavaScript (ES6), 117 bytes

Emite una lista de valores separados por espacios.

a=>(g=m=>a.map(n=>x[k=(z|=m/2<n|m/2<-n,n%m+m)%m]=-~x[k],y=z=0,x=[])|z?(x.some(x=>x-(y?y:y=x))?'':m+' ')+g(m+1):'')(2)

Casos de prueba

Arnauld
fuente
0

Clojure, 91 bytes

#(for[i(range 2(apply +(map * % %))):when(apply =(vals(frequencies(for[j %](mod j i)))))]i)

Usar frequenciesno es ideal en el código de golf.

NikoNyrh
fuente
0

J, 38 bytes

[:}.@I.([:i.1#.|)(1=1#.[:~:|#/.])"0 1]

El crédito va al Sr. Xcoder por el truco de la suma de valores absolutos.

Edite en un enlace TIO si lo desea: he jugado golf con un poco de prisa.

Explicación y enlace TIO próximamente (ish).

col
fuente
0

APL (Dyalog) , 43 41 38 30 bytes

La ⍨s en el código cuenta toda la historia.

8 bytes guardados gracias a @ Adám

x⊆⍨1=⊂(≢∘∪1⊥|∘.=|)¨⍨x1+∘⍳1⊥|

Pruébalo en línea!

Uriel
fuente
Tren + Profundidad → Rango, 30 bytes:∊x⊆⍨1=⊂(≢∘∪1⊥|∘.=|)¨⍨x←1+∘⍳1⊥|
Adám