Permutation #recurstion #permutation

dfs.cpp

// $ g++ dfs.cpp --std=c++11
#include <iostream>
#include <vector>

template<class T>
void ShowResult(std::vector<T>& result)
{
  for (unsigned int i = 0 ; i < result.size() ; ++i) {
    std::cout << result[i] << " ";
  }
  std::cout << std::endl;
}

// Get all the permutations from 0 to max
void permute(unsigned int index, unsigned int max)
{
  static std::vector<unsigned int> result(max);
  static std::vector<bool> used(max);

  if (index >= max) {
    ShowResult(result);
    return;
  }

  for (unsigned int i = 0 ; i < max ; ++i) {
    if (!used[i]) {
      used[i] = true;
      result[index] = i;
      permute(index + 1, max);
      used[i] = false;
    }
  }
}

// Get all the permutations of the elements in the data
template<class T>
void permute(unsigned int index, std::vector<T>& data)
{
  static std::vector<T> result(data.size());
  static std::vector<bool> used(data.size());

  if (index >= data.size()) {
    ShowResult(result);
    return;
  }

  for (unsigned int i = 0 ; i < data.size() ; ++i) {
    if (!used[i]) {
      used[i] = true;
      result[index] = data[i];
      permute(index + 1, data);
      used[i] = false;
    }
  }
}

int main()
{
  permute(0, 4);

  std::vector<char> v = { 'a', 'b', 'c', 'd' }; // c++ 11 style to initialize vector.
  permute(0, v);

  return 0;
}