El fenómeno de Will Rogers

35

El llamado fenómeno de Will Rogers describe una forma de ajustar las estadísticas elevando el promedio en dos (múltiples) conjuntos cuando un elemento se mueve entre los dos conjuntos. Como un ejemplo simple, considere los dos conjuntos

A = {1, 2, 3}
B = {4, 5, 6}

Sus medios aritméticos son 2y 5, respectivamente. Si movemos el 4a A:

A = {1, 2, 3, 4}
B = {5, 6}

Ahora los promedios son 2.5y 5.5, respectivamente, por lo que ambos promedios se han elevado mediante una simple reagrupación.

Como otro ejemplo, considere

A = {3, 4, 5, 6} --> A = {3, 5, 6}
B = {2, 3, 4, 5} --> B = {2, 3, 4, 4, 5}

Por otro lado, no es posible aumentar ambos promedios para los conjuntos

A = {1, 5, 9}
B = {4, 5, 7, 8}

El reto

Dadas dos listas de enteros no negativos, determine si es posible aumentar ambos promedios moviendo un solo entero de una lista a la otra.

El promedio de una lista vacía no está definido, por lo que si una de las listas contiene solo un elemento, este elemento no se puede mover.

Puede escribir un programa o función, tomando entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), valor de retorno de función o parámetro de función (out).

La entrada puede tomarse en cualquier cadena conveniente o formato de lista.

No debe suponer que los elementos en cada lista son únicos, ni que están ordenados. Puede suponer que ambas listas contienen al menos un elemento.

El resultado debería ser verdadero si ambos promedios pueden elevarse moviendo un solo entero y falso de lo contrario.

Este es el código de golf, por lo que gana la respuesta más corta (en bytes).

Casos de prueba

Verdad:

[1], [2, 3]
[1, 2, 3], [4, 5, 6]
[3, 4, 5, 6], [2, 3, 4, 5]
[6, 5, 9, 5, 6, 0], [6, 2, 0, 9, 5, 2]
[0, 4], [9, 1, 0, 2, 8, 0, 5, 5, 4, 9]

Falsy

[1], [2]
[2, 4], [5]
[1, 5], [2, 3, 4, 5]
[2, 1, 2, 3, 1, 3], [5, 1, 6]
[4, 4, 5, 2, 4, 0], [9, 2, 10, 1, 9, 0]

Tablas de clasificación

Aquí hay un fragmento de pila para generar una tabla de clasificación regular y una descripción general de los ganadores por idioma.

Para asegurarse de que su respuesta se muestre, comience con un título, usando la siguiente plantilla de Markdown:

# Language Name, N bytes

¿Dónde Nestá el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:

# Ruby, <s>104</s> <s>101</s> 96 bytes

<script>site = 'meta.codegolf'; postID = 5314; isAnswer = true; QUESTION_ID = 53913</script><script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)</code></pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>

Martin Ender
fuente
Como matemático y no como programador, realmente no puedo abordar el desafío, pero me interesa la siguiente pregunta: si se pueden elevar ambos promedios al cambiar una colección finita de enteros (digamos cinco) de un conjunto al otro , ¿siempre se deduce que ambos promedios pueden aumentarse al cambiar un solo entero ? Mostrando así que el desafío realmente cubre todos los casos.
Trevor J Richards
3
@TrevorRichards Creo que el último caso falso de prueba cubre esto. Puede mover una 1y 9otra vez, lo que elevaría ambos promedios, pero no puede hacerlo moviendo uno solo.
Martin Ender
@TrevorRichards En general, si los conjuntos A y B tienen promedios a y b con a <b, ambos promedios pueden aumentarse si hay un subconjunto C de B que tiene un promedio c tal que a <c <b. Por otro lado, si requiere que todos los elementos movidos de B a A tengan valores <b, entonces su hipótesis sería verdadera.
Alchymist

Respuestas:

11

Pyth, 29 28 26 24 bytes

Gracias a @Jakube por guardarme 3 bytes con .py L.

Muy simple, comprueba si alguno de los elementos de la lista 2 es mayor que la media de la lista 1 y menor que la media de la lista 2, luego se repite con la lista 1 y la lista 2 conmutadas.

Lcsblbff&>YyhT<YyeTeT.pQ

Imprime una lista no vacía para la verdad y []para falsey.

L                    Define y(b). Pyth has no builtin for mean
 c                   Float div
  sb                 Sum of b
  lb                 Length of b
