algorythm for distributing items as evenly as possible while keeping original order

Question

User2146470223 posted

Hi,

Sorry for possibly posting in the wrong forum but I don't know where to put this:

does anybody know if there is an algoryhtm to distribute items (numbers) of an array as evenly as possible while keeping the order of the items is a must.

Let's say I have 3 containers and I have numbers that equal 90.

• Each container should thus contain around 30, 30 being the maximum (but not necessarily if it's not possible because one of the numbers is higher than 30). But the total of each container should always be as close as possible to the limit (30) (means below or above that limit).
• Each container should contain at least 1 number.
• The initial order of the number must NOT be changed.

Examples:

Ex1:

array: 20, 10, 10, 10, 10, 5, 5, 30

Here it's quite easy:

c1 = 20, 10, 10 (=30)

c2 = 10, 10, 5, 5 (=30)

c3= 30 (=30)

Ex2:

array: 25, 10, 5, 10, 10, 5, 5, 30

Here it gets trickier:

either:

c1 = 25, 10 (=35)

c2 = 5, 10, 5, 5 (=25)

c3= 30 (=30)

or

c1 = 25 (=25)

c2 = 10, 5, 10, 5, 5 (=35)

c3= 30 (30)

Ex3:

array: 20, 40, 25, 2, 3

c1 = 20 (=20)

c2 = 40 (=40)

c3= 25, 2, 3 (=30)

Ex4:

array: 25, 40, 25, 2, 3

c1 = 25 (=25)

c2 = 40 (=40)

c3= 20, 2, 3 (=25)

Of course all these numbers are only examples. There could be 2 or more containers and the limit is always total of numbers in array divided by number of containers (rounded to next integer) and the numbers in the array are always integers.

I hope you get the point with my examples.

I have not found anything on the net until now.

Regards,

Pascal

Answer 1

User-707554951 posted

Hi Translating-IT,

Based on your requirement, following working code for your reference:

 protected void Page_Load(object sender, EventArgs e)
        {
            //Ex1:
            //int[] arry = { 20, 10, 10, 10, 5, 5, 30 };
            //Ex2:
           int[] arry = { 25, 10, 5, 10, 10, 5,5, 30 };
            //Ex3:
            //int[] arry = { 20, 40, 25, 2, 3 };
            //Ex4:
            //int[] arry = { 25, 40, 25, 2, 3 };
            List<int> sumChaArry = new List<int>();

            List<MyResult> myResultArry = new List<MyResult>();

            for (int i = 0; i <= arry.Length - 3; i++)
            {
                int sum1 = getSum(0, i, arry);
                // Debug.WriteLine("Here is sum1: "+ sum1);

                int j = i + 1;

                for (int m = j; m <= arry.Length - 2; m++)
                {
                    int sum2 = getSum(i + 1, m, arry);
                    //  Debug.WriteLine("Here is sum2: " + sum2);

                    int k = m + 1;

                    int sum3 = getSum(k, arry.Length - 1, arry);
                    // Debug.WriteLine("Here is sum3: " + sum3);


                    Debug.WriteLine("i:" + i + " j: " + j + " m:" + m + "  k:" + k);
                    Debug.WriteLine("Here is sum1: " + sum1 + "  sum2: " + sum2 + "sum3: " + sum3);

                    int[] sums = { sum1, sum2, sum3 };
                    int sumCha = getSumCha(sums);

                    sumChaArry.Add(getSumCha(sums));
                    //Debug.WriteLine("here is get Sum Cha: " + getSumCha(sums));

                    myResultArry.Add(new MyResult { i = i, j = j, m = m, k = k, sum1 = sum1, sum2 = sum2, sum3 = sum3, sumCha = sumCha });


                }
            }
            //int index= myResultArry.Min(a => a.sumCha);

            //MyResult final = myResultArry[index];
            int getMinCha = sumChaArry.Min();
            MyResult final = myResultArry.Where(a => a.sumCha == getMinCha).FirstOrDefault();

            // Debug.WriteLine("here is minCha result:"+ getMinCha);
            Debug.WriteLine("here is minCha result:" + final.sumCha + " i: " + final.i + " j: " + final.j + " m: " + final.m + " k: " + final.k);

            ToPrint(0, final.i, arry);

            ToPrint(final.j, final.m, arry);

            ToPrint(final.k, arry.Length - 1, arry);
        }

        public class MyResult
        {
            public int i { get; set; }
            public int j { get; set; }
            public int m { get; set; }
            public int k { get; set; }
            public int sum1 { get; set; }
            public int sum2 { get; set; }
            public int sum3 { get; set; }
            public int sumCha { get; set; }

        }

        public int getSumCha(int[] sums)
        {
            int sumCha = 0;
            for (int i = 0; i < sums.Length; i++)
            {
                sumCha += Math.Abs(sums[i] - 30);
            }
            return sumCha;
        }
        public void ToPrint(int index1, int index2, int[] arry)
        {

            for (int i = index1; i <= index2; i++)
            {
                Debug.Write(arry[i] + " ");

            }
            Debug.WriteLine("------------");

        }

        public int getSum(int index1, int index2, int[] arry)
        {
            int sum = 0;
            for (int i = index1; i <= index2; i++)
            {
                Debug.Write(arry[i]);
                sum += arry[i];
            }
            Debug.WriteLine("------------");
            return sum;
        }

After enter F5 to run this page, the Output window as below:

Best regards

Cathy

Answer 2

User2146470223 posted

ouch, forgot to add, that I need it in vb.net.

Converting to vb.net generates errors on getsum, getsumcha, toprint, myresult. -> doh, used the wrong online converter. with teleriks it worked.

So, if I got your code right, it is trying all possible solutions and then picking out the best one?

regards.

Pascal

Answer 3

User2146470223 posted

Hi Cathy,

I just did some testing and it works as expected from what I saw.

But what when I don't know how many containers there will be, how many items there are in the main array or the approximate limit per container? The latter should normally be total of all numbers in main array (ArrayTotal) divided by number of containers (NumCont) thus ArrayTotal/NumCont.

For the number of items in the main array it seems the code would need no change as it worked well even if I added more items to the array. But what about the rest?

Just being curious: do you have a repository to consult for such algorithms or did you work it out by yourself? I would not even have known where to start.

Edit: for the time being a maximum of 8 containers would seems to be valid but there might be more needed in future. So it would be 2 to 8 containers.

Edit2: Ok, already found out where to change the limit per container. Still looking for some way to program the main function so that it would not matter how many containers there are.

Edit3: if it would not be possible to get a function for container = n, how would the above solution look like with 4 containers? That way I could at least construct the cases after 4 and implement them with an if then pattern for container = 3 to 8, hoping I'll not need more than 8 containers that soon.

regards,

Pascal

Answer 4

User2146470223 posted

Hi Cathy,

This is my try to alter the function to 4 containers but it does not work at all:

		For i = 0 To arry.Length - 4
			sum1 = getSum(0, i, arry)
			j = i + 1
			For k = j To arry.Length - 3
				sum2 = getSum(i + 1, k, arry)
				l = k + 1
				For l = k To arry.Length - 2
					sum3 = getSum(l + 1, l, arry)
					m = l + 1
					sum4 = getSum(m, arry.Length - 1, arry)
					Response.Write("i:" & i & " j: " & j & " k:" & k & " l:" & l & " m:" & m)
					Response.Write("<br>Here is sum1: " & sum1 & "  sum2: " & sum2 & "  sum3: " & sum3 & "  sum4: " & sum4 & "<br>")
					sums = {sum1, sum2, sum3, sum4}
					sumCha = getSumCha(sums)
					sumChaArry.Add(getSumCha(sums))
					myResultArry.Add(New MyResult With {.i = i, .j = j, .k = k, .l = l, .m = m, .sum1 = sum1, .sum2 = sum2, .sum3 = sum3, .sum4 = sum4, .sumCha = sumCha})
				Next
			Next
		Next

PS: I removed the Dim parts from this code and declared all the variables further up, that way it gets easier to add more if then clauses for the different numbers of containers.

What did I miss?

I guess I made some mistake with the integers i, j, k, l or m.

Do I need to alter your code somewhere else than this part to get everything working?

Auntie Edit(h) says I forgot to greet. ;) :

