Permutations Program With Backtracking

Backtracking Programming - Check with all feasibles. Dynamic Programming we will choose optimal chosen.

These days in coding exams very popular. Even though you are talented, it will help sharp your skills and ask companies more salary.

If we take the (ABC) --> How many all possible ways to combination, This problem belongs to backtracking.

Backtracking with DFS approach I had taken. DFS (Stack) - means first we will one branch we will complete that branch means here (ABC,0,0) - We will complete all possibilites then we will choose (BAC,0,1) like this way.

For this type of try to understand conceptual logic, it's very tricky here combination of for loop with recursion. for loop --> sequence, recursion --> stack (DFS)

Forumula:
Deriving the recursive with for loop forumula, I am attaching image.

p(ABC,0,2) --> for loop (   (ABC,0,0)  (BAC,0,1)    (CAB,0,2) )
            p(ABC,1,2) --> for ( (swapped str, 1,1)  (swapped str,1,2)) like this

Mixing of recursion with for loop

package optumtest.permutation;

public class PermutationTest {

public static void main(String[] args) {
String str = "ABC";
        int n = str.length();
        PermutationTest permutation = new PermutationTest();
        permutation.permute(str, 0, n-1);
}

int ram = 0;


private void permute(String str, int start, int end) {
System.out.println("("+str+","+start+","+end+")");
if (start == end) {
System.out.println(str);
} else {
for (int i = start; i <= end; i++) {
  str = swap(str, start, i);
permute(str, start + 1, end);
str = swap(str, start, i);
}
}
}


public String swap(String a, int start, int end) {
char temp;
char[] charArray = a.toCharArray();
temp = charArray[start];
charArray[start] = charArray[end];
charArray[end] = temp;
return String.valueOf(charArray);
}

}

JAVA Streams

Java streams main intension performance improvement.
State of stream - Sorted, distinct
ArrayList : characteristics
public int characteristics()
{ return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED; }

HashSet : characteristics
public int characteristics() {
return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) | Spliterator.DISTINCT; }

Stream - Characteristic
ORDERED ordermatters
DISTINCT No duplication possible
SORTED Sorted
SIZED The size is known
NONNULL No nullvalues
IMMUTABLE Immutable
CONCURRENT Parallelismis possible
SUBSIZED The size is known

employee.stream()
                .distinct() // returns a stream = intermediate method
                .sorted()   // the same as distinct()
                .forEach(System.out::println);

How streams will improve performance ?

distinct() and sorted() intermediate methods means until terminal methods forEach invoke no computation will not perfomed ? what it means ?
if stream call distinct() then it will update the state of distinct either 0 or 1.
if stream call sorted() then it will update the state of sorted either 0 or 1
Now terminal method forEach
1) Checks the state of streams in our case
if(distinct==1) { it will perform the distinct operation }
if(sorted == 1) { it will perform the sorted operation }
after that stream it will process each element in stream.

But where you got performance improvement here ?

// HashSet
HashSet<Employee> employee= ... ;
employee.stream()
          .distinct() // no processing is triggered
          .sorted()   // quicksort is triggered
          .forEach (System.out::println);

HashSet stream, HashSet will not allowed duplicated means in our distinct operation not requires.
distinct = 0
sorted = 1
Now forEach it will skip the distinct and perform the sorted so here little bit performance improved.


// SortedSet
SortedSet<Employee> employee= ... ;
employee.stream()
           .distinct() // no processing is triggered
           .sorted()   // no quicksort is triggered
           .forEach(System.out::println);
SortedSet stream - means SortedSet not allows duplicates and it's already sorted
hence
distinct - 0
sorted - 0
hence forEach it will skip the distinct and sorted operations.


We know stateful and stateless object ? What is Stateful and Stateless operation ?

I will explain
// call parallel on an existing stream
List<Person> people = ... ;
 people.stream()
            .parallel()
            .filter(person -> person.getAge() > 20)
            .sorted()
            .forEach(System.out::println);

Here In the filter operation/method, we don't need to remember any state.

// call parallel on an existing stream
List<Person> people = ... ;
people.stream()
          .parallel()
          .skip(2)
          .limit(5)
          .forEach(System.out::println);

We need to maintain one counter variable, remove 2, add 5 means we need to atomicLong instance variable in class level. This instance variable updated by multiple threads.

Here we are depend on counter variable state, this example stateful example.

AWS Cloud

Now I am started to publish articles on AWS Cloud related.