I have a list of numbers which I'm trying to sort efficiently into different sized groups. My group sizes are 1000, 500, 300. It's a bin packing problem. So if I have a list with
250, 100
I'd use a 300 sized group, as the difference between the total of the list and the total bin capacity is "waste".
So for a list that totaled 1600 the best that can be done would be 1 1000, 1 500, and 1 300.
I have logic to determine what sized bin to use, given the remaining total.
Since in my case the order of the list is important I cant simply sort by largest then bin pack. a list that is
85, 100, 240, ...
Needs to stay in that order. So to efficiently pack, I start by taking from the beginning of the list as many numbers as will fit in the given group, removing them from the list so they aren't used twice.
The problem is when I go to call the recursive function, I want to pass it a list of what numbers are left to use.
The problem I'm running into is the list I am passing to the recursive file is being passed by reference, so whatever changes happen in the later recursion are still present in the earlier one's. How could I get around this problem in C#?
Edit: I'm adding more of an example to hopefully explain my problem more completely
This will be lengthy so I apologize. I'm going to give a long winded example which shows my dilemma.
Say I have a list
100, 115, 105, 205, 195, 240, 240, 130, 180, 140, 225, 85
The total of which is 1960. So I'm wanting to create 2 1000 groups. Theres an added 15 for a safety factor, so each group starts at 15.
If I start from the front of the list and take numbers I get a group like this
Whats left of original list : 240, 130, 180, 140, 225, 85 total remaining 1000
group 1 : 15, 100, 115, 105, 205, 195, 240 total 975
The remaining amount is 1000, which when the next recursion try's to make the second 1000 group will be left with the 85, resulting in a fail.
So the algorithm is to go back to group 1, (the "progress" from the second groups iteration now gone), remove the last number, then start looking at the remaining list to find the next first number that would fit.
In this case there the last 240 from the group 1 would be removed, and replaced with the next 240 in the list, so the next group 2 iteration would fail again.
So go the "progress" from that iteration of group 2 would be removed, go back to group 1 and remove the 240. Now group one and the remaining look like this
Remaining : 240, 240, 130, 180, 140, 225, 85
Group 1 : 15, 100, 115, 105, 205, 195
The next iteration should then take the 130 and then the 85 which would then make a group of 950, so the remaining is 1025 and once again would not fit.
So on and so on. The problem I'm having is have one recursive level know which numbers it's already tried and knowing to avoid them, while having the next iteration down not avoid those that were avoided by the previous one. When group 1 removes the 240 from it's list and returns it the the remaining, when group 2 starts picking from the list it would start with 240 since it would be first in the list
The solution with this list in the end would be
Group 1 : 15, 100, 115, 105, 205, 195, 180, 85
Group2 : 15, 240, 240, 130, 140, 225
You could try to clone the list whenever you call the recursive function and pass the freshly created clone instead of the original list. This could look something like this:
public List<int> RecursiveFunction(List<int> listOfRemainingNumbers)
{
// Do some logic
List<int> numbers = new List<int>();
List<int> clone = new List<int>(numbers);
return RecursiveFunction(clone);
}
Please note that this is not really an efficient approach. Especially when your lists are very large and contain multiple thousands of items, this approach will use a lot of memory.
A more efficient approach may be not to use recursion and to use a simple loop instead and trying not to remove the items from the list, possibly utilizing the out keyword to get an additional "return value" from your function.