Is there a way to constrain a sum of Integers in a set to (0,1) without finding the maximum integer in the set?

I have a set of n, numbers {N_1, N_2.....N_n}

Basically I want to do something to the sum of all N_k that keeps the result of the sum normalized/bounded between (0,1) 开发者_如何学运维( (like divide by some f(N_1,N_2..N_n)) but I don't want to compare all integers in the set to find the maximum and I want to keep the answer "dimensionless" so f cannot be the sum of (N_k)^2 for example.

Is there a simple function f or another way to ensure this?

EDIT I want a mapping of all possible sums from (0,infinity) to (0,1)

f = sum will not work because it will always give a result of 1 and so is not proportional to the sum.

Assuming each term were a length in meters...dimensionless means that the end result of the operation should not have any units..e.g 2m + 3m/ (2m + 1m) =5/3 with no units.

However...there fairly obvious answers that may work e.g. f = sum +1 or f= sum +2 etc. These will grow with the sum and tend to 1 for large values of the sum the question is then perhaps more subjective and becomes which other kind of f can be used and which will give the "most linear" type of mapping for large values?

atan(x/k)/(pi/2) maps all [0..infinity] to the range 0..1: fooplot

Pick a number k at least half as large as the largest number you expect to see. input k is mapped to 0.5. Too large of inputs will be so close to each other and 1 as to be lost in the roundoff.

but I want a map that is as linear as one can get...preferably something more linear than the inverse tangent?

I'm not a mathematician, but my intuition is that the only way that you map from (0, infinity) to (0, 1) is with a function f that that has the property that f(x) is asymptotic to 1 as x tends to infinity. It cannot be linear.

Per @Alexandre's comment, a revised statement should be:

• a function f that that has the property that f(x) is either constant or asymptotic to a constant as x tends to infinity.

• this means that it cannot be linear across the entire range ... except for the case of f(x) = C.

But like I said ... I'm not a mathematician ... and he apparently is.

If you want something dimensionless you must take f positive homogeneous (by definition of dimensionless). This means that for each a > 0,

f(a * x_1, ..., a * x_n) = a * f(x_1, ..., x_n).

This ensures that

sum(a * x_1, ... a * x_n) / f(a * x_1, ..., a * x_n)

does not depend on a (see the multiplication by a as a "change of units"). Put another way, the function f must grow linearly when you scale evenly its arguments.

Basic examples of homogeneous functions are the ones you mentioned:

f(x_1, ..., x_n) = n * max(x_1, ..., x_n)                                     (1)
f(x_1, ..., x_n) = sum(x_1, ..., x_n)                                         (2)

but also the Euclidean norm:

f(x_1, ..., x_n) = sqrt(n) * sqrt(sum(x_1^2, ..., x_n^2))                     (3)

and the p-norms, for p > 1:

f(x_1, ..., x_n) = n^(p/(p-1)) * sum(x_1^p, ..., x_n^p) ^ (1/p)               (4)

As a bonus, they are symmetric, which may also be one of your requirements. Pick whichever you want. There are others, but are more complicated.

By Hölder's inequality the ratio sum / f is always between zero and one for those four functions (this is why I chose the funny normalizing constants). Note that chosing (2) is a trivial choice: the result is always 1.

Why not just use a plain hyperbolic curve? The function y=n/(x+n) maps any positive number to the range [1,0]. The higher you choose n the flatter your curve becomes. If you take y=1-n/(x+n), it will be in the range [0,1]. So the choice of n will indicate how fast your curve will near its assymptote.

Try here: http://graph-plotter.cours-de-math.eu/

I'm not sure if I can understand the question right. If you try to find a mapping that maps every individual element N₁...N_n to (0,1) you could certainly use (as you propose)

f(x) = x / max { N₁, ..., N_n }

but for some reason you don't want to take the maximum of all the elements. You can use

f(x) = x / ∑_i N_i

but this doesn't necessarily map any of the elements even near to 1. Another alternative is to use the "soft max" function, i.e.

f(x) = e^x / [e^N₁ + ... + e^N_n]

If the value of x is not necessarily any individual element of the set but a subset sum, then obviously

f(x) = x / ∑_i N_i

works very well, us now when x is the sum of all the elements you get to 1.

But then you say that x can tend to infinity. Can that really happen if the set { N_i } is finite and remains constant?

In general if you want to compress from (0,∞) to (0,1) you can't do that with a linear function for obvious reasons. For a compression function f : (0,∞) → (0,1) you want d/dx f > 0 and necessarily lim x→∞ d/dx f(x) = 0; f(0) = 0; lim x→∞ f(x) = 1. Some functions with these properties are

1 - e^-Cx for a any positive constant C, and

2 / (1 + e^-Cx) - 1 (the Sigmoid function).