Java – grouping sequences is a subsequence of a given sum with dictionary priority
I'm looking for a way to search for subsequences in a given sequence that sum up to a given number (sum, here 4) and have lexicographic priority
Take the following example:
1,2,4,1,1
The sum of different subsequences can reach 4 For example, 1,2,2,1 If there are multiple such sequences, the first dictionary of the corresponding index array should be returned: if it is possible to find the sequence of the first element, the sequence must be returned, if not, the second element So one (iteration (next) and recursion (after selecting the first, the next, but the first should also be closest to the head of the sequence)
Therefore, for this example, we choose 1,1 Now there are 2,1 left If we repeat this problem, we cannot match 2: 2,4 is greater than 4, and 1 is less than 4 So we choose 4 Finally, we must choose 2 and 1
The practical application of this concept is the roller coaster queue You need four people to ride, but some people are with their friends and want everyone to ride together
In this example, 1 is a person in front of the line and 2 is a group of 2 friends behind him Now we need a total of 4 people to complete the trip. We already have 3 people, so we cut off the line (2 and 4) and chose the first single person, a total of 4 people
Solution
If I understand this problem correctly, all you basically have to do is group the numbers so that the sum is 4, and give priority to adding numbers to the queue
You can do this using dynamic programming I use int [] and int as the sum here, but the problem can be extended to most data structures
First, you must define a comparator that compares index lists, such as dictionary index lists:
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 methods:
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];
}
The corresponding elements of the ArrayList < integer > index returned by this method will sum up. If such a group cannot be created, it will be null According to the lexcomp comparator, it will give priority to certain groups
For your input:
groupSum(new int[] {1,1},4);
groupSum(new int[] {1,3,2},3},4);
It leads to:
[0,4] [0,2] [0,3] [0,4]
Therefore, you should select the first, second, and fifth elements, and the sum of these elements is up to 4 You must then remove these items from the array yourself and rerun the process If such a sum cannot be constructed, or there are not enough elements with a sum of 4 - as mentioned earlier - the algorithm returns null In this case, you must invent a fallback mechanism Perhaps the group returned is the least different from the sum
background
This is a dynamic programming method You generate a memory - store - for each sum - store the best solution so far Initially, we didn't see any value, so all items contain null, except memory [0] containing empty ArrayList (because the sum of zero elements is 0) So memory looks like:
Mem 4 -> null 3 -> null 2 -> null 1 -> null 0 -> []
Now the algorithm iterates over the values The first value of the example case we encountered is 1 Now let's find the defined list. The only one is memory [0]. We can upgrade the list to list [0] (array storage index), and the total result is 1 Since the value of this list is null at this time, it cannot be replaced, so we add this list 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], which will result in lists of and 2 and 3 respectively, so we store them in these indexes in memory:
Mem 4 -> null 3 -> [0,1] 2 -> [1] 1 -> [0] 0 -> []
The next project is again 2 Now we can upgrade 4 lists: [] – > [2], [0] – > [0,2], [1] – > [1,2] and [0,1] – > [0,2] The first problem is that the sum of [0,2] is 5, which is higher than sum It's not very interesting, so we give up that But the problem is that some places already contain what is listed:
Mem 4 -> null 3 -> [0,1] <> [0,2] 2 -> [1] <> [2] 1 -> [0] 0 -> []
For the conflict list, we need to find a solution In this case, the comparator – in this case, lexcomp resolves the error Because we do this in dictionary order, [0,1] wins from [0,2] and [1] in [2] When resolved, the list looks like:
Mem 4 -> [3] 3 -> [0,1] 2 -> [1] 1 -> [0] 0 -> []
The next element is 4 The only list we can upgrade, that is, 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 one 4 – > [3] (otherwise the sum will be greater than 4) But this has led to many conflicts:
Mem 4 -> [3] <> [0,4] 3 -> [0,1] <> [1,4] 2 -> [1] <> [0,4] 1 -> [0] <> [4] 0 -> []
Now, if we run the dictionary comparator, it sometimes accepts new lists and sometimes old lists After parsing, the memory looks like:
Mem 4 -> [0,1] 2 -> [0,4] 1 -> [0] 0 -> []
Now, our current best solution for generating groups with a total of up to 4 has been changed from [3] to [0,4] Finally, the last element 1 will not change the game much:
Mem 4 -> [0,4] <> [0,5] 3 -> [0,5] 2 -> [0,5] 1 -> [0] <> [5] 0 -> []
The solved contents are as follows:
Mem 4 -> [0,4] 1 -> [0] 0 -> []
Now that we have considered all the elements, the best solution for generating 4 is memory [4] or [0,4]
Different order
This method can be summarized as providing different comparators on the list < T > (here lexcomp < T >) will give priority to another index array The comparator should always meet at least the transitivity constraint: if x is less than y and Y is less than Z: X must be less than Z. in addition, the index list will always increase Therefore, the index array of [4,0] is impossible