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

Question

I am given a string and i need to find all possible 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?

Strictly speaking, those are *permutations* and there are `n!` of them: `n * (n-1) * (n-2) * ... * 1` — Álvaro González, Jul 29 '11 at 16:04

score 3 · Accepted Answer · answered Jul 29 '11 at 15:52

3

you can sort it then use std::next_permutation

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

answered Jul 29 '11 at 15:52

Hayri Uğur Koltuk

2,970
4
31
60

score 1 · Answer 2 · answered Jul 29 '11 at 15:53

1

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.

answered Jul 29 '11 at 15:53

Mark B

95,107
10
109
188

i want to see bbac once... so what is my problem called? – lin Jul 29 '11 at 15:56
You want the combinations, rather than the permutations of the string. :) – Thomas Russell Jul 29 '11 at 15:59

score 1 · Answer 3 · edited May 23 '17 at 12:23

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. :)

score 0 · Answer 4 · answered Jul 29 '11 at 15:54

0

In C++, std::next_permutation:

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

answered Jul 29 '11 at 15:54

Peter Alexander

53,344
14
119
168

score 0 · Answer 5 · answered Jul 29 '11 at 16:00

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;
}

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

5 Answers5