f        .pQ         Filter all permutations of input
 f     eT            Filter the last element of the filter var
  &                  Logical and
   >Y                Inner filter var greater than
    y                Call the mean function we defined earlier
     hT              First element of outer filter var
   <Y                Inner filter var less than
    y                Mean of
     eT              Last element of outer filternvar

Pruébelo en línea aquí .

Banco de pruebas.

Maltysen
fuente
7

Pitón 3, 74

lambda*L:any(sum(C)/len(C)>x>sum(D)/len(D)for(C,D)in[L,L[::-1]]for x in C)

Toma dos listas como entrada. Comprueba si la primera lista tiene un elemento que es más grande que el promedio pero más pequeño que el otro. Luego, hace lo mismo para las dos entradas intercambiadas. Tener una comprensión de lista de dos capas fue más corto que definir una función separada para probar las dos órdenes (82):

f=lambda A,B:any(sum(A)/len(A)>x>sum(B)/len(B)for x in A)
lambda A,B:f(A,B)|f(B,A)
xnor
fuente
7

Haskell, 58 57

x%y=any(\n->(\g->g x<0&&g y>0)$sum.map(n-))x
x?y=x%y||y%x

Podemos verificar si ampliamos o disminuimos el promedio verificando si el elemento a eliminar o incluir es mayor o menor que el promedio.

podemos verificar eso verificando si el promedio es más pequeño o más grande que un elemento eliminando ese elemento de la matriz y verificando si la media de la nueva matriz es negativa o positiva, lo que a su vez es igual a verificar si la suma es positiva o negativa .

la comprobación de que se pone muy simplemente como sum.map(-n+).

orgulloso Haskeller
fuente
6

Mathematica, 49 47 bytes

m=Mean;MemberQ[#2,x_/;m@#<x<m@#2]&@@#~SortBy~m&

Evalúa una función pura que espera entrada en el formulario {list1, list2}.

jcai
fuente
4

APL, 45 40 bytes

¡Guardado 5 bytes gracias a Moris Zucca!

{U←∊⍺⍵[⊃⍒M←(+/÷≢)¨⍺⍵]⋄1∊(U<⌈/M)∧(U>⌊/M)}

Esto crea una función diádica sin nombre que acepta matrices a la izquierda y a la derecha y devuelve 1 o 0.

{
  M←(+/÷≢)¨⍺⍵          ⍝ Compute the mean of each array
  U←∊⍺⍵[⊃⍒M]           ⍝ Get the array with the larger mean
  1∊(U<⌈/M)∧(U>⌊/M)    ⍝ Any smaller mean < U < larger mean
}

Puedes probarlo en línea .

Alex A.
fuente
1
puede escribir la media como: (+ / ÷ ≢)
Moris Zucca
@MorisZucca ¡Gracias! Editado para usar su sugerencia.
Alex A.
3

R, 66 52 bytes

Como una función sin nombre, que acepta 2 vectores. Se deshizo de algunas cosas espurias.

function(a,b)any(a<(m=mean)(a)&a>m(b),b<m(b)&b>m(a))

Pruebas

> f=
+ function(a,b)any(a<(m=mean)(a)&a>m(b),b<m(b)&b>m(a))
> f(c(1), c(2, 3))
[1] TRUE
> f(c(1, 2, 3), c(4, 5, 6))
[1] TRUE
> f(c(3, 4, 5, 6), c(2, 3, 4, 5))
[1] TRUE
> f(c(6, 5, 9, 5, 6, 0), c(6, 2, 0, 9, 5, 2))
[1] TRUE
> f(c(0, 4), c(9, 1, 0, 2, 8, 0, 5, 5, 4, 9))
[1] TRUE
> 
> f(c(1), c(2))
[1] FALSE
> f(c(2, 4), c(5))
[1] FALSE
> f(c(1, 5), c(2, 3, 4, 5))
[1] FALSE
> f(c(2, 1, 2, 3, 1, 3), c(5, 1, 6))
[1] FALSE
> f(c(4, 4, 5, 2, 4, 0), c(9, 2, 10, 1, 9, 0))
[1] FALSE
> 
MickyT
fuente
3

SAS / IML, 67

start m(a,b);return((a>b[:]&&a<a[:])||(b>a[:]&&b<b[:]))[<>];finish;

Utiliza operadores de reducción de subíndice para obtener la respuesta, devolviendo 0 si no se encuentra ningún elemento que coincida con los requisitos o 1 si se encuentra uno.

Sin golf, aquí devuelvo el valor real usando la multiplicación de matrices:

proc iml;
  b={1 2 3 4 5 6 7 8 9 };
  a={2 3 4 5 6};
  start m(a,b);
  return (a#(a>b[:] && a < a[:]) || b#(b>a[:] && b < b[:]))[<>];
  finish;

  z= m(a,b);
  print z;
quit;

Pruebas:

%macro test(a,b,n);
  z&n=m({&a},{&b});
  print z&n;
%mend test;

proc iml;
  b={1 2 3 4 5 };
  a={2 3 4 5 6 7};
start m(a,b);return((a>b[:]&&a<a[:])||(b>a[:]&&b<b[:]))[<>];finish;

* True;
 %test(1,2 3,1);
 %test(1 2 3,4 5 6,2);
 %test(3 4 5 6, 2 3 4 5,3);
 %test(6 5 9 5 6 0,6 2 0 9 5 2,4);
 %test(0 4, 9 1 0 2 8 0 5 5 4 9,5);
* False;
 %test(1,2,6);
 %test(2 4, 5,7);
 %test(1 5, 2 3 4 5,8);
 %test(2 1 2 3 1 3, 5 1 6,9);
 %test(4 4 5 2 4 0, 9 2 10 1 9 0,10);

quit;

(Condensado para facilitar la lectura)

z1 1

z2 1

z3 1

z4 1

z5 1

z6 0

z7 0

z8 0

z9 0

z10 0

Joe
fuente
2

Python 2.7, 102 98 96

lambda p:any([1for i in 0,1for e in p[i]if g[i^1]<e<g[i]]for g in[[sum(l)*1./len(l)for l in p]])

Toma la entrada como una matriz de las 2 entradas y devuelve boolean.
La lógica es -encontrar el promedio de las 2 listas, luego encontrar un elemento tal que sea menor que el promedio de su propia lista y mayor que el promedio de la otra lista.

Probarlo para las entradas dadas se muestra aquí

Kamehameha
fuente
2
Puede hacerlo en *1.lugar de *1.0guardar un byte. Alternativamente, si hace esto en Python 3, la división devolverá un flotante por defecto, por lo que no necesitaría esa multiplicación en absoluto. (No creo que tenga que cambiar su código para usar Python 3.)
Mathmandan
@mathmandan Me salvó un byte. Gracias :)
Kamehameha
Puede convertirlo en una función anónima eliminando f=y cambiando in[0,1]fora in 0,1for. Como en realidad tienes 101 bytes, esto te lleva a 98.
Kade
@ Vioz- Gracias, no sabía que podía hacer eso :)
Kamehameha
2

