Randomly pick from a list of numbers until specific limit

Question

Let's say I have a list of predefined numbers, and a list of predefined max limits.

When a user picks a limit, I need to randomly pick a certain amount of numbers from the first list, up until their totals match (As close to, but never over) the user selected total.

What I've tried so far:

void Main()
{
    List<int> num = new List<int>(){ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,17, 18, 19, 20 };
    int maxNum = 17;

    List<int> curNum = new List<int>();
    int curTotal = 0;

    foreach(int sel in num.Where(x => x < maxNum)){

    curTotal += sel;

    if(curTotal <= maxNum){
        curNum.Add(sel);
    }


    }
}

There needs to be x amount of numbers picked. In this case, 5 numbers picked, +- 20 numbers to be randomly picked from, and 1 max values.

So the end list should look like this:

1, 2, 3, 4, 7 (17)
1, 2, 3, 5, 6 (17)
1, 2, 3, 4, 6 (16) <- This will be fine if there isn't a solution to the max value.

It would be better to start with the largest number and add on progressively smaller pieces. — kgh, Jan 27 '15 at 17:22
What about this: If the last random number is too big (exceeds the total) just use the remaining (total-sum) as the last "random number"? — DrKoch, Jan 27 '15 at 17:23
The numbers can't be dynamically created. It *has* to be from a list. — TheGeekZn, Jan 27 '15 at 17:24
Brute Force: pick 15 numbers, calc sum, repeat until it matches — DrKoch, Jan 27 '15 at 17:28
If it works you may optimize: Start over if sum gets too big, and so on — DrKoch, Jan 27 '15 at 17:29
In your code snippet you'll need to add: random picking, retry loop — DrKoch, Jan 27 '15 at 17:35
@OllieJones feels more like variation of http://en.wikipedia.org/wiki/Knapsack_problem to me. — Alexei Levenkov, Jan 27 '15 at 17:48
@SemiDemented please edit your question with very clear definition of how you want to make picks. I don't get how it could be random and exactly matching total at the same time. — Alexei Levenkov, Jan 27 '15 at 17:52
@AlexeiLevenkov I've tried - Every Time I rewrite it it leads me to believe I need to have a defined list of integers for every max value - because you can't guarantee that you will always be able to add the picked numbers to a value. I will have to settle for as-close-to the max value. — TheGeekZn, Jan 27 '15 at 17:58

score 0 · Answer 1 · edited May 23 '17 at 11:49

0

I think shuffle + "take while sum < limit" may be what you are looking for.

Something like following:

var shuffledList = num.ToList();
shuffledList.Shuffle();

var sum = 0;
var count = 0;
while (shuffledList[count] + sum < max)
{ 
    sum += shuffledList[count++];
}
return shuffledList.Take(count);

edited May 23 '17 at 11:49

Community

1
1

answered Jan 27 '15 at 18:09

Alexei Levenkov

98,904
14
127
179

I get a range from 0 - 5 items with this – TheGeekZn Jan 27 '15 at 18:15
@SemiDemented I think "+=" should fix that (see updated code, not tested at all) – Alexei Levenkov Jan 27 '15 at 19:17

score 0 · Answer 2 · answered Jan 27 '15 at 18:37

Building upon @AlexiLevenkov's answer:

class Program { static void Main(string[] args) { int limit = 17; int listSize = 5;

        List<int> a = new List<int>() { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };
        a.Shuffle();
        List<int> genList = new List<int>();
        int stoppedCount = 0;

        for (int i = 0; i < a.Count(); i++)
        {

            if (i < listSize)
            {
                genList.Add(a[i]);
                stoppedCount = i;
            }
            else
            {
                break;
            }
        }

        while (genList.Sum() > limit)
        {
            genList.Remove(genList.Max());

            stoppedCount++;
            genList.Add(a[stoppedCount]);
        }
    }

}

static class ThisClass
{
    public static void Shuffle<T>(this IList<T> list)
    {
        Random rng = new Random();
        int n = list.Count;
        while (n > 1)
        {
            n--;
            int k = rng.Next(n + 1);
            T value = list[k];
            list[k] = list[n];
            list[n] = value;
        }
    }
}

Randomly pick from a list of numbers until specific limit

2 Answers2