Verificare se una lista (o una sottolista di quell'elenco) di valori decimali può essere uguale a una certa somma

Question

Ciao Ho uno List<decimal> contenente valori compresi tra] 0; 1]. Voglio verificare se un totale (o subtotale) di questi valori può essere uguale a 1 (o quasi).

Posso anche utilizzare le funzioni Linq per filtrare o manipolare l'elenco.

risultati desiderati:

• un elenco contenente {0.7, 0.7, 0.7} dovrebbe return false;
• Un elenco contenente {0.7, 0.3, 0.7} deve restituire true;
• Un elenco contenente {0.777777, 0.2, 0.1} deve restituire falso;
• Un elenco contenente {0,33333, 0,33333, 0,33333} deve restituire true;
• Un elenco contenente {0,4, 0,5, 0,6, 0,3} deve restituire true.

Ovviamente, voglio qualcosa con il minor costo possibile delle prestazioni.

Answer 1

AGGIORNAMENTO - ora non repetively riassumere provare questo

bool isClose(IEnumerable<decimal> list, decimal epislon) { 
    return isClose(Enumerable.Empty<decimal>(),list,0,list.Sum(),epislon); 
} 
// Define other methods and classes here 
bool isClose(IEnumerable<decimal> left,IEnumerable<decimal> right, decimal leftSum,decimal rightSum, decimal epsilon) { 
    if (leftSum>=1-epsilon && leftSum<=1+epsilon) return true; 
    if (leftSum>1+epsilon) return false; 
    if (leftSum+right.Sum()< 1-epsilon) return false; 
    if (!right.Any()) return false; 

    for (var i=0;i<right.Count();i++) { 
    var skip=right.Skip(i); 
    var newItem=skip.First(); 
    if (isClose(left.Concat(skip.Take(1)),skip.Skip(1),leftSum+newItem,rightSum-newItem,epsilon)) return true; 
    } 
    return false; 
} 



isClose(new[] {0.7m,0.7m,0.7m},0.001m); // returns false 
isClose(new[] {0.7m,0.3m,0.7m},0.001m); //returns true 
isClose(new[] {0.777777m,0.2m,0.1m},0.001m); //returns false 
isClose(new[] {0.33333m,0.33333m,0.33333m},0.001m); //returns true 

EDIT 5 ° prova

isClose(new[] {0.4m, 0.5m, 0.6m, 0.3m},0.001m); //returns true 

Answer 2

Questo è il numero di sottogruppi, un caso speciale del problema dello zaino. È difficile (NP-completo). Gli algoritmi più noti hanno una complessità esponenziale. Tuttavia ci sono algoritmi approssimativi con complessità polinomiale. Questi rispondono alla domanda "c'è un sottoinsieme che somma a 1 ± ε?"

• http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/nanda-scribe-3.pdf
• http://en.wikipedia.org/wiki/Subset_sum_problem
• TAOCP di Knuth (probabilmente)

Answer 3

public static bool SubListAddsTo(this IEnumerable<decimal> source, 
    decimal target, decimal tolerance) 
{ 
    decimal lowtarget = target - tolerance; 
    decimal hightarget = target + tolerance; 
    HashSet<decimal> sums = new HashSet<decimal>(); 
    sums.Add(0m); 
    List<decimal> newSums = new List<decimal>(); 

    foreach(decimal item in source) 
    { 
    foreach(decimal oldSum in sums) 
    { 
     decimal sum = oldSum + item; 
     if (sum < lowtarget) 
     { 
     newSums.Add(sum);//keep trying 
     } 
     else if (sum < hightarget) 
     { 
     return true; 
     } 
     //else { do nothing, discard } 
    } 
    foreach (decimal newSum in newSums) 
    { 
     sums.Add(newSum); 
    } 
    newSums.Clear(); 
    } 
    return false; 
} 

Testato da:

List<decimal> list1 = new List<decimal>(){0.7m, 0.7m, 0.7m}; 
List<decimal> list2 = new List<decimal>(){0.7m, 0.3m, 0.7m}; 
List<decimal> list3= new List<decimal>(){0.777777m, 0.2m, 0.1m}; 
List<decimal> list4 = new List<decimal>() { 0.33333m, 0.33333m, 0.33333m }; 
List<decimal> list5 = new List<decimal>() { 0.4m, 0.5m, 0.6m, 0.3m }; 