Regards,

Pascal

Answer 5

User2146470223 posted

Hi,

I think I managed to get rid of most errors in the algorithm part for 4 containers but am not quite sure. One thing that for sure is still buggy is the ToPrint part. It does not show all the 4 result rows but only 3 what did I miss there?

	Dim divid As Integer

	Public Function test() As String
		Dim arry As Integer() = {2, 3, 50, 50, 45, 45}
		Dim sumChaArry As List(Of Integer) = New List(Of Integer)()
		Dim myResultArry As List(Of MyResult) = New List(Of MyResult)()
		Dim i As Integer
		Dim j As Integer
		Dim k As Integer
		Dim l As Integer
		Dim m As Integer
		Dim n As Integer
		Dim o As Integer
		Dim p As Integer
		Dim q As Integer
		Dim r As Integer
		Dim s As Integer

		Dim sum1 As Integer
		Dim sum2 As Integer
		Dim sum3 As Integer
		Dim sum4 As Integer
		Dim sum5 As Integer
		Dim sum6 As Integer
		Dim sum7 As Integer
		Dim sum8 As Integer

		Dim x As Integer
		Dim cont As Integer
		cont = 4
		divid = 23

		Dim sums As Integer()
		Dim sumCha As Integer

		For i = 0 To arry.Length - cont
			sum1 = getSum(0, i, arry)
			j = i + 1
			For k = j To arry.Length - 3
				sum2 = getSum(i + 1, k, arry)
				l = k + 1
				For m = l To arry.Length - 2
					sum3 = getSum(k + 1, m, arry)
					n = m + 1
					sum4 = getSum(n, arry.Length - 1, arry)
					Response.Write("i:" & i & " j: " & j & " k:" & k & " l:" & l & " m:" & m)
					Response.Write("<br>Here is sum1: " & sum1 & "  sum2: " & sum2 & "  sum3: " & sum3 & "  sum4: " & sum4 & "<br><br>")
					sums = {sum1, sum2, sum3, sum4}
					sumCha = getSumCha(sums)
					sumChaArry.Add(getSumCha(sums))
					myResultArry.Add(New MyResult With {.i = i, .j = j, .k = k, .l = l, .m = m, .sum1 = sum1, .sum2 = sum2, .sum3 = sum3, .sum4 = sum4, .sumCha = sumCha})
				Next
			Next
		Next


		Dim getMinCha As Integer = sumChaArry.Min()
		Dim final As MyResult = myResultArry.Where(Function(a) a.sumCha = getMinCha).FirstOrDefault()
		Response.Write("<br><br>here is minCha result:" & final.sumCha & " i: " & final.i & " j: " & final.j & " k: " & final.k & " l: " & final.l & "<br>")
		ToPrint(0, final.i, arry)
		ToPrint(final.j, final.k, arry)
		ToPrint(final.l, final.m, arry)
		ToPrint(final.n, arry.Length - 1, arry)
		Response.End()
	End Function

	Public Class MyResult
		Public Property i As Integer
		Public Property j As Integer
		Public Property k As Integer
		Public Property l As Integer
		Public Property m As Integer
		Public Property n As Integer
		Public Property o As Integer
		Public Property p As Integer

		Public Property sum1 As Integer
		Public Property sum2 As Integer
		Public Property sum3 As Integer
		Public Property sum4 As Integer
		Public Property sum5 As Integer
		Public Property sum6 As Integer
		Public Property sum7 As Integer
		Public Property sum8 As Integer

		Public Property sumCha As Integer
	End Class

	Public Function getSumCha(ByVal sums As Integer()) As Integer
		Dim sumCha As Integer = 0
		For i As Integer = 0 To sums.Length - 1
			sumCha += Math.Abs(sums(i) - divid)
		Next

		Return sumCha
	End Function

	Public Sub ToPrint(ByVal index1 As Integer, ByVal index2 As Integer, ByVal arry As Integer())
		For i As Integer = index1 To index2
			Response.Write(arry(i) & " ")
		Next

		Response.Write("-------------------<br>")
	End Sub

	Public Function getSum(ByVal index1 As Integer, ByVal index2 As Integer, ByVal arry As Integer()) As Integer
		Dim sum As Integer = 0
		For i As Integer = index1 To index2
			Response.Write(arry(i) & " ")
			sum += arry(i)
		Next

		Response.Write("-------------------<br>")
		Return sum
	End Function

