list of processes, resources, requests and releases:
A req R
A req S
A rel R
A rel S
B req S
B req R
B rel S
B rel R
Ordering withing a process can't be rearranged (A must always request R before it can request S in the example above), however orderings across processes can be rearranged (B can request S and R before A requests R)
package Test;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
public class SortStr {
public static void main(String[] args) {
Set<String> s = new HashSet<String>();
List<String> A = List.of("A req R", "A req S", "A rel R", "A rel S");
List<String> B = List.of("B req S", "B req R", "B rel S", "B rel R");
s.addAll(A);
s.addAll(B);
/* List<String> A = List.of("A");
List<String> B = List.of("1");
List<String> C = List.of("X");
s.addAll(A);
s.addAll(B);
s.addAll(C); */
Map<Integer, List<String>> result = new HashMap<>();
permutations(s, new Stack<String>(), s.size(), result);
result.forEach((key, value) ->
System.out.println("ORDER " + key + " : " + value)
);
}
public static void permutations(Set<String> items, Stack<String> permutation, int size,
Map<Integer, List<String>> result) {
/* permutation stack has become equal to size that we require */
if (permutation.size() == size) {
/* print the permutation */
// System.out.println(Arrays.toString(permutation.toArray(new String[0])));
/* add the permutation in the result */
Integer key = (result.size() > 0) ? result.size() + 1 : 0;
result.put(key, Arrays.asList(permutation.toArray(new String[0])));
}
/* items available for permutation */
String[] availableItems = items.toArray(new String[0]);
for (String i : availableItems) {
/* add current item */
permutation.push(i);
/* remove item from available item set */
items.remove(i);
/* pass it on for next permutation */
permutations(items, permutation, size, result);
/* pop and put the removed item back */
items.add(permutation.pop());
}
}
}
Above Program generate all the possible sorting permutations. but my conditional criteria is a process can't be rearranged (A must always request R before it can request S in the example above), however orderings across processes can be rearranged (B can request S and R before A requests R)
so, how can I sorting all possible orderings of resource request/releases?
Output Result what I want:-
ORDER 1: A req R, A req S, A rel R, A rel S, B req S, B req R, B rel S, B rel R
ORDER 2: A req R, A req S, A rel R, B req S, A rel S, B req R, B rel S, B rel R
...
ORDER X: A req R, B req S, A req S, B req R ...
Test Case Inputs :-
Case 1 :-
A req R A req S A rel R A rel S B req S B req T B rel S B rel T C req T
C req R C rel T C rel R
Case 2 :-
A req R A req S A rel R A rel S B req T B rel T C req S C rel S D req U
D req S D req T D rel U D rel S D rel T E req T E req V E rel T E rel V
F req W F req S F rel W F rel S G req V G req U G rel V G rel U
I tried a lot but I can't So, Please guide me to achieve this permutations generation.
Thank you.
I think you should start by organizing your data a bit better, then you can use the permutation algorithm.
List<String> processes = List.of("A req R", "A req S", "A rel R", "A rel S", "B req S", "B req R", "B rel S", "B rel R");
First
Map<String, List<String>> grouped = processes.stream().collect(Collectors.groupingBy( s -> s.substring(0, 1) ) );
Now you have a collection of a list of processes that you're not going to re-arrange.
String order = processes.stream().map( s -> s.substring(0, 1) ).collect( Collectors.joining() );
Now order is a string of the process names, "AAAABBBB". You can create all the permutations of this string. Your algorithm should work, it might produce duplicates so either store the results in a Set so it only keeps unique values.
This version below should only generate unique permutations.
List<String> permutations = new HashSet<>();
void permutations(String s){
permutation("", String str)
}
void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) permutations.add(prefix);
else {
Set<Character> checked = new HashSet<>();
for (int i = 0; i < n; i++){
Character c = str.charAt(i);
if( checked.contains(c) ) continue;
permutation(prefix + c, str.substring(0, i) + str.substring(i+1, n));
checked.add(c);
}
}
}
The last step is to get the processes back.
String o = ...; //one entry taken from the list of all permutations.
Map<Character, Iterator<String>> iterators = grouped.entrySet().stream().collect(
Collectors.toMap(
e->e.getKey().charAt(0),
e-> e.getValue().iterator()
)
);
for( char c: o.toCharArray() ){
System.out.print( iterators.get(c).next() + ", ");
}
System.out.println();
That gives me.
A req R, A req S, A rel R, A rel S, B req S, B req R, B rel S, B rel R,
A req R, A req S, A rel R, B req S, A rel S, B req R, B rel S, B rel R,
A req R, A req S, A rel R, B req S, B req R, A rel S, B rel S, B rel R,
...
B req S, B req R, B rel S, A req R, B rel R, A req S, A rel R, A rel S,
B req S, B req R, B rel S, B rel R, A req R, A req S, A rel R, A rel S,