How can I find all possible letter combinations of a string?

I am given a string and i need to find all pos开发者_开发技巧sible letter combinations of this string. What is the best way I can achieve this? example:

abc

result:

abc
acb
bca
bac
cab
cba

i have nothing so far. i am not asking for code. i am just asking for the best way to do it? an algorithm? a pseudocode? maybe a discussion?

you can sort it then use std::next_permutation

take a look at the example: http://www.cplusplus.com/reference/algorithm/next_permutation/

Do you want combinations or permutations? For example, if your string is "abbc" do you want to see "bbac" once or twice?

If you actually want permutations you can use std::next_permutation and it'll take care of all the work for you.

If you want the combinations (order independant) You can use a combination finding algorithm such as that found either here or here. Alternatively, you can use this (a java implementation of a combination generator, with an example demonstrating what you want.

Alternatively, if you want what you have listed in your post (the permutations), then you can (for C++) use std::next_permutation found in <algorithm.h>. You can find more information on std::next_permutation here.

Hope this helps. :)

In C++, std::next_permutation:

std::string s = "abc";
do
{
  std::cout << s << std::endl;
} while (std::next_permutation(s.begin(), s.end()));

Copied from an old Wikipedia article;

For every number k, with 0 ≤ k < n!, the following algorithm generates a unique permutation on sequence s.

function permutation(k, s) {
     for j = 2 to length(s) {
        swap s[(k mod j) + 1] with s[j]; // note that our array is indexed starting at 1
        k := k / j;        // integer division cuts off the remainder
     }
     return s;
}