This would throw the following result:

2 -------------------
3 -------------------
50 -------------------
50 45 45 -------------------
i:0 j: 1 k:1 l:2 m:2
Here is sum1: 2 sum2: 3 sum3: 50 sum4: 140

50 50 -------------------
45 45 -------------------
i:0 j: 1 k:1 l:2 m:3
Here is sum1: 2 sum2: 3 sum3: 100 sum4: 90

50 50 45 -------------------
45 -------------------
i:0 j: 1 k:1 l:2 m:4
Here is sum1: 2 sum2: 3 sum3: 145 sum4: 45

3 50 -------------------
50 -------------------
45 45 -------------------
i:0 j: 1 k:2 l:3 m:3
Here is sum1: 2 sum2: 53 sum3: 50 sum4: 90

50 45 -------------------
45 -------------------
i:0 j: 1 k:2 l:3 m:4
Here is sum1: 2 sum2: 53 sum3: 95 sum4: 45

3 50 50 -------------------
45 -------------------
45 -------------------
i:0 j: 1 k:3 l:4 m:4
Here is sum1: 2 sum2: 103 sum3: 45 sum4: 45

2 3 -------------------
50 -------------------
50 -------------------
45 45 -------------------
i:1 j: 2 k:2 l:3 m:3
Here is sum1: 5 sum2: 50 sum3: 50 sum4: 90

