operaciones de acumulación independientes de orden?

Question

Este es un seguimiento de una respuesta que he publicado en stackoverflow sobre el cálculo de un total de operación.

Hay otros invertible operaciones sobre enteros además de adición (+), resta (-) y XOR, donde si se tienen N números enteros, se puede calcular una generalizada suma (suma real, en el caso de la suma) y el orden no importa?

Hay multiplicación y la división, sino la multiplicación no es invertible, y la división no produce resultados válidos para 0 operandos.

Answer 1

Sí, de hecho, una cantidad no numerable. Esto es porque si $a \oplus b$ es una operación de ese tipo y $f : \mathbb{Z} \to \mathbb{Z}$ es un bijection, a continuación, $f^{-1} (f(a) \oplus f(b))$ es también una operación de ese tipo, y hay una cantidad no numerable de permutaciones de $\mathbb{Z}$. (Edit: este argumento realmente necesita un poco más de trabajo, ya que no es obvio que $f^{-1}( f(a) \oplus f(b)) \neq a \oplus b$ bastante $f$. Pero el argumento de abajo es mejor).

Que fue un poco la lengua en la mejilla. Si entiendo tu pregunta correctamente, que son, básicamente, pidiendo ejemplos de contables abelian grupos. Los enteros $\mathbb{Z}$ bajo, además de formar un grupo, como lo hace la suma directa de countably muchas copias de la cíclico grupo $\mathbb{Z}/2\mathbb{Z}$ (este es el XOR ejemplo), pero, por ejemplo, los racionales $\mathbb{Q}$ bajo, además de que también forman un grupo, y hay más complicada ejemplos. Uno puede tomar la suma directa de cualquier contables colección de ejemplos y obtener otro ejemplo, que por cierto muestra que hay una cantidad no numerable de ejemplos, incluso hasta el isomorfismo.

Existe una clasificación de abelian grupos que son finitely generado, todos los cuales son finito o contable. El infinitamente generado caso fue discutido en matemáticas.SE pregunta.

---

En el caso de que era un poco demasiado abstracto, no es una generalización de XOR para cada entero positivo $b > 1$ define de la siguiente manera: escribe tu (no negativo) enteros en base $b$, y añadir sus dígitos sin llevar.

Answer 2

No muy seguro de lo que quieres decir por invertible, o por qué lo quieres, lo que no parece necesario para su acumulador de definición. Así que, ignorando que por ahora ....

Cómo acerca de min, max ? O contar ?

Si usted admite compuesto acumuladores adicionales con el estado, entonces usted puede tener un promedio (media), debido a que puede almacenar { count, media } y actualización:

count' = count + 1
mean'  = (count*mean + n) / count'

o tal vez tienda { count, sum, media } donde

count' = count + 1
sum'   = sum + n
mean'  = sum' / count'

Parece que quieres un monoid: asociativa operador binario con una identidad. El valor de identidad es el valor inicial de su acumulador. La propiedad asociativa es decir, el orden de aplicación es irrelevante. Para obtener más información, consulte Introducción a las Aves Meertens, el Formalismo, por Jeremy Gibbons.

En programación funcional, el problema es equivalente a encontrar la lista de homomorphisms, que son funciones de las listas (f) que puede ser expresado con un monoid (#) y la lista de operador de concatenación (++), tal que:

f (a ++ b) = (f a) # (f b)

es decir, la aplicación de una función a la lista completa se puede descomponer en la aplicación de la función a 2 sublistas y la combinación de los 2 resultados con un nuevo operador binario. El Tercer Homomorphism Teorema (ver otro trabajo de Gibbons) establece que si se pueden encontrar dos implementaciones para la función f, una acumulación de la izquierda (foldl) y una acumulación de la derecha (foldr), a continuación, usted puede encontrar el monoid operador y la función se puede calcular en cualquier orden, o en paralelo. Un excelente artículo sobre el tema es la Inversión Automática Genera Divide y Vencerás Programas Paralelos.

Mik