Algorithms and Data Structures : Part 4.3 String : Substring : Subset : Permutation : Combination

For the set {1,2,3,4}  if we have to select 3 elements , we can proceed as below


1)   Select the left most 3 elements . 1,2,3
      Then move the right most elements till we reach SET end  1,2,4
      Once the right most element is reached, then move the second element from right 1,3,4
      2,3,4

  Select 2 elements
     1,2
         1,3
             1,4
     2,3
          2,4
     3,4


Now as we can see in   nCr , if r value changes then number of FOR loop will also changes, So in this situation we have to use RECURSION.

2) Now in RECURSION we use SYSTEM STACK, but we can use our STACK using DFS

1-->2-->3-->4

insert 1 in stack , then insert 2 without poping 1  ..Now if  r value is 2 ....print all elements in stack 1,2

now since R is reached , pop stack ...so we poped 2 , now from 2 we can go to 3...so insert 3....again r value is reached so print 1,3

similarly  1,4 will be printed


Now once SET end is reached pop two elements from stack  , and insert next element  and repeat process.

2,3  2,4

then 3,4

For    say 5 elements  1,2,3,4,5    we have to get all 3 elements ...the stack method will be

1,2,3     r value is reached , pop only 1 element and insert next element
1,2,4
1,2,5
        // here SET last element is reached, pop out that and also the next element
1
       // Now insert the next element
1,3  // now keep inserting till we reach r value
1,3,4
1,3,5
1
1,4
1,4,5
1
1,5  SET end reached, pop top and also next element
empty stack
2
2,3    keep inserting till R value reached
2,3,4
2,3,5
2,4,5
2,5   pop one more
3,4,5
3,5 pop one more


Below is the code snapshot.


Here obj1  is STACK object , whose SIZE is R.

1. while(obj1.empty)
2. {
3. if(n==N && obj1.push(n)==-1 ) obj1.print();
4. if(n==N) { obj1.pop();n=obj1.pop(); }
5. else if(obj1.push(n)==-1)
6. {
7. obj1.print();
8. n=obj1.pop();
9.  
10. }
11. ++n;