Soustraction d'ensembles non négatifs

La signification du terme «efficace» n’est pas claire.

Pour un algorithme, vous pouvez

• .map () tableau d'entrée pour saisir arr tableau d'entiers ou de décimales moins n nombre divisé par l'entrée .length , map

• .filter () résultats du tableau map aux éléments dont la valeur est supérieure à 0 , pas

• .filter () éléments du tableau map aux éléments supérieurs ou égaux à 0 , .matches

• .reduce () pas tableau à la somme des éléments inférieurs à 0 , sous-total

• transmettez subtotal à Math.abs () pour obtenir la valeur absolue d'un entier, divisée par matches.length moins not.length pour obtenir le sous-traitant à appliquer à l'entrée, N

• .map () map, où la valeur de minuend est inférieure ou égale à 0 return 0 , sinon la valeur de retour moins N , avec .toFixed (3) enchaîné pour répondre à l'exigence de 3 chiffres décimaux décrits comme sortie attendue, transtypés en nombre avec ajouter l'opérateur + , résultat

• retourne le résultat

const nonNegativeSubtraction = (arr, n) => {
  const map = arr.map(x => x - (n / arr.length));
  const not = map.filter(x => x < 0);
  const matches = map.filter(x => x >= 0);
  const subtotal = not.reduce((a, b) => a + b);
  const N = Math.abs(subtotal) / (matches.length - not.length);
  const result = map.map(x => x <= 0 ? 0 : +(x - N).toFixed(3));
  return result;
}

const test = [0, 0, 1 - 0.333, 2 - 0.333, 3 - 0.333];

let input = [4,5,6,7,8]; // minuend

let n = 25; // subtrahend

let res = nonNegativeSubtraction(input, n); // result

console.log(res);

console.assert(JSON.stringify(test) !== JSON.stringify(res), [test, res]);

Je suis venu avec cette solution qui utilise la récursivité. Il n'est pas nécessaire de pré-trier le tableau pour fonctionner, mais cela empêchera l'algorithme de profiter de certains avantages. Les explications se trouvent dans le code ...

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

const spreadSubtract = (arr, val) =>
{
    let avgSub = val / arr.length;

    return arr.map((x, idx) =>
    {
        if (x < avgSub)
        {
            avgSub = (val -= x) / (arr.length - idx - 1);
            return 0;
        }
        else
        {
            return x - avgSub;
        }
    });
}

// Tests
let test1 = [[4, 5, 6, 7, 8], 25];
let test2 = [[0, 9, 1, 5, 3], 11];
let test3 = [[4, 0, 1, 2, 5], 20];

// Note array are sorted first.
console.log(spreadSubtract(test1[0], test1[1]));
console.log(spreadSubtract(test2[0].sort(), test2[1]));
console.log(spreadSubtract(test3[0].sort(), test3[1]));

Et voici une approche que vous pouvez utiliser lorsque le tableau est trié par ordre croissant:

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

const spreadSubtract = (arr, val) =>
{
    // Get the numbers of positive (> 0) elements on the array.

    let len = arr.filter(x => x > 0).length;

    // Get the new subtract value.

    let sub = val / len;

    // Stop condition: if the positive (> 0) elements on the
    // array minus the subtract value are all positive (> 0),
    // then return the mapped array.

    if (!arr.some(x => x > 0 && x - sub < 0))
    {
        return arr.map(x => x > 0 ? x - sub : x);
    }
    
    // Get the minimum element on the array that will be
    // negative when subtracting <sub> from it.

    sub = Math.min(...arr.filter(x => x > 0 && x - sub < 0));

    // Proceed to next iteration of the recursion.

    return spreadSubtract(
        arr.map(x => x > 0 ? x - sub : x),
        val - sub * len
    );
}

// OP example:
console.log(spreadSubtract([4, 5, 6, 7, 8], 25));

// Another test:
console.log(spreadSubtract([0, 9, 1, 5, 3], 11));

// Test subtract greater than the sum of array values:
console.log(spreadSubtract([4, 0, 1, 2, 5], 20));

Vous pouvez réduire beaucoup de boucles nécessaires, en supposant que le nombre défini

1. N'a que des valeurs positives
2. La somme de l'ensemble est supérieure à la valeur à soustraire
3. Il peut être trié.

Au point 3. vous avez dit dans les commentaires que c'était bien de trier ceci, alors voici l'algorithme que j'ai en tête. C'est verbeux en termes de noms de variables, mais j'espère que cela rend les choses plus claires. Dans l'ensemble, ce n'est pas trop complexe:

