how can i get combinations of string Array?

Question

Possible Duplicate:
Generating all Possible Combinations

I'm trying to do a little algorithm in C++ or C#

Basically if you have an array:

{"ab","cd"}

output:

ac
ad
bc
bd

(I have two nested for loops)

but what if i have an array of 3 elements? or 4 ?

Thank you guys :)

Try to write to console all binary numbers with two (or three, or N) digits, and see how you can apply it to this problem. — vgru, Feb 12 '12 at 14:17

score 4 · Answer 1 · edited May 23 '17 at 10:34

4

You are looking for the Cartesian product of arbitrarily many sequences of characters. See this blog post:

http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx

and this StackOverflow question, which you have duplicated.

Generating all Possible Combinations

edited May 23 '17 at 10:34

Community

1
1

answered Feb 12 '12 at 15:26

Eric Lippert

647,829
179
1,238
2,067

Sergey Kalinichenko · Accepted Answer · 2012-02-12T18:30:36.437

In order to vary the number of "nested loops" you need to use recursion.

void printCombination(string[] str, string partial, int p) {
    if (p == str.Length) {
        Console.WriteLine(partial);
        return;
    }
    for (int i = 0 ; i != str[p].Length; i++) {
        printCombination(str, partial + str[p][i], p+1);
    }
}

Initial call looks like this:

printCombination(new[] {"ab", "cd", "ef", "gh"}, "", 0);

EDIT (in response to a comment by OP)

To understand what is going on, you need to understand the meaning of the parameters first:

str is the array of strings. Each element of the array corresponds to a nesting level of the imaginary nested loops: element 0 is for the outer loop, element 1 is for the first level of nesting, and so on.
partial is the partially constructed result string. It is empty at the initial level, has one character at the first level of nesting, two at the second, and so on.
p is the nesting level. It is zero in the initial level, one at the first nesting level, and so on.

The function has two parts - the stopping condition, and the body of the recursive call. The stopping condition is simple: once we get to the last level, partial result is no longer "partial": it is complete; we can print it out and exit. How do we know that we're at the last level? The number of elements of str equals the number of levels, so when p equals the length of the str array, we're done.

The body of the recursive call is a loop. It does the same thing that your nested loops do, but for only one level: each iteration adds one letter from its own array, and calls itself recursively for the next level.

The best way to see this in action is to set a breakpoint on the line with the return statement, and look at the call stack window . Click each invocation level, and inspect the values of function parameters.

If you are up for an exercise, try modifying this function to take two parameters instead of three. Hint: you can eliminate the last parameter by observing that the length of partial always matches the value of p.

"need to use" is not quite true, since any recursive algorithm could be written iteratively. However, recursion is easiest to grasp. — Hogan, Feb 12 '12 at 14:34
@Hogan Well, logically recursive algorithm remains recursive no matter how it is implemented. In the end, it all boils down to using a stack, either a hardware or a software one. — Sergey Kalinichenko, Feb 12 '12 at 14:39
Isn't this example tail end recursive so a stack is not needed? — Hogan, Feb 12 '12 at 14:56
done..dasblinkenlight you are my savior :) i've always been sloppy at recursion,dynamic algorithms and such.. if its okay, can you walk through me what you did? how you approached it? :) — Salma Nafady, Feb 12 '12 at 18:07
@SalmaNafady Sure, I just edited the answer. Try the little exercise at the end to make sure that you've understood the explanation completely. — Sergey Kalinichenko, Feb 12 '12 at 18:32

score 0 · Answer 3 · answered Feb 12 '12 at 14:19

in c++ there is an algorithm called std::next_permutation. Here is an example, hope this helps you.

#include <algorithm>
#include <string>
#include <iostream>
int main()
{
    std::string s = "aba";
    std::sort(s.begin(), s.end());
    do {
        std::cout << s << '\n';
    } while(std::next_permutation(s.begin(), s.end()));
}

Output:
aab
aba
baa

score 0 · Answer 4 · answered Feb 12 '12 at 14:19

Then you cannot use nested for loops, since you cannot vary this programmatically.

In that case, use a counter for each element, which is the current element you are iterating. Use a while loop and a function to check if you are finished.

Increase the counter of the first element, if it has reached its maximum, set it to 0 and increase the next counter etc.

(edit: the solution using the permutation probably makes use of my solution internally).

how can i get combinations of string Array?

4 Answers4