Print all permutations with repetition of characters

Question

Given a string of length n, print all permutation of the given string. Repetition of characters is allowed. Print these permutations in lexicographically sorted order

Examples:

Input: AB

Ouput: All permutations of AB with repetition are:

  AA
  AB
  BA
  BB

Input: ABC

Output: All permutations of ABC with repetition are:

   AAA
   AAB
   AAC
   ABA
   ...
   ...
   CCB
   CCC

The following is my code:

void permutate(const string& s, int* index, int depth, int len, int& count)
{
    if(depth == len)
    {
        ++count;
        for(int i = 0; i < len; ++i)
        {
            cout << s[index[i]];
        }
        cout << endl;
        return;
    }

    for(int i = 0; i < len; ++i)
    {
        index[depth] = i;
        permutate(s, index, depth+1, len, count);
    }
}

int main()
{
    string s("CBA");
    sort(s.begin(), s.end());
    cout << s << endl;
    cout << "**********" << endl;
    int len = s.size();
    int* index = new int[len];
    int count = 0;
    permutate(s, index, 0, len, count);
    cout << count << endl;

    system("pause");
    return 0; 
}

Answer 1

• In case you ever want to just display the string (if you have something like "AAA"):

  // if a different character from the first is not found
  // std::string::npos corresponds to "not found" (or -1)
  
  if (s.find_first_not_of(s.front()) == std::string::npos)
  {
      // inform user that only one permutation exists
  }
  

• This is a potential loss of data:

  int len = s.size();
  

  size() returns std::size_type, not int. Do not use int for std::string or other STL container sizes. They have their own size types that prevents this very issue. This would be the proper initialization of len:

  std::string::size_type len = s.size();
  

• This is needless and potentially dangerous:

  int* index = new int[len];
  

  The "dangerous" part refers to the fact that delete is never used to free the allocated memory. Always use delete with new where appropriate.

  In order to free the memory properly, you would use delete in this way:

  delete [] index;
  

  But since you're utilizing the STL, instead consider an std::vector:

  std::vector<int> index(s.size());
  

  As the memory management is already properly done in std::vector's implementation, new/delete is not needed here at all. Always try to avoid doing this manually in C++.

• No need to pass the string's size; it's already part of the implementation. Just use s.size().

• With the utilization of the aforementioned std::vector and size(), you should now make depth and the loop counters of std::size_t. This will avoid type-mismatch warnings from comparing size() with an int. Make sure your compiler's warning flags are high.

• Avoid using system("PAUSE") as it is platform-specific and can be imitated by better alternatives such as std::cin.get(). This will ask the user for a console input instead of a keystroke, but that difference shouldn't matter if it means maintaining portability.

Final code with applied changes (also tested on Ideone):

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

void permutate(const std::string& s, std::vector<int>& index, std::size_t depth, int& count)
{
    if (depth == s.size())
    {
        ++count;
        for (std::size_t i = 0; i < s.size(); ++i)
        {
            std::cout << s[index[i]];
        }
        std::cout << "\n";
        return;
    }

    for (std::size_t i = 0; i < s.size(); ++i)
    {
        index[depth] = i;
        permutate(s, index, depth+1, count);
    }
}

int main()
{
    std::string s("CBA");

    if (s.find_first_not_of(s.front()) == std::string::npos)
    {
        std::cout << "Only 1 permutation exists";
        return 0;
    }

    std::sort(s.begin(), s.end());

    std::cout << s << "\n**********\n";

    std::vector<int> index(s.size());
    int count = 0;

    permutate(s, index, 0, count);

    std::cout << "\nTotal permutations with repetitions: " << count;
}

Answer 2

I think it could be improved by not calling the task "permutations". Permutations are rearrangements. It seems you are mostly producing all combinations.

I refer you to these:

• http://www.cplusplus.com/reference/algorithm/next_permutation/
• http://en.wikipedia.org/wiki/Permutation