50 45 -------------------
45 -------------------
i:1 j: 2 k:2 l:3 m:4
Here is sum1: 5 sum2: 50 sum3: 95 sum4: 45

50 50 -------------------
45 -------------------
45 -------------------
i:1 j: 2 k:3 l:4 m:4
Here is sum1: 5 sum2: 100 sum3: 45 sum4: 45

2 3 50 -------------------
50 -------------------
45 -------------------
45 -------------------
i:2 j: 3 k:3 l:4 m:4
Here is sum1: 55 sum2: 50 sum3: 45 sum4: 45



here is minCha result:103 i: 2 j: 3 k: 3 l: 4
2 3 50 -------------------
50 -------------------
45 -------------------
2 3 50 50 45 45 -------------------

The orange highlighted part is the result I would need to show at the end (here is minCha result: (just below the orange highlighted text)) but for some reason it does not show the line with the last 45. It should be:

here is minCha result:103 i: 2 j: 3 k: 3 l: 4
2 3 50 -------------------
50 -------------------
45 -------------------
45 -------------------

2 3 50 50 45 45 -------------------

Thanks for the help,

Pascal

Answer 6

User2146470223 posted

Finally found the error:

I missed a tiny part further up the algorithm. See orange highlight:

Dim divid As Integer

	Public Function test() As String
		Dim arry As Integer() = {2, 3, 50, 50, 45, 45}
		Dim sumChaArry As List(Of Integer) = New List(Of Integer)()
		Dim myResultArry As List(Of MyResult) = New List(Of MyResult)()
		Dim i As Integer
		Dim j As Integer
		Dim k As Integer
		Dim l As Integer
		Dim m As Integer
		Dim n As Integer
		Dim o As Integer
		Dim p As Integer
		Dim q As Integer
		Dim r As Integer
		Dim s As Integer

		Dim sum1 As Integer
		Dim sum2 As Integer
		Dim sum3 As Integer
		Dim sum4 As Integer
		Dim sum5 As Integer
		Dim sum6 As Integer
		Dim sum7 As Integer
		Dim sum8 As Integer

		Dim x As Integer
		Dim cont As Integer
		cont = 4
		divid = 23

		Dim sums As Integer()
		Dim sumCha As Integer

		For i = 0 To arry.Length - cont
			sum1 = getSum(0, i, arry)
			j = i + 1
			For k = j To arry.Length - 3
				sum2 = getSum(i + 1, k, arry)
				l = k + 1
				For m = l To arry.Length - 2
					sum3 = getSum(k + 1, m, arry)
					n = m + 1
					sum4 = getSum(n, arry.Length - 1, arry)
					Response.Write("i:" & i & " j: " & j & " k:" & k & " l:" & l & " m:" & m)
					Response.Write("<br>Here is sum1: " & sum1 & "  sum2: " & sum2 & "  sum3: " & sum3 & "  sum4: " & sum4 & "<br><br>")
					sums = {sum1, sum2, sum3, sum4}
					sumCha = getSumCha(sums)
					sumChaArry.Add(getSumCha(sums))
					myResultArry.Add(New MyResult With {.i = i, .j = j, .k = k, .l = l, .m = m, .n = n, .sum1 = sum1, .sum2 = sum2, .sum3 = sum3, .sum4 = sum4, .sumCha = sumCha})
				Next
			Next
		Next


		Dim getMinCha As Integer = sumChaArry.Min()
		Dim final As MyResult = myResultArry.Where(Function(a) a.sumCha = getMinCha).FirstOrDefault()
		Response.Write("<br><br>here is minCha result:" & final.sumCha & " i: " & final.i & " j: " & final.j & " k: " & final.k & " l: " & final.l & "<br>")
		ToPrint(0, final.i, arry)
		ToPrint(final.j, final.k, arry)
		ToPrint(final.l, final.m, arry)
		ToPrint(final.n, arry.Length - 1, arry)
		Response.End()
	End Function

	Public Class MyResult
		Public Property i As Integer
		Public Property j As Integer
		Public Property k As Integer
		Public Property l As Integer
		Public Property m As Integer
		Public Property n As Integer
		Public Property o As Integer
		Public Property p As Integer

		Public Property sum1 As Integer
		Public Property sum2 As Integer
		Public Property sum3 As Integer
		Public Property sum4 As Integer
		Public Property sum5 As Integer
		Public Property sum6 As Integer
		Public Property sum7 As Integer
		Public Property sum8 As Integer

		Public Property sumCha As Integer
	End Class

	Public Function getSumCha(ByVal sums As Integer()) As Integer
		Dim sumCha As Integer = 0
		For i As Integer = 0 To sums.Length - 1
			sumCha += Math.Abs(sums(i) - divid)
		Next

		Return sumCha
	End Function

	Public Sub ToPrint(ByVal index1 As Integer, ByVal index2 As Integer, ByVal arry As Integer())
		For i As Integer = index1 To index2
			Response.Write(arry(i) & " ")
		Next

		Response.Write("-------------------<br>")
	End Sub

	Public Function getSum(ByVal index1 As Integer, ByVal index2 As Integer, ByVal arry As Integer()) As Integer
		Dim sum As Integer = 0
		For i As Integer = index1 To index2
			Response.Write(arry(i) & " ")
			sum += arry(i)
		Next

		Response.Write("-------------------<br>")
		Return sum
	End Function

Now everything works.

This part of the answer is for 4 containers in VB. Cathy's one is valid for 3 containers in c#. You best use Telerik's converter to switch the function for the respective language.

From these 2 answers it'll be easier to change the algorithm to 5 or more containers. For me, right now, a function for n containers without setting a case or else if condition for each number of containers seems impossible. If anyone can come up with one, I would be glad to see the final function. ;)

Cheers,

Pascal