Returns all subsequences of an array, like only sequential values in Java
The problem I'm trying to solve in Java requires dividing the input array into all valid subsequences, where the valid subsequence only contains consecutive values. For example, I would like {A, E, D} to return {A, E, D}, {A, E}, {A}, {E, D}, {D}, {E}
This differs from this question in that (for the example above)
1) I have a "sequential value" rule that means {A, D} is NOT allowed and
2) I cannot depend on Python syntax in the answers here.
My question in particular is how to implement the "sequential value" rule for the more general subsequence problem.
So far I have come up with one algorithm for example {1,2,3}:
1. Copy {1,2,3} and store in arr
2. Append {1,2,3} to the solutions, separate 3
3. Append {1 , 2} to the solutions, separate 2
4. Append {1} to the solutions. Cut 1 out of arr
5. Add {2,3} to solutions flake 3
6. Append {2} to solutions. Cut 2 from arr
7. Add {3} to solutions
You can just use two nested loops:
// Setup
char[] arr = { 'A', 'E', 'D' };
// Generate all subsequences
List<char[]> result = new ArrayList<>();
for (int start = 0; start < arr.length; start++) {
for (int end = start + 1; end <= arr.length; end++) {
result.add(Arrays.copyOfRange(arr, start, end));
}
}
// Print result
result.forEach(a -> System.out.println(Arrays.toString(a)));
Output:
[A] [A, E] [A, E, D] [E] [E, D] [D]
source to share