Grouping a squence is subsequences with a given sum with lexicographical priority

Question

I am looking for a way to search for a subsequence in a given sequence that sums up to a given number (sum, here 4) with a lexicographical priority.

Take for instance the following example:

1,2,2,4,1,1

Different subsequences can sum up to 4. For instance 1,2,1, 2,2 2,1,1. In case multiple of such sequences exists, the lexicographical first of the corresponding index-array should be returned: so if it is possible to find such sequence with the first element, one has to returned that one, if not, aim for the second and so one (both iterative (take the next one), and recursively (after selecting the first, the next but first should be closest to the head of the sequence as well).

So for this example, we select 1,2,1. Now 2,4,1 is left. If we repeat this problem we cannot make a match with 2: 2,4 is greater than 4 and 2,1 is less than 4. Thus we select 4. Finally we have to select 2 and 1.

A practical application of this concept is a queue of a roller coaster. You need 4 people for a ride, but some people are in groups with their friends and would like to all get on the same ride together.

In this example 1 is a single person at the front of the line, 2 is a group of 2 friends behind him. Now we need a total of 4 people for this ride and we already have 3, so we cut the line (2 and 4) and take the first single person, which gives us 4 people total.

Answer 1

If I understand the problem correctly, what you basically try to do is grouping the numbers such that the sum is 4 and you give priority to adding numbers in the queue first.

You can do this using a dynamic programming approach. I'm here using a int[] and an int as sum, but the problem can be generalized to work with most datastructures.

First you must define a comparator that compares lists of indices for instance a lexicographical one:

public class LexComp<T extends Comparable<T>> implements Comparator<List<T>> {

    @Override
    public int compare (List<T> la, List<T> lb) {
        Iterator<T> ita = la.iterator();
        Iterator<T> itb = lb.iterator();
        while(ita.hasNext() && itb.hasNext()) {
            T ea = ita.next();
            T eb = itb.next();
            int cr = ea.compareTo(eb);
            if(cr != 0x00) {
                return cr;
            }
        }
        if(itb.hasNext()) {
            return 1;
        } else if(ita.hasNext()) {
            return -1;
        }
        return 0;
    }

}

Next you can use the following method:

public ArrayList<Integer> groupSum (int[] values, int sum) {
    ArrayList[] memory = new ArrayList[sum+1];
    memory[0] = new ArrayList<Integer>();
    LexComp<Integer> lc = new LexComp<Integer>();
    int index = 0;
    for(int val : values) {
        for(int i = sum-val; i >= 0 ; i--) {
            if(memory[i] != null) {
                ArrayList<Integer> tmp = (ArrayList<Integer>) memory[i].clone();
                tmp.add(index);
                if(memory[i+val] == null || lc.compare(tmp,(ArrayList<Integer>) memory[i+val]) < 0) {
                    memory[i+val] = tmp;
                }
            }
        }
        index++;
    }
    return memory[sum];
}

This method returns an ArrayList<Integer> of indices whose corresponding elements will sum up to sum and null if no such group can be created. It will give priority to some groups according to the LexComp comparator.

For your given input:

groupSum(new int[] {1,2,2,4,1,1},4);
groupSum(new int[] {1,2,3,2,2,2},4);
groupSum(new int[] {1,2,2,3},4);
groupSum(new int[] {1,2,2,3,1},4);

It results in:

[0, 1, 4]
[0, 2]
[0, 3]
[0, 1, 4]

So you should pick the first, second and fifth element which indeed sum up to 4. You then will have to remove these items out of the array yourself and rerun the process. In case no such sum can be constructed, or there are not enough elements to sum up to 4 - as said before - the algorithm will return null. In that case you have to invent a fallback mechanism. Perhaps returning the group the differs the least from sum.

Background

This is a dynamic programming approach. You generate a memory which stores - for each sum - the thus far best found solution. Initially we haven't seen any values so all items contain null except memory[0] which contains an empty arraylist (because the sum of zero elements is 0). So the memory looks like:

Mem
4 -> null
3 -> null
2 -> null
1 -> null
0 -> []

Now the algorithm iterates over the values. The first value we encounter for the example case is a 1. Now we look for lists already defined and the only one is memory[0] we can upgrade that list into a list [0] (the arrays store indices) whose sum results in 1. Since at that moment the value for that list is null there is no alternative, thus we add this list to to memory[1]:

Mem
4 -> null
3 -> null
2 -> null
1 -> [0]
0 -> []

The next item is 2: we can upgrade two lists [] -> [1] and [0] -> [1] these will results in lists with sums 2 and 3 respectively, so we store them at these indices of the memory:

Mem
4 -> null
3 -> [0,1]
2 -> [1]
1 -> [0]
0 -> []

The next item is again a 2. Now we can upgrade 4 lists: [] -> [2], [0] -> [0,2], [1] -> [1,2] and [0,1] -> [0,1,2]. A first problem is that the sum of [0,1,2] is 5 which is higher than sum. That's not interesting, so we drop that one. The problem is however, that some of the places contain already lists:

Mem
4 -> null
3 -> [0,1] <> [0,2]
2 -> [1] <> [2]
1 -> [0]
0 -> []

For the conflicting lists, we need to look for a resolution. In that case the comparator - in this case the LexComp resolves the errors. Since we do this lexicographically, [0,1] wins from [0,2] and [1] from [2]. After resolution the lists looks like:

Mem
4 -> [3]
3 -> [0,1]
2 -> [1]
1 -> [0]
0 -> []

The next element is a 4. The only list we can upgrade such that the sum is still less than or equal to sum is [] -> [3]

Mem
4 -> [3]
3 -> [0,1]
2 -> [1]
1 -> [0]
0 -> []

The next element is 1. We can upgrade all lists except the one 4 -> [3] (otherwise the sum would be larger than 4). But again this results in a lot of conflicts:

Mem
4 -> [3] <> [0,1,4]
3 -> [0,1] <> [1,4]
2 -> [1] <> [0,4]
1 -> [0] <> [4]
0 -> []

Now if we run the lexicographically comparator, it will sometimes accept new lists and sometimes the old lists. After resolution, the memory looks like:

Mem
4 -> [0,1,4]
3 -> [0,1]
2 -> [0,4]
1 -> [0]
0 -> []

Now our current best solution to generate a group that sums up to four has changed from [3] to [0,1,4]. Finally the last element 1 won't change much to the game:

Mem
4 -> [0,1,4] <> [0,1,5]
3 -> [0,1] <> [0,4,5]
2 -> [0,4] <> [0,5]
1 -> [0] <> [5]
0 -> []

Which after resolution reads:

Mem
4 -> [0,1,4]
3 -> [0,1]
2 -> [0,4]
1 -> [0]
0 -> []

Now we have considered all elements and the best solution to generate 4 is memory[4] or [0,1,4].

Different order

This approach can be generalized in the sense that providing a different Comparator on List<T> (here the LexComp<T>) will give priority to another index array. The comparator should always fulfill at least the transitivity constraint: if x is less than y and y is less than z: x must be less than z. Furthermore the list of indices will always increase. An index array of [4,1,0] is thus impossible.

Answer 2

The correct answer to this question depends a lot on how you define your priorities.

Should we always pick the first group in the line if possible or is the optimal solution to have as many people from the front of the queue?

I.e. given

1, 2, 2, 3, 3, 4, 2, 2, 3, 1

is the optimal solution

1, 2, 1

or

1, 3

To get you started, here's a recursive solution that does the first:

private static List<Integer> getSumIndices(int sum, List<Integer> queue) {
    return getSumIndices(sum, new ArrayList<>(queue), 0);
}

private static List<Integer> getSumIndices(int sum, List<Integer> queue, int offset) {
    System.out.printf("Looking for sum %s in values of %s with offset %s%n", sum, queue, offset);
    if(sum == 0) {
        //Base case
        return new ArrayList<>();
    }
    for(int i = 0; i < queue.size(); i++) {
        int value = queue.get(i);
        // Can we actually use this group
        if(value <= sum) {
            try {
                // See if we can find the remainder if we use this group
                ArrayList<Integer> list = new ArrayList<>();
                list.add(i + offset);
                list.addAll(getSumIndices(sum - value, queue.subList(i + 1, queue.size()), offset + i + 1));
                return list;
            } catch(IllegalArgumentException e) {
                // We couldn 't, continue looking
            }
        }
    }
    // We could not construct the sum using the values in the queue
    System.out.printf("Failed to construct sum %s from values in %s%n", sum, queue);
    throw new IllegalArgumentException(String.format("Could not construct sum %s from values in %s%n", sum, queue));
}

Results:

q=[1, 2, 2, 3, 3, 4, 2, 2, 3, 1]
Looking for sum 4 in values of [1, 2, 2, 3, 3, 4, 2, 2, 3, 1] with offset 0
Looking for sum 3 in values of [2, 2, 3, 3, 4, 2, 2, 3, 1] with offset 1
Looking for sum 1 in values of [2, 3, 3, 4, 2, 2, 3, 1] with offset 2
Looking for sum 0 in values of [] with offset 10
Index: Group Size
0: 1
1: 2
9: 1
Remaining q=[2, 3, 3, 4, 2, 2, 3]

q=[1, 2, 3, 2, 3, 4, 2, 2, 3, 2]
Looking for sum 4 in values of [1, 2, 3, 2, 3, 4, 2, 2, 3, 2] with offset 0
Looking for sum 3 in values of [2, 3, 2, 3, 4, 2, 2, 3, 2] with offset 1
Looking for sum 1 in values of [3, 2, 3, 4, 2, 2, 3, 2] with offset 2
Failed to construct sum 1 from values in [3, 2, 3, 4, 2, 2, 3, 2]
Looking for sum 0 in values of [2, 3, 4, 2, 2, 3, 2] with offset 3
Index: Group Size
0: 1
2: 3
Remaining q=[2, 2, 3, 4, 2, 2, 3, 2]

q=[1, 2, 2]
Looking for sum 4 in values of [1, 2, 2] with offset 0
Looking for sum 3 in values of [2, 2] with offset 1
Looking for sum 1 in values of [2] with offset 2
Failed to construct sum 1 from values in [2]
Looking for sum 1 in values of [] with offset 3
Failed to construct sum 1 from values in []
Failed to construct sum 3 from values in [2, 2]
Looking for sum 2 in values of [2] with offset 2
Looking for sum 0 in values of [] with offset 3
Index: Group Size
1: 2
2: 2
Remaining q=[1]

q=[2, 3, 3]
Looking for sum 4 in values of [2, 3, 3] with offset 0
Looking for sum 2 in values of [3, 3] with offset 1
Failed to construct sum 2 from values in [3, 3]
Looking for sum 1 in values of [3] with offset 2
Failed to construct sum 1 from values in [3]
Looking for sum 1 in values of [] with offset 3
Failed to construct sum 1 from values in []
Failed to construct sum 4 from values in [2, 3, 3]
Could not construct sum 4 from values in [2, 3, 3]

Answer 3

You can loop through the list and add in order until it is larger than the value you are looking for.

Code:

public static int addListValues(int[] list, int num){//Returns number which can not be added by anything else in the list to be <= num.
    boolean b[] = new boolean[list.length];//List of numbers already taken care of.  True for not, false for cleared.
    for(int i = 0; i < b.length; i++){
        b[i] = true;
    }
    int count = 0;//Amount of numbers in int[] list which have been added to equal less than or equal to num.
    int total = 0;

    while(true){//loops until values left can not be added to equal or be less than num.
        int check = 0;
        for(int i = 0; i < list.length; i++){//Loops through list.
            if(b[i]){//If the number has not been added already.
                System.out.println("CHECKING: " + i);
                if(total + list[i] > num){//Adds to check if the number is greater than num.
                    check++;
                }
                if(total + list[i] <= num){//Adds numbers together to equal num or less than num.
                    System.out.println("TEST: " + list[i] + " TOTAL: " + total);
                    if(total + list[i] != num){
                        boolean contains = false;
                        int index = 0;
                        for(int o = 0; o < list.length; o++){
                            if(list[o] == num - total && b[o] && o != i){
                                contains = true;
                                index = o;
                                break;
                            }
                        }
                        if(contains){
                            System.out.println("1: " + index + ",  " + list[index]);
                            b[index] = false;
                            count++;
                            total = 0;
                        }else{
                            System.out.println("2");
                            b[i] = false;
                            count++;
                            total+= list[i];
                        }
                    }else{
                        System.out.println("3");
                        b[i] = false;
                        count++;
                        total = 0;
                    }
                }else if(check == list.length - count){//Check if "check" is equal to the amount left over.  In other words, if the numbers left are higher than the number you are looking for.
                    System.out.println("FINAL: 3");
                    int t = 0;
                    for(int j = 0; j < list.length; j++){
                        if(b[j]){
                            t += list[j];
                        }
                    }
                    return t;//More than one number is left and is higher than num. Returns numbers left added together
                }else if(count == list.length-1){
                    System.out.println("FINAL: 2");
                    return list[i];//returns list[i] if it is the only number left over.
                }
            }else if(count >= list.length){
                System.out.println("FINAL: 1");
                return total;//Returns total if there is nothing left over. The total may be anything less than the "num".
            }
        }
    }
}

I have tested this method with multiple sets of numbers and it works. I was unsure what to return if more than one value were left over and were higher than 4, so I added the left over values and returned this.

This code does not require any imports.