ishanmeh ishanmeh - 1 month ago 11
C# Question

Get set of random numbers from input List having fixed sum using C#

I am looking for a C# algorithm that would give me a set of random integers from input List, such that the sum of obtained random integers is N.

For example:
If the list is {1,2,3,4,5,6...100} and N is 20, then the algorithm should return a set of random numbers like {5,6,9} or {9,11} or {1,2,3,4,10} etc.

Note that the count of integers in result set need not be fixed. Also, the input list can have duplicate integers. Performance is one of my priority as the input list can be large (around 1000 integers) and I need to randomize about 2-3 times in a single web request. I am flexible with not sticking to List as datatype if there is a performance issue with Lists.

I have tried below method which is very rudimentary and performance inefficient:


  1. Use the Random class to get a random index from the input list

  2. Get the integer from input list present at index obtained in #1. Lets call this integer X.

  3. Sum = Sum + X.

  4. Remove X from input list so that it does not get selected next.

  5. If Sum is less than required total N, add X to outputList and go back to #1.

  6. If the Sum is more than required total N, reinitialize everything and restart the process.

  7. If the Sum is equal to required total N, return outputList

    while(!reachedTotal)
    {
    //Initialize everything
    inputList.AddRange(originalInputList);
    outputList = new List<int>();
    while (!reachedTotal)
    {
    random = r.Next(inputList.Count);
    sum += inputList.ElementAt(random);
    if(sum<N)
    {

    outputList.Add(inputList.ElementAt(random));
    inputList.RemoveAt(random);
    }
    else if(sum>N)
    break;
    else
    reachedTotal = true;
    }
    }


Answer

This is a stochastical approach that gives you a solution within a 10% range of N - Assuming one exists

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;

namespace StackOverflowSnippets
{
    class Program
    {
        static void Main(string[] args)
        {
            // ----------------------------------------------------------------------------------
            // The code you are interested in starts below this line
            const Int32 N = 100;
            Int32 nLowerBound = (90 * N) / 100; Int32 nUpperBound = (110 * N) / 100;

            Random rnd = new Random();
            Int32 runningSum = 0;
            Int32 nextIndex = 0;

            List<Int32> inputList = GenerateRandomList( /* entries = */ 1000);
            List<Int32> o = new List<Int32>();

            while (runningSum < nLowerBound)
            {
                nextIndex = rnd.Next(inputList.Count); if (nUpperBound < (runningSum + inputList[nextIndex])) continue;

                runningSum += inputList[nextIndex];
                o.Add(inputList[nextIndex]);
                inputList.RemoveAt(nextIndex);
            }
            // The code you are interested in ends above this line
            // ----------------------------------------------------------------------------------

            StringBuilder b = new StringBuilder();

            for(Int32 i = 0; i < o.Count;i++)
            {
                if (b.Length != 0) b.Append(",");
                b.Append(o[i].ToString());
            }

            Console.WriteLine("Exact N    : " + N);
            Console.WriteLine("Upper Bound: " + nUpperBound);
            Console.WriteLine("Lower Bound: " + nLowerBound);
            Console.WriteLine();

            Console.WriteLine("sum(" + b.ToString() + ")=" + GetSum(o).ToString());
            Console.ReadLine();
        }

        // -------------------------------------------------------------------
        #region Helper methods
        private static object GetSum(List<int> o)
        {
            Int32 sum = 0;

            foreach (Int32 i in o) sum += i;

            return sum;
        }
        private static List<Int32> GenerateRandomList(Int32 entries)
        {
            List<Int32> l = new List<Int32>();

            for(Int32 i = 1; i < entries; i++)
            {
                l.Add(i);
            }

            return l;
        }
        #endregion
    }
}

EDIT

  1. Forgot to remove the element from the input-list so it cannot be selected twice
  2. Fixed the 'remove element' insertion