I have a vector of numbers from 0 to 1. For example:
[0.5, 0.5, 0.1]. I need to find a transformation which increases sum of the vector to asked number and:
-keeps the order of elements (if element1 was bigger than element2 it needs to stay that way)
-numbers stay in 0 - 1 range
-differences between elements are kept relatively close (if elements are close to each other in value they are close in value after the transformation); if possible for every four elements where a1>b1 and a2>b2 if a1-b1 > a2-b2 it stays that way after the transformation
-for any two elements a and b if a > b then (1-a')/(1-a) < (1-b)/(1-b') where a' and b' are elements after the transformation; that is the distance to 1 decreases relatively more for bigger elements than for lower ones;
Last point needs an example. Let's say I want to transform [0.8, 0.1, 0.1] to a vector of sum 2. The easiest way to do it is to move every element halfway to 1 arriving at: [0.9, 0.55, 0.55]. What I want is a transformation which moves 0.8 the most and 0.1 and 0.1 less. One try would be to apply a function (let's say x**2), like this: (code in Python but it should be easily readable for non programmers)
def transform(v, newsum, func):
F = sum([func(x) for x in v])
oldsum = sum(v)
return [x + (newsum-oldsum)*func(x)/F for x in v]
This satisfies a requirement that biggest elements move more, like in this example:
>>> transform([0.5, 0.5, 0.1], 2, lambda x: x*x)
[0.9411764705882353, 0.9411764705882353, 0.11764705882352942]
but it has a flow that elements after a transformation may exceed 1:
>>> transform([0.8, 0.4, 0.3, 0.1], 2.4, lambda x: x*x)
[1.3688888888888886, 0.5422222222222222, 0.37999999999999995, 0.1088888888888889]
Part 2: The same problem, but now there are is another vector of weights and the goal is to make a transformation for required weighted sum (weights * numbers in resulting vector (weights stay unchanged) sum up to required number).
I need this transformation for adjusting vectors in huge decision tree so it would be great if it's not very computationally expensive (sorting would be painful for example but probably acceptable).
Since the element values are supposed to stay close to each other the new value $f(x)$ has to be a continuous function of the old one $x$, and $f:[0,1]\to[0,1]$ to keep them within $[0,1]$. To shift $x$ up we must have $f(x)\geq x$, and for larger to go to larger $f$ must be monotone increasing. The relative distance decrease condition is that the ratio of distances $\frac{1-f(x)}{1-x}$ is monotone decreasing.
It is convenient to make the change $\varphi(x):=1-f(1-x)$, then still $\varphi:[0,1]\to[0,1]$ and $\varphi$ is monotone increasing, but $f(x)\geq x$ becomes $\varphi(x)\leq x$ and the distance ratio decrease condition simplifies to $\frac{\varphi(x)}{x}$ being monotone increasing. The family $\varphi_n(x)=x^n$ with $n>1$ obviously satisfies all the conditions, leading to $f_n(x)=1-(1-x)^n$. With $n=2$ for example this transforms $[0.8,0.1,0.1]$ to $[0.96,0.19,0.19]$ with new/old distance ratios of $0.2,0.9,0.9$.
Since $f_1(x)=x$ and $f_n(x)\xrightarrow[n\to\infty]{}1$ for $x>0$ it is possible to make the sum of elements into any value between the original sum and $d$, the number of elements, by adjusting $n$. Solving for a particular sum $S$ isn't pleasant though, one has to solve $d-\sum_{k=1}^d(1-x_k)^n=S$ for $n$. It can be done with Newton's iteration to some accuracy, solving $d-d(1-\bar{x})^{n_0}=S$, where $\bar{x}$ is the average of $x_k$, gives $n_0$ for the initial guess. Alternatively, $\varphi$ can be chosen piecewise linear, reducing distance ratios more crudely, with the break point(s) and the value(s) at it serving as parameters, equation(s) for them should be easier to solve.