title: Most efficient way to choose an item from a list with a given probability
body: <p>I'm trying to solve a rather simple problem where I have a list of items where the probability of finding an item also depends on the item itself (I imagine finding a shovel in a haystack is easier than finding a needle). </p>
  
  <p>I want a method that returns one of these items at random taking in consideration the probability of finding each one of them.</p>
  
  <p>So the items can be listed as such:</p>
  
  <pre><code>A - 100
  B - 50
  C - 10
  </code></pre>
  
  <p>Where the number represents how easy it is to find the item, where a higher value makes it easier to find.</p>
  
  <p>Running the below method 10000 times resulted in  finding the items in these quantities:</p>
  
  <pre><code>A - 6249  (100 / 160 = 0,625)
  B - 3139  (50  / 160 = 0,3125)
  C - 612   (10  / 160 = 0,0625)
  </code></pre>
  
  <p>Which pretty much proves that the below code works.</p>
  
  <p>So now my question is, how can this be improved considering that the list itself can contain many thousands of items. Right now the method will run in the worst case over each item in the list at least once, ie O(n).</p>
  
  <p>Can this be written into a LINQ/LAMBDA statement so the SQL server can deal with it and not lift all the items to C#?</p>
  
  <pre><code>public long GetRandomItem()
  {
      var allItems = _db.AllItems
          .Where(x =&gt; x.CanBeFound == true)
          .OrderByDescending(x =&gt; x.Rarity)
          .Select(x =&gt; new
          {
              x.Id,       // id of item
              x.Rarity,   // rarity between 1 and 100
          }).ToList();
  
      int totalRarity = allItems.Sum(x =&gt; x.Rarity);
      var random = new Random(DateTime.Now.Millisecond);
  
      var randomNumber = random.NextDouble() * totalRarity;
  
      double totalSoFar = 0;
      long chosenId = -1;
      foreach (var i in allItems)
      {
          totalSoFar += i.Rarity;
          if (totalSoFar &gt; randomNumber)
          {
              chosenId = i.Id;
              break; 
          }
      }
  
      return chosenId;
  }
  </code></pre>
  
  <p><strong>----- EDIT ------</strong></p>
  
  <p>Remade the LINQ to a version that only makes two queries to the database, and does not require a loop. Not completly sure if this is better yet as this will force the SQL to do more joins and selections of data.</p>
  
  <pre><code>public long GetRandomGamePiece()
  {
      int totalRarity = _db.GamePieceTemplates.Sum(x =&gt; x.Rarity);
      var randomNumber = 1 + Math.Round(_Random.NextDouble() * (totalRarity - 1)); 
  
      var randomItem = _db.GamePieceTemplates
          .Where(x =&gt; x.CanBeFound == true)
          .OrderBy(x =&gt; x.Id)
          .Select((x) =&gt; new
          {
              x.Id,       // id of item
              x.Rarity,   // rarity between 1 and 100
  
              // +1 so that it dosent overlap previous level
              MinRarity = _db.GamePieceTemplates.Where(y =&gt; y.Id &lt;= x.Id).Sum(y =&gt; y.Rarity) - x.Rarity + 1, 
              MaxRarity = _db.GamePieceTemplates.Where(y =&gt; y.Id &lt;= x.Id).Sum(y =&gt; y.Rarity)
          })
          .Single(x =&gt; x.MinRarity &lt;= randomNumber &amp;&amp; x.MaxRarity &gt;= randomNumber);
  
      long chosenId = -1;
      return  randomItem.Id;
  }
  </code></pre>
  
  <p>This gets converted to this TSQL:</p>
  
  <pre><code>SELECT TOP (2) 
      [Project6].[Rarity] AS [Rarity], 
      [Project6].[Id] AS [Id], 
      [Project6].[C1] AS [C1], 
      [Project6].[C2] AS [C2]
      FROM ( SELECT 
          [Project5].[Id] AS [Id], 
          [Project5].[Rarity] AS [Rarity], 
          ([Project5].[C1] - [Project5].[Rarity]) + 1 AS [C1], 
          [Project5].[C2] AS [C2]
          FROM ( SELECT 
              [Project4].[Id] AS [Id], 
              [Project4].[Rarity] AS [Rarity], 
              [Project4].[C1] AS [C1], 
              (SELECT 
                  SUM([Extent5].[Rarity]) AS [A1]
                  FROM [dbo].[GamePieceTemplates] AS [Extent5]
                  WHERE [Extent5].[Id] &lt;= [Project4].[Id]) AS [C2]
              FROM ( SELECT 
                  [Project3].[Id] AS [Id], 
                  [Project3].[Rarity] AS [Rarity], 
                  (SELECT 
                      SUM([Extent4].[Rarity]) AS [A1]
                      FROM [dbo].[GamePieceTemplates] AS [Extent4]
                      WHERE [Extent4].[Id] &lt;= [Project3].[Id]) AS [C1]
                  FROM ( SELECT 
                      [Project2].[Id] AS [Id], 
                      [Project2].[Rarity] AS [Rarity]
                      FROM ( SELECT 
                          [Project1].[Id] AS [Id], 
                          [Project1].[Rarity] AS [Rarity], 
                          [Project1].[C1] AS [C1], 
                          (SELECT 
                              SUM([Extent3].[Rarity]) AS [A1]
                              FROM [dbo].[GamePieceTemplates] AS [Extent3]
                              WHERE [Extent3].[Id] &lt;= [Project1].[Id]) AS [C2]
                          FROM ( SELECT 
                              [Extent1].[Id] AS [Id], 
                              [Extent1].[Rarity] AS [Rarity], 
                              (SELECT 
                                  SUM([Extent2].[Rarity]) AS [A1]
                                  FROM [dbo].[GamePieceTemplates] AS [Extent2]
                                  WHERE [Extent2].[Id] &lt;= [Extent1].[Id]) AS [C1]
                              FROM [dbo].[GamePieceTemplates] AS [Extent1]
                              WHERE 1 = [Extent1].[CanBeFound]
                          )  AS [Project1]
                      )  AS [Project2]
                      WHERE ( CAST( ([Project2].[C1] - [Project2].[Rarity]) + 1 AS float) &lt;= 130) AND ( CAST( [Project2].[C2] AS float) &gt;= 130)
                  )  AS [Project3]
              )  AS [Project4]
          )  AS [Project5]
      )  AS [Project6]
      ORDER BY [Project6].[Id] ASC
  </code></pre>