Console.WriteLine(list1.SubListAddsTo(1m, 0.001m)); //false 
Console.WriteLine(list2.SubListAddsTo(1m, 0.001m)); //true 
Console.WriteLine(list3.SubListAddsTo(1m, 0.001m)); //false 
Console.WriteLine(list4.SubListAddsTo(1m, 0.001m)); //true 
Console.WriteLine(list5.SubListAddsTo(1m, 0.001m)); //true 

Answer 4

Ecco un niave approccio piuttosto semplice,, forza bruta. Non sarà efficiente, ma speriamo sia più facile da capire.

private const decimal threshold = .001M; 

public static bool CloseEnough(decimal first, decimal second, decimal threshold) 
{ 
    return Math.Abs(first - second) < threshold; 
} 

private static bool SubsetSum(List<decimal> data, int desiredSum) 
{ 

    int numIteratons = (int)Math.Pow(2, data.Count); 

    for (int i = 1; i < numIteratons; i++) 
    { 
     decimal sum = 0; 
     int mask = 1; 
     for (int j = 0; j < data.Count && sum < desiredSum + threshold; j++) 
     { 
      if ((i & mask) > 0) 
      { 
       sum += data[j]; 
      } 
      mask <<= 1; 
     } 

     if (CloseEnough(sum, desiredSum, threshold)) 
     { 
      return true; 
     } 
    } 

    return false; 
} 

Answer 5

modificato: il mio codice originale non ha permesso per il ravvicinamento (0.9999 = 1).

Questo utilizza una bitmap del numero di varianti per mascherare i valori nell'array sorgente in modo da forzare brute tutte le varianti.

Questo è circa 7,5 volte più veloce della risposta accettata quando testati su tutti i cinque casi di test in un ciclo di conteggio di milioni (circa 41 secondi contro circa 5,5 secondi). È circa due volte più veloce della sln di David B e circa il 15% più veloce della sln di Servy.

public static bool Test(decimal[] list, decimal epsilon) 
    { 
     var listLength = list.Length; 
     var variations = (int)(Math.Pow(2, listLength) - 1); 
     var bits = new bool[9]; 

     for (var variation = variations; variation > 0; variation--) 
     { 
      decimal sum = 0; 

      bits[1] = (variation & 1) == 1; 
      bits[2] = (variation & 2) == 2; 
      bits[3] = (variation & 4) == 4; 
      bits[4] = (variation & 8) == 8; 
      bits[5] = (variation & 16) == 16; 
      bits[6] = (variation & 32) == 32; 
      bits[7] = (variation & 64) == 64; 
      bits[8] = (variation & 128) == 128; 

      for (var bit = listLength; bit > 0; bit--) 
      { 
       if (bits[bit]) 
       { 
        sum += list[bit - 1]; 
       } 
      } 

      if (Math.Abs(sum - 1) < epsilon) 
      { 
       return true; 
      } 
     } 

     return false; 
    } 

edit: questa versione Newtest è il 30% più veloce rispetto alla versione di cui sopra ed è più di dieci volte più veloce rispetto alla soluzione accettata. Rimuove la creazione dell'array per ottenere la maschera di bit in favore dell'approccio di Servy, da cui proviene la maggior parte del miglioramento. Rimuove anche la chiamata Math.Abs ​​che ha dato un miglioramento marginale.

private const decimal Epislon = 0.001m; 
    private const decimal Upper = 1 + Epislon; 
    private const decimal Lower = 1 - Epislon; 

    private static bool NewTest(decimal[] list) 
    { 
     var listLength = list.Length; 
     var variations = (int)(Math.Pow(2, listLength) - 1); 

     for (var variation = variations; variation > 0; variation--) 
     { 
      decimal sum = 0; 
      int mask = 1; 

      for (var bit = listLength; bit > 0; bit--) 
      { 
       if ((variation & mask) == mask) 
       { 
        sum += list[bit - 1]; 
       } 
       mask <<= 1; 
      } 

      if (sum > Lower && sum < Upper) 
      { 
       return true; 
      } 
     } 

     return false; 
    }