CJam, 28 bytes

{{_:+1$,d/\+}%$~(m],@0=i)>&}

Esta es una función anónima que saca una matriz bidimensional de la pila y deja una matriz de elementos móviles a cambio.

En los navegadores compatibles, puede verificar todos los casos de prueba a la vez en el intérprete de CJam .

Casos de prueba

Código

q~]{{_:+1$,d/\+}%$~(m],@0=i)>&}%:p

Entrada

[[1] [2 3]]
[[1 2 3] [4 5 6]]
[[3 4 5 6] [2 3 4 5]]
[[6 5 9 5 6 0] [6 2 0 9 5 2]]
[[0 4] [9 1 0 2 8 0 5 5 4 9]]
[[1] [2]]
[[2 4] [5]]
[[1 5] [2 3 4 5]]
[[2 1 2 3 1 3] [5 1 6]]
[[4 4 5 2 4 0] [9 2 10 1 9 0]]

Salida

[2]
[4]
[4]
[5]
[4]
""
""
""
""
""

Cómo funciona

Si A y B son las matrices y avg (A) ≤ avg (B) simplemente verificamos si B ∩ {⌊avg (A) ⌋ + 1, ..., ⌈avg (B) ⌉-1} no está vacío. Cualquier elemento en esta intersección podría moverse de B a A para aumentar ambos promedios.

{          }%              e# For each of the arrays:
 _:+                       e#   Compute the sum of its elements.
    1$,                    e#   Compute its length.
       d/                  e#   Cast to Double and perform division.
         \+                e#   Prepend the computed average to the array.
             $             e# Sort the arrays (by the averages).
              ~            e# Dump both arrays on the stack.
               (           e# Shift out the higher average.
                m]         e# Round up to the nearest integer b.
                  ,        e# Push [0 ... b-1].
                   @0=     e# Replace the array with lower average by its average.
                      i)   e# Round down to the nearest integer a and add 1.
                        >  e# Skip the first a integer of the range.
                           e# This pushes [a+1 ... b-1].
                         & e# Intersect the result with the remaining array.

