orderinvariant

Orderinvariant, sometimes written order-invariant or permutation-invariant, is a property of a function or computation that remains unchanged when the order of its inputs is permuted. In mathematics and computer science, this idea captures the notion that the result depends only on the multiset of input values, not on their arrangement.

Formally, a function f: X^n -> Y is order-invariant if for every permutation pi of {1,...,n} and every input (x1,...,xn) in X^n, f(x1,...,xn) = f(x_{pi(1)},..., x_{pi(n)}). Functions with this property are sometimes called permutation-invariant. Common examples include sum, product, min, max, and logical OR over a finite collection; these operations yield the same result regardless of input order.

In some contexts, order-invariance is a property of statistics or databases. A statistic is order-invariant if permuting the sample leaves its value unchanged; a query operator is order-invariant if its output sequence does not depend on input order.

In machine learning, permutation-invariant models exist for learning from sets. The Deep Sets framework and related pooling schemes ensure that the model's output is invariant to input ordering, which is essential when data are unordered yet the set of elements matters.

See also: permutation invariance, symmetry, aggregation function, commutativity, multiset.