Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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; 
}
share|improve this question
    
Doesn't seem to work. Firstly, the strings are not in lexicographically sorted order, and secondly there are repetitions - eg if string = "AAA", it prints "AAA" 27 times when there is really only 1 permutation. Or did I misunderstand the objective? Also should string s be const string& s ? –  William Morris Oct 23 '12 at 17:52
    
@WilliamMorris, for the case "AAA", it's OK to print 27 times. You're right, the strings are not in lexicographically sorted order. I should sort the string at first. Thanks very much –  FihopZz Oct 24 '12 at 0:17
    
Removed the C tag, as this is clearly C++. –  harald Mar 6 '13 at 23:05
    
Is the question yours, or one you have been asked? Are the examples yours, or given as well? –  RichardPlunkett Nov 25 '13 at 3:29
    
I'm leaving a comment here in case you haven't seen my answer. I've just made a large edit to it. –  Jamal Mar 15 at 23:17
add comment

2 Answers

  • 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;
}
share|improve this answer
add comment

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:

share|improve this answer
    
please elaborate, this is for code review. please give a nice review of the code. –  Malachi Nov 25 '13 at 2:36
    
Whats to elaborate? Sure I have not give a full review of the code, but correct naming is an important part of coding and I thought qualifies as meaningful feedback. 'Permutation' not only generally means something other than as used in his code, but specifically means something else in C++, due to the standard library function next_permutation. And, btw, when I first looked at his code, one of the first things I wondered is why isnt he using std::next_permutation, and I had to figure out that he isn't doing perumtations. That's work for the next reader that could be avoided. –  RichardPlunkett Nov 25 '13 at 3:28
    
you put more into a comment explaining why you didn't add more to your answer. point made. explain these things in the answer please. as it stands your answer could have been written in a comment, and looks like a comment. –  Malachi Nov 25 '13 at 3:42
    
I have actually removed the std::next_permutation snippet from my answer. I've realized that it may be best to stick with the OP's permutations with repetition, which the STL function does not perform. Yes, permutations are rearrangements. But the order does matter, unlike combinations. I also agree with Malachi: your answer could be more substantial if it explained how the code can actually be improved. If that means producing permutations without repetition, then that could be explained. These links by themselves are not enough. –  Jamal Dec 8 '13 at 5:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.