Esto empuja la matriz de todos los elementos de la matriz con un promedio más alto que se puede mover para aumentar ambos promedios. Esta matriz está vacía / falsa si y solo si no se pueden mover elementos para lograr este resultado.

Dennis
fuente
1

Ruby, 86

A=->x{x.reduce(0.0,:+)/x.size}
F=->q{b,a=q.sort_by{|x|A[x]};a.any?{|x|x<A[a]&&x>A[b]}}

Toma como entrada una matriz que contiene las dos matrices.

Trata de encontrar un elemento por debajo del promedio del grupo con el promedio más alto que sea mayor que el promedio del otro grupo.

Prueba: http://ideone.com/444W4U

Cristian Lupascu
fuente
Comenzó a trabajar en esto sin darse cuenta de que ya había una solución Ruby, terminó con algo muy similar, pero tiene dos caracteres menos al hacer que la función asuma que la primera lista es 'mejor', luego se llama al revés. f=->a,s=1{i,j=a.map{|x|x.inject(0.0,:+)/x.size};a[0].any?{|y|i>y&&j<y}||s&&f[b,a,p]}
histocrat
@histocrat ¡Buen enfoque! Sin bembargo, obtengo un NameError con respecto a la variable . Creo que la llamada recursiva debería ser algo así f[a.rotate,p].
Cristian Lupascu
1
Oops, así es como obtuve una mejor puntuación, haciendo trampa.
histocrat
1

Matlab, 54

Usando una función anónima:

f=@(A,B)any([B>mean(A)&B<mean(B) A>mean(B)&A<mean(A)])

Ejemplos:

>> f=@(A,B)any([B>mean(A)&B<mean(B) A>mean(B)&A<mean(A)])
f = 
    @(A,B)any([B>mean(A)&B<mean(B),A>mean(B)&A<mean(A)])

>> f([1 2 3],[4 5 6])
ans =
     1

>> f([3 4 5 6],[2 3 4 5])
ans =
     1

>> f([1 5 9],[4 5 7 8])
ans =
     0
Luis Mendo
fuente
1

C #, 104

bool f(int[]a,int[]b){double i=a.Average(),j=b.Average();return a.Any(x=>x<i&&x>j)||b.Any(x=>x<j&&x>i);}

Llamadas de ejemplo:

f(new []{1,2,3}, new []{4,5,6})
f(new []{1}, new []{2, 3})
f(new []{1, 2, 3}, new []{4, 5, 6})
f(new []{3, 4, 5, 6}, new []{2, 3, 4, 5})
f(new []{6, 5, 9, 5, 6, 0}, new []{6, 2, 0, 9, 5, 2})
f(new []{0, 4}, new []{9, 1, 0, 2, 8, 0, 5, 5, 4, 9})

f(new []{1}, new []{2})
f(new []{2, 4}, new []{5})
f(new []{1, 5}, new []{2, 3, 4, 5})
f(new []{2, 1, 2, 3, 1, 3}, new []{5, 1, 6})
f(new []{4, 4, 5, 2, 4, 0}, new []{9, 2, 10, 1, 9, 0})
Stephan Schinkel
fuente
0

C ++ 14, 157 bytes

Como lambda sin nombre, regresa por el último parámetro r. Asume A, Bser contenedores como vector<int>o array<int,>.

[](auto A,auto B,int&r){auto m=[](auto C){auto s=0.;for(auto x:C)s+=x;return s/C.size();};r=0;for(auto x:A)r+=x<m(A)&&x>m(B);for(auto x:B)r+=x<m(B)&&x>m(A);}

Sin golf:

auto f=
[](auto A,auto B,int&r){
  auto m=[](auto C){
   auto s=0.;
   for(auto x:C) s+=x;
   return s/C.size();
  };
  r=0;
  for (auto x:A) r+=x<m(A)&&x>m(B);
  for (auto x:B) r+=x<m(B)&&x>m(A);
}
;

Uso:

int main() {
  std::vector<int>
    a={1,2,3}, b={4,5,6};
  //  a={1,5,9}, b={4,5,7,8};
  int r;
  f(a,b,r);
  std::cout << r << std::endl;
}
Karl Napf
fuente