Sequentially distribute data from a list to arrays of different weight

Question

How to, Sequentially distribute data from a list to arrays (or some other structure) of fixed size/weight.

For example, lets say I have a list of 10 elements. I want to sequentially distribute the elements to 3 arrays A, B, and C. The arrays are given a weight lets say A=3, B=5, and C=2.

The element would be distributed in the following fashion.

A - list[0]  list[3] list[6]
B - list[1]  list[4] list[7] list[8] list[9]
C - list[2]  list[5] 

If the size of the list was 13, then after the above distribution, it would start again after the cycle completes

A - list[0]  list[3] list[6] list[10]
B - list[1]  list[4] list[7] list[8] list[9] list[11]
C - list[2]  list[5] list[12]

The size of the list is dynamic, so in the above example, the list size would be 3, 4, or 100, etc. And the number of arrays (or structure) and weight of the arrays are available in runtime only.

Is there a good way to solve it?

Answer 1

As I understand the problem, if there are N different weights (W1,W2..etc) and M is their sum, you want the cycle to be repeated for every M elements. There would be N different arrays, and each cycle puts the weight number of elements in each array like first one takes W1 etc.

One solution is to just read elements, keeping a counter if counter is < W1 put element in first array, if counter is between W1 and W2 put the element in second array etc Reset the counter every M elements. Increment the counter after element is read. When you get the weights at run time, you create a LinkedList list with the same size as number of weights and add Those many arrays with the corresponding sizes to the LinkedList. The weights could be kept in array.same Does it help ?

Answer 2

I would use ArrayLists with assosiated parts of elements, that should be added in them.

For example: ArrayListA - with assosiated value of 3 ArrayListB - with assosiated value of (3+5)= 8 ArrayListC - with assosiated value of (8+2)= 10

and for every item from the list do: 1. find random number from 0 to 10 2. add item to array with specified value, liek e.g: if rondom number i 9, then add to ArrayListC if rondom number i 2, then add to ArrayListA if rondom number i 8, then add to ArrayListB

and if array is realy needed, then conver it to array.

and these arraylists you can keep in same structure, so you can have so many of them, as You want to.

Answer 3

You should better define the problem. The term 'weight' is not deterministic enough and usually simply signifies a factor that is used is some procedure or calculation.

For example, if you want to sequentially assign elements from a queue to n-buckets, aiming for certain distribution of data in the buckets then the problem becomes clearer.

Then you might simply take next element from the queue and roll the dice in such a way that it will determine the bucket with given distribution (using example with A,B,C->3,5,2 distribution, roll the dice with 10 sides and if you get 1,2 or 3 put the element in A, if it is 4,5,6,7,8 put it in B and if it is 9 or 10 put it in C).

Still, realize that I did not fully define the problem, when I say aim for a distribution, there is no guarantee when such distribution will be reached, nor how much you might be off from it along the way (especially early on in the process).

From your example it seems that you want the distribution to be as close as possible to distribution you are aiming for for each processed element.

In that case, a naive and straightforward effort would be to add the element to the bucket that will make a new distribution closest to the aimed distribution.

Answer 4

Not sure if this is exactly what you want because your example had the tenth value going back to the first array when I suspect it should have gone to the third. Also it probably can be optimized somewhat...

package test.stack.overflow;

import java.util.ArrayList;

public class TestWeights
{
    public static void main(String[] args)
    {
        int[] w = {3, 5, 2};
        ArrayList<ArrayList<Integer>> v = new ArrayList<ArrayList<Integer>>(w.length);

        int s = 0, i = 0;
        for (int x = 0 ; x < w.length; x++)
        {
            v.add(new ArrayList<Integer>());
            s += w[x];
        }

        for (int nv = 0; nv < 30; nv++)
        {
            int r = 1 + nv / s;

            while (true)
            {
                if (v.get(i).size() < w[i] * r)
                {
                    v.get(i).add(nv);
                    i = ++i % w.length;
                    break;
                }
                else
                    i = ++i % w.length;
            }
        }

        for(ArrayList<Integer> a : v)
        {
            for(Integer ai : a)
                System.out.print(ai + " ");

            System.out.println();
        }
    }
}

Answer 5

The easiest way to sequentially distribute element across different different weighted array (fixed size) array is to auto pollulate the stacks using array size. And put the stack in a circular array. sequentially get the next stack and pop the element of the stack. If stack has not more element remove it from the circular array until the distribution list is empty. if distribution list size is not predefined, or if circular array becomes empty, reset the circular array, and start from the beginning.

A=3, B=5, and C=1.

    Stack<String> sA= new Stack<String>();
    sA.push("A");sA.push("A");sA.push("A");

    Stack<String> sB = new Stack<String>();
    sB .push("B");sB .push("B");sB .push("B");sB .push("B");sB .push("B");


    Stack<String> sC = new Stack<String>();
    sC.push("C");

//add stack to array CircularLinkedList list = new CircularLinkedList(); list.add(s1); list.add(s2); list.add(s3);

    CircularListIterator<Stack> iterator = list.iterator();
    Stack<String> s;

//iterate till the stack is empty, reset the stack if distribution list is remaining // or if the lead comes from another source for example website, simply get the next stack

    while (iterator.hasNext()){
        s = iterator.next();
        if (s.empty()){
            iterator.remove();
            continue;
        } 
        System.out.println(s.pop());            
    }

Here is an example of circular list //http://www.cs.princeton.edu/algs4/13stacks/CircularLinkedList.java.html