Iterative Permutation and Recursive Permutation Algorithms.

 

 1. Permutation algorithm with swap and recursion

 class Solution {
public:
   void swap(vector<int> &num, int i, int j) {
        if (i != j) {
            int tmp = num[i];
            num[i]= num[j];
            num[j] = tmp;          
        }
    }

    void helper(vector<int> &num, int pos, vector<vector<int>> &ans)
    {
        int n = num.size();
        if (pos == n) {
            ans.push_back(num);
            return;
        }
        for(int i = pos; i < n; i++)
        {
            swap(num, pos, i);
            helper(num, pos+1, ans);
            swap(num, pos, i);
        }
    }
    vector<vector<int>> permute(vector<int> &num) {
        int N = num.size();
        vector<vector<int>> output;
        helper(num, 0, output);
        return output;
    }
};

2. Permutation algorithm with a used mask:

class Solution {
public:
    void helper(const vector<int> &num, vector<int> &current, vector<bool> &used, int pos, vector<vector<int>> &ans)
    {
        int n = num.size();
        if (pos == n) {
            ans.push_back(current);
            return;
        }
     
        for(int i = 0; i < n; i++){
            if (!used[i]) {
                used[i] = true;
                current[pos]= num[i];
                helper(num, current, used, pos+1, ans);
                used[i] = false;
            }
        }
    }
    vector<vector<int>> permute(vector<int> &num) {
        vector<vector<int>> output;
        vector<bool> used(num.size(), false);
        vector<int> current(num.size());
        helper(num, current,used, 0, output);
        return output;
    }
};

3. Iterative way by Next permutation
class Solution {
public:
      void swap(vector<int> &num, int i, int j) {
        if (i != j) {
            int tmp = num[i];
            num[i]= num[j];
            num[j] = tmp;          
        }
    }
    void reverse(vector<int> &num, int i, int j) {
        while(i < j) {
           swap(num, i, j);      
           i++;
           j--;
        }
    }
 
    void nextPermutation(vector<int> &num) {
        int N = num.size();
        int i = N-1;
        while(i >0  && num[i] <= num[i-1])
          i--;
        if (i == 0) {
            reverse(num, 0, N-1);
            return;
        }
        i--;
        int j = N-1;
        while(j > i && num[j] <= num[i])
            j--;
           
        swap(num, i, j);
        reverse(num, i+1, N-1);
    }
 
    vector<vector<int>> permute(vector<int> &num) {
        vector<vector<int>> output;
        sort(num.begin(), num.end());
        int n = num.size();
        int total = 1;
        while(n>1)
            total *=n--;
        while(--total>=0)
        {
            output.push_back(num);
            nextPermutation(num);
        }
        return output;
    }
};

4. Here is my original way of permutation in iterative:

// ----------------------------------------------------------------------------
// Copyright (c) SimpleCoder 201３
// ----------------------------------------------------------------------------

class Solution {
public:
   void swap(vector<int> &num, int i, int j) {
        if (i != j) {
            int tmp = num[i];
            num[i]= num[j];
            num[j] = tmp;          
        }
    }

    vector<vector<int>> permute(vector<int> &num) {
        int N = num.size();
     
        vector<vector<int>> output;
        vector<int> mask(N);
     
        for(int i = 0; i < N; i++)
           mask[i] = i;
     
        while(true) {
            output.push_back(num);
            for(int i = 0; i <= N; i++) {
              if (i == N) return output;
              if (mask[i] == 0) {
                  mask[i] = i;
                  swap(num, 0, i); // Important
              } else {
                  swap(num, mask[i], i);
                  mask[i]--;
                  swap(num, mask[i], i);
                  break;
              }
          }
      }      
    }
};