Sandrino's WEBSITE

   ABOUT  BLOG  


Finding possible permutations of an array

As every person once in life needs to find all possible permutations of an array, this day I had this moment. I saw it in a YT video as an interview question and i thought its a cool question and tried to solve it. And it took longer than expected but at the end we have a working solution. In this article I will just share the code and try to go over the first several steps explaining in text. With recursion I always have to write it down on a paper otherwise my brain will not get it.

The solution:

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>

// Example of DFS ( Depth first search )
void permuteMe( std::vector<std::vector<int32_t> >& ans, std::vector<int32_t>& sol, std::vector<int32_t>& arr )
{
   std::cout << ">>>> Entering permute\n";
   std::cout << "[ ";
   for( auto n : sol )
   {
      std::cout << n << " ";
   }
   std::cout << "]\n";

   if( sol.size() == arr.size() )
   {
      ans.push_back( sol );
      std::cout << ">>>> Exiting permute size reached\n";
      return;
   }

   for( auto num : arr )
   {
      std::cout << "Next Number: " << num << "\n";
      // The next number is already part of the partial solution
      if( std::find( sol.begin(), sol.end(), num ) != sol.end() )
      {
         continue;
      }

      sol.push_back( num );
      permuteMe( ans, sol, arr );
      std::cout << "Popping: " << sol.back() << "\n";
      sol.pop_back(); // Important step to be able to go back the tree
   }
   std::cout << ">>>> Exiting permute\n";
}

int main()
{
   // Permutation sind n!
   // 9! = 362,880 moegliche permutationen
   std::vector<int32_t> arr = {1,2,3};

   std::vector<std::vector<int32_t> > ans;
   std::vector<int32_t> sol;

   permuteMe( ans, sol, arr );

   for( auto solArr : ans )
   {
      std::cout << "[ ";
      for( auto n : solArr )
      {
         std::cout << n << " ";
      }
      std::cout << "]\n";
   }

   return 0;
}

Ignore the cout calls :)

So the possible permutations for this question is n! in which n is the number of elements in the array.

Step by Step

Enough of talk we have the code and now we run the program in our head:

  1. Recursion Level: 0
    • Entering permuteMe
    • Entering the for loop in permuteMe starting with the first number 1
    • Pushing 1 to the solution array -> Solution array [1]
    • Calling permuteMe
    • Currently we are at the number 1 in the for loop
  2. Recursion Level: 1
    • Entering permuteMe
    • Entering the for loop
      • We skip the first iteration (number 1) because it is already added to the solution array. Following code is skipping numbers which are part of the solution already
      if( std::find( sol.begin(), sol.end(), num ) != sol.end() )
      {
          continue;
      }
      
    • Next iteration with number 2
    • We add the number 2 to the solution array -> [1,2]
    • Calling permuteMe
    • Currently we are at the number 2 in the loop
  3. Recursion Level: 2
    • Entering permuteMe
    • Entering the for loop
      • We skip the first two numbers because they are already part of the solution array
    • Next iteration with number 3
    • Pushing number 3 to the solution array -> [1,2,3]
    • Calling permuteMe
    • Currently we are at the number 3 in the loop
  4. Recursion Level: 3
    • Entering permuteMe
    • Now we entering this if clausel which indicates we reached a leaf node and there are no possible permutations left on this path. We are pushing this partial soluation (sol vector) into the ans vector which holds all the possible permutations.
    if( sol.size() == arr.size() )
    {
        ans.push_back( sol );
        std::cout << ">>>> Exiting permute size reached\n";
        return;
    }
    
    As we can see in the code above we are returning from this function so we are exiting this recursion level and will continue from Recursion Level 2
    • Returning from Recursion Level: 3
  5. Entering Recursion Level: 2 ( Basically continue from Step 3 )
    • Returning from permuteMe
    • Popping the last element from sol array which is 3. Befor: [1,2,3] -> After: [1,2]
    • We are currently still at number 3 check Point 3
    • This means we are exiting the loop and returning from this recursion level
    • Returning from Recursion Level: 2
  6. Entering Recursion Level: 1 ( Basically continue from Step 2 )
    • Popping the last element from sol array which is 2. Befor: [1,2] -> [1]
    • We are currently still at the number 2 in this Recursion level
    • Because we popped the last element the next instruction is to go to the next iteration which is 3
    • Pushing number 3 to the sol array -> [1,3]
    • Calling permuteMe
    • Currently we are at the number 3 in the loop
  7. Entering Recursion Level: 2
    • Skipping Number 1
    • Pushing 2 to the solution array -> [1,3,2]
    • Calling permuteMe
    • Currently we are at the number 2 in the loop
  8. Recursion Level: 3
    • Entering permuteMe
    • Now we entering this if clausel which indicates we reached a leaf node and there are no possible permutations left on this path. We are pushing this partial soluation (sol vector) into the ans vector which holds all the possible permutations.
    if( sol.size() == arr.size() )
    {
        ans.push_back( sol );
        std::cout << ">>>> Exiting permute size reached\n";
        return;
    }
    
    As we can see in the code above we are returning from this function so we are exiting this recursion level and will continue from Recursion Level 2
    • Returning from Recursion Level: 3
  9. Entering Recursion Level: 2 ( Basically continue from Step 7 )
    • Popping the last number Befor: [1,3,2] --> After: [1,3]
    • Because we are still at number 2 in this iteration we continue with the next iteration
    • Next iteration with Number 3
    • We skip the next iteration (number 3) because it is already added to the solution array. Following code is skipping numbers which are part of the solution already
      if( std::find( sol.begin(), sol.end(), num ) != sol.end() )
      {
          continue;
      }
      
    • Returning from Recursion level: 2
  10. Entering Recursion level: 1 ( basically continue from step 6 )
    • Popping last added element Befor: [1,3] --> After: [1]
    • We try to iterate over the next element which does not exist because we are at the last element already (check step 6 iteration)
    • Returning from Recursion level: 1
  11. Entering Recursion level: 0 ( basically continue from step 1 )
    • Popping last element in solution Befor: [1] --> After: [ ]
    • Entering next iteration which is number 2
    • Pushing number 2 to the solution array
    • Calling permuteMe

Basically thats it after that it is only repeating. In the steps above we finished following tree branch:

The red "circle" shows our path which we solved by hand step by step