Showing posts from October, 2008

Permutations of a string containing duplicates (C++ Version)

Update : This is part 1 of a 2 part series of posts that discuss generating all possible permutations/anagrams of a given string. This post discusses how to use the next_permutation function provided by the standard C++ library to generate the anagrams iteratively. The next post discusses a custom recursive implementation of how to achieve the same thing. See:  Recursively printing all permutations of a string containing duplicate characters. Have you ever thought of how to generate and display/print all possible permutations of a string (containing duplicate characters) such that every legal permutation appears atmost once in the final output, without taking a humungous amount of memory to keep track of all the permutations you have generated? This particular function utilizes a cool STL algorithm and generates all possible permutations of a string only once (whether the original string contained duplicates or not). int dup_permute(char *str, size_t length) {     int count = 0;