const input = [4, 5, 6, 7, 8];
subtractFromSet(input, 25);
console.log(input);

function subtractFromSet(numberSet, totalToSubtract) {
  numberSet.forEach((currentMember, index, wholeSet) => { //using .forEach instead of .map
    const remainingElements = wholeSet.length - index
    const averageToSubtract = totalToSubtract / remainingElements;
    
    const toSubtract = Math.min(averageToSubtract, currentMember);
    //modify both the total remaining to subtract and the current element
    totalToSubtract -= toSubtract;
    wholeSet[index] = currentMember - toSubtract; //modify the array directly
  })
}

Pour l'expliquer avec des mots, voici ce qui se passe

1. Soustraire une valeur de la somme de l'ensemble équivaut à soustraire la valeur divisée par la taille de l'ensemble de chaque membre. Ainsi [4, 5, 6, 7, 8] - 25 serait 4 - 5 , 5 - 5 , 6 - 5 , etc.
2. Si nous ne voulons pas de négatifs, nous soustrayons uniquement jusqu'à le membre actuel. Donc, avec le membre actuel 4 et la moyenne étant 25/5 = 5 , nous ne pouvons soustraire que 4 .
3. Afin de répartir le reste, nous le rajoutons simplement au total restant à soustraire pour le reste des membres. Ainsi, lorsque nous arrivons au deuxième membre 5 , la moyenne est maintenant de (25 - 4) / (5 - 1) car nous n'avons pas pu soustraire le complet 5 en moyenne la première fois, seulement 4 , et les éléments restants sont un de moins. Cela donne 5,25 .

Et donc en passant par chaque membre et en ajustant le total puis la moyenne nécessaire pour soustraire, nous obtenons le résultat correct. Cependant, soyez conscient de l ' arithmétique en virgule flottante dans la programmation, car cela peut conduire à des résultats qui sont légèrement décalés. Si vous arrondissez à des chiffres suffisamment significatifs pour vos besoins, vous pouvez en grande partie éviter cela.

Une dernière chose - comme je l'ai dit, l'entrée doit être triée. Cela peut être fait facilement comme ceci:

const unsortedArray = [6, 4, 7, 8, 5];
const sortedArray = unsortedArray.sort((a, b) => a - b)

console.log(sortedArray);

J'ai laissé de côté l'algorithme ci-dessus pour me concentrer sur ce que nous faisons réellement avec l'entrée triée.

La complexité totale de cet algorithme est assez décente - un tri décent vous rapporterait O (n log (n)) complexité temporelle. Dépend de l'implémentation du tri et du jeu de données - 5 éléments sont susceptibles d'être triés via un Bubblesort O (n ^ 2) mais là encore, il s'agit de 5 éléments, donc cela n'aura probablement pas d'impact. L'exécution de l'algorithme de soustraction est un simple O (n) . La complexité de l'espace pour la soustraction est O (2n) car .map () fait une copie du tableau. J'ai choisi cela car c'est un peu plus propre car vous avez toujours l'entrée. Mais vous pouvez également faire la soustraction sur place avec des changements minimes et cela vous apporterait une complexité d'espace O (n) .

const result = subtractFromSet([4, 5, 6, 7, 8], 25);
console.log(result)

function subtractFromSet(numberSet, totalToSubtract) {
  return numberSet.map((currentMember, index, wholeSet) => {
    const remainingElements = wholeSet.length - index
    const averageToSubtract = totalToSubtract / remainingElements;
    
    const toSubtract = Math.min(averageToSubtract, currentMember);
    //modify both the total remaining to subtract and the current element
    totalToSubtract -= toSubtract;
    return currentMember - toSubtract;
  })
}

Vous pouvez adopter une approche en boucle unique pour un tableau ordonné et examiner la valeur changeante pour la dispersion.

function subtract(array, delta) {
    return array.map((v, i, { length }) => {
        var d = delta / (length - i);
        delta -= Math.min(v, d);
        return Math.max(0, v - d);
    });
}

console.log(subtract([4, 5, 6, 7, 8], 25));

Aucun tri requis, mais en utilisant la récursivité.

let output = substract( [6,5,7,4,8], 25, 5)
console.log(output)
output = substract( [6,5,7,4,8.5], .10, 5)
console.log(output)
function substract(array, substractThis, length) {
	let delta = substractThis/length;
	let toSubstract;
	let out = array.map(ele => {
		toSubstract =  Math.min(ele, delta);
		substractThis -= toSubstract;
		ele = ele - toSubstract;
		length -= !ele;
		return ele;
	});
	if(substractThis < 1) {
		return out
	}
	return substract(out, substractThis, length)
}