In the code below I mix various flavors of icecream together (chocolate, strawberry, vanilla, & neapolitan) in order to produce a new, never-before-seen flavor of icecream.*
A flavor is represented by an array where the first element is simply a string, the name of the flavor.
The second element is a number from 0 to 100 representing the vanilla component, the third the chocolate component, and the fourth the strawberry component.
Mixing is performed by averaging all the input flavors (arrays) together.
After mixing, I attempt to determine which flavor the new mixture is most similar to. This is done by taking the sum of the absolute difference of the mystery icecream and known flavors. The smaller the sum, the smaller the difference and greater the similarity.
In this specific example, the mixture is 6 parts strawberry icream and 1 part of each of the other flavors. Predictably, the strawberry is calculated to be the most similar, followed by neapolitan, because it is itself a mixture.
This is a good ways towards reverse-engineering the mixture, but I want to go further. I want to determine the precise proportions of each flavor that went into the mixture.
In this example it would be as stated above: 6 strawberry, 1 vanilla, 1 chocolate, 1 neapolitan.
Of course, there may be many (infinite?) ways to come up with a given mixture. But I am looking for the most parsimonious possibility.
For example, 1 part neopolitan plus 1 part strawberry is identical to 4 parts strawberry plus 3 parts of every other flavor. But the former is more parsimonious.
How would I go about predicting how a mixture was created?
I don't know what the technical term for this is.
const mixture = mixIcecreams([
['vanilla', 100, 0, 0],
['chocolate', 0, 100, 0],
['neapolitan', 33, 33, 33],
['strawberry', 0, 0, 100],
['strawberry', 0, 0, 100],
['strawberry', 0, 0, 100],
['strawberry', 0, 0, 100],
['strawberry', 0, 0, 100],
['strawberry', 0, 0, 100],
]);
console.log(mixture);
const distances = calculateDistances(mixture, [
['vanilla', 100, 0, 0],
['chocolate', 0, 100, 0],
['strawberry', 0, 0, 100],
['neapolitan', 33, 33, 33],
]);
console.log('Distances:');
console.log(distances);
console.log(
`The icecream named "${mixture[0]}" is most similar to "${distances[0][0]}" icecream.`
);
// Calculate the "distance" between a "target" vector and "sources" vectors.
// Smaller distance means more similarity.
function calculateDistances(target, sources) {
return (
sources
.map((source) => [
// First element is the label.
source[0],
target.reduce(
(distance, value, i) =>
// Avoid doing math with the first element (the label).
i === 0 ? distance : distance Math.abs(source[i] - value),
0
),
])
// Sort by shortest distance (most similar).
.sort((a, b) => a[1] - b[1])
);
}
function mixIcecreams(icecreams) {
return icecreams.reduce(
(mixture, icecream, i) => {
icecream.forEach((value, j) => j !== 0 && (mixture[j] = value));
if (i === icecreams.length - 1) {
return mixture.map((value, j) =>
// Ignore the first element, it's just a label.
j === 0 ? value : value / icecreams.length
);
}
return mixture;
},
Array.from({ length: icecreams[0].length }, (_, i) =>
i === 0 ? 'mixture' : 0
)
);
}*Patent pending.
CodePudding user response：
If I understand your problem correctly, in mathematical terms you seem to need the solution of an underdetermined system of equations, in the least squares sense.
I put up a quick solution that can be improved upon.
I can further explain, if interesting.
Edit: I added a simple integer approximation, to find an integer solution that best approximates the percentual one.
const mixture = mixIcecreams([
['vanilla', 100, 0, 0],
['chocolate', 0, 100, 0],
['neapolitan', 33, 33, 33],
['strawberry', 0, 0, 100],
['strawberry', 0, 0, 100],
['strawberry', 0, 0, 100],
['strawberry', 0, 0, 100],
['strawberry', 0, 0, 100],
['strawberry', 0, 0, 100],
]);
console.log(mixture);
const distances = calculateDistances(mixture, [
['vanilla', 100, 0, 0],
['chocolate', 0, 100, 0],
['strawberry', 0, 0, 100],
['neapolitan', 33, 33, 33],
]);
console.log('Distances:');
console.log(distances);
console.log(
`The icecream named "${mixture[0]}" is most similar to "${distances[0][0]}" icecream.`
);
const probableMixture = mostProbableMixture(mixture, [
['vanilla', 100, 0, 0],
['chocolate', 0, 100, 0],
['strawberry', 0, 0, 100],
['neapolitan', 33, 33, 33],
]
);
console.log('most likely mixture, percent', probableMixture)
const im = integerMix(probableMixture, 100);
// the second argument, nMax, is the maximum number allowed from one basic flavor
// the larger nMax, the closer you may get to the exact mixture
console.log('integer mixture', im)
const rm = repeatIntegerMix(im, [
['vanilla', 100, 0, 0],
['chocolate', 0, 100, 0],
['strawberry', 0, 0, 100],
['neapolitan', 33, 33, 33],
]);
console.log('verify mixture', mixIcecreams(rm))
// Calculate the "distance" between a "target" vector and "sources" vectors.
// Smaller distance means more similarity.
function calculateDistances(target, sources) {
return (
sources
.map((source) => [
// First element is the label.
source[0],
target.reduce(
(distance, value, i) =>
// Avoid doing math with the first element (the label).
i === 0 ? distance : distance Math.abs(source[i] - value),
0
),
])
// Sort by shortest distance (most similar).
.sort((a, b) => a[1] - b[1])
);
}
function mixIcecreams(icecreams) {
return icecreams.reduce(
(mixture, icecream, i) => {
icecream.forEach((value, j) => j !== 0 && (mixture[j] = value));
if (i === icecreams.length - 1) {
return mixture.map((value, j) =>
// Ignore the first element, it's just a label.
j === 0 ? value : value / icecreams.length
);
}
return mixture;
},
Array.from({ length: icecreams[0].length }, (_, i) =>
i === 0 ? 'mixture' : 0
)
);
}
function mostProbableMixture(mixture, baseFlavors){
const nVars = baseFlavors.length,
nEq = mixture.length - 1,
At = baseFlavors.map(flavor=>flavor.slice(1)),
b = mixture.slice(1),
AAt = Array(nEq).fill(0).map(z=>Array(nEq));
//compute A*At
for(let i = 0; i < nEq; i ){
for(let j = 0; j < nEq; j ){
AAt[i][j] = 0;
for(let k = 0; k < nVars; k ){
AAt[i][j] = At[k][i]*At[k][j];
}
}
}
// normalize rows
for(let i = 0; i < nEq; i ){
let maxRow = Math.abs(b[i]);
for(let j = 0; j < nEq; j ){
maxRow = Math.max(maxRow, Math.abs(AAt[i][j]));
}
for(let j = 0; j < nEq; j ){
AAt[i][j] = AAt[i][j] /maxRow;
}
b[i] = b[i]/maxRow;
}
// Solve (for t) A * At * t = b
// Gaussian elimination; diagonal dominance, no pivoting
for(let j = 0; j < nEq-1; j ){
for(let i = j 1; i < nEq; i ){
let f = AAt[i][j] / AAt[j][j];
for(let k = j 1; k < nEq; k ){
AAt[i][k] -= f * AAt[j][k];
}
b[i] -= f*b[j];
}
}
const t = Array(nEq).fill(0);
t[nEq-1] = b[nEq-1]/AAt[nEq-1][nEq-1];
for(let i = nEq-2; i >= 0; i--){
let s = b[i];
for(let j = i 1; j<nEq; j ){
s -= AAt[i][j]*t[j];
}
t[i] = s/AAt[i][i];
}
// the solution is y = At * t
const y = Array(nVars).fill(0);
let sy = 0;
for(let i = 0; i < nVars; i ){
for(let j = 0; j < nEq; j ){
y[i] = At[i][j] * t[j];
}
sy = y[i];
}
for(let i = 0; i < nVars; i ){
y[i] = y[i]/sy*100;
}
return y.map((yi, i)=>[baseFlavors[i][0], yi]);
}
function integerMix(floatMix, nMax){
const y = floatMix.map(a=>a[1]),
maxY = y.reduce((m,v)=>Math.max(m,v));
let minAlpha = 0, minD = 1e6;
for(let alpha = 1/maxY; alpha <= nMax/maxY; alpha =(nMax-1)/10000/maxY){
//needs refining!!
const sdif = y.map(v=>Math.pow(Math.round(v*alpha)-v*alpha, 2));
const d2 = sdif.reduce((s,x)=>s x);
if(d2 < minD){
minD = d2;
minAlpha = alpha;
}
}
return floatMix.map(([name, f]) => [name, Math.round(minAlpha*f)]);
}
function repeatIntegerMix(integerMix, baseFlavors){
return integerMix.flatMap(([name, n], i)=> Array.from({length: n}, e=>baseFlavors[i].slice(0)));
}