8
\$\begingroup\$

I came across this interview question and it has been asked to print combinations of the characters in a string. For example: "abc" --> a, b, c, ab, ac, bc, abc. Also it has been mentioned that 'ab' and 'ba' are same.

I want to know if there is any improvement I can make in terms of memory usage/performance.

public string[] Combination(string str)
{
    if (string.IsNullOrEmpty(str))
        throw new ArgumentException("Invalid input");

    if (str.Length == 1)
        return new string[] { str };

    // read the last character
    char c = str[str.Length - 1];

    // apart from the last character send remaining string for further processing
    string[] returnArray = Combination(str.Substring(0, str.Length - 1));

    // List to keep final string combinations
    List<string> finalArray = new List<string>();

    // add whatever is coming from the previous routine
    foreach (string s in returnArray)
        finalArray.Add(s);

    // take the last character
    finalArray.Add(c.ToString());

    // take the combination between the last char and the returning strings from the previous routine
    foreach (string s in returnArray)
        finalArray.Add(s + c);

    return finalArray.ToArray();
}
\$\endgroup\$

migrated from stackoverflow.com Jul 8 '13 at 12:50

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ For big strings you can fall through stackoverflow exception. \$\endgroup\$ – Hamlet Hakobyan Jul 8 '13 at 7:07
  • \$\begingroup\$ @HamletHakobyan: thanks for your reply. is there any way to avoid it? \$\endgroup\$ – Pritam Karmakar Jul 8 '13 at 7:15
  • \$\begingroup\$ @p.s.w.g: From next time I will surely post such question in the codereview site. thanks for the information. \$\endgroup\$ – Pritam Karmakar Jul 8 '13 at 7:16
6
\$\begingroup\$

I can suggest following project for combinations and permutations which is very efficient and easy to use:

http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G

Then it's simple as:

IList<Char> chars = "abc".ToList();
List<string> allCombinations = new List<String>();
for (int i = 1; i <= chars.Count; i++)
{ 
    var combis = new Facet.Combinatorics.Combinations<Char>(
        chars, i, Facet.Combinatorics.GenerateOption.WithRepetition);
    allCombinations.AddRange(combis.Select(c => string.Join("", c)));
}

foreach (var combi in allCombinations)
    Console.WriteLine(combi);

Output:

a
b
c
aa
ab
ac
bb
bc
cc
aaa
aab
aac
abb
abc
acc
bbb
bbc
bcc
ccc

If you don't want repetion you just have to change GenerateOption.WithRepetition to GenerateOption.WithoutRepetition and the result is:

a
b
c
ab
ac
bc
abc
\$\endgroup\$
  • 7
    \$\begingroup\$ I wonder if that would be accepted at an interview. \$\endgroup\$ – svick Jul 8 '13 at 14:14
5
\$\begingroup\$

You can improve the implementation by building the strings only when needed:

public static string[] Combination2(string str)
{
    List<string> output = new List<string>();
    // Working buffer to build new sub-strings
    char[] buffer = new char[str.Length];

    Combination2Recurse(str.ToCharArray(), 0, buffer, 0, output);

    return output.ToArray();
}

public static void Combination2Recurse(char[] input, int inputPos, char[] buffer, int bufferPos, List<string> output)
{
    if (inputPos >= input.Length)
    {
        // Add only non-empty strings
        if (bufferPos > 0)
            output.Add(new string(buffer, 0, bufferPos));

        return;
    }

    // Recurse 2 times - one time without adding current input char, one time with.
    Combination2Recurse(input, inputPos + 1, buffer, bufferPos, output);

    buffer[bufferPos] = input[inputPos];
    Combination2Recurse(input, inputPos + 1, buffer, bufferPos + 1, output);
}

When run 100,000 times with the string 'abcdefghi' on my laptop the results are:

  • Question's implementation: 5.21s
  • This implementation: 2.48s
  • Tim Schmelter's implementation: 93s
  • p.s.w.g's implementation: 142s

You can further improve performance/memory by pre-allocating the needed output array string[] and writing the strings directly to the array (the size is 2^n, minus 1 the empty string).

\$\endgroup\$
  • \$\begingroup\$ Just wondering, is the Tim you referring now Rango? \$\endgroup\$ – Chor Wai Chun Apr 29 at 5:52
  • \$\begingroup\$ @ChorWaiChun Yes. \$\endgroup\$ – sagis Apr 30 at 19:51
4
\$\begingroup\$

Mostly for fun, this version will work for strings up to 30 characters long:

var str = "abc";
var results = 
    from e in Enumerable.Range(0, 1 << str.Length)
    let p = 
        from b in Enumerable.Range(0, str.Length)
        select(e & (1 << b)) == 0 ? (char?)null : str[b]
    select string.Join(string.Empty, p);

Or in fluent syntax:

var results = Enumerable.Range(0, 1 << str.Length)
    .Select(e => string.Join(string.Empty, Enumerable.Range(0, str.Length).Select(b => (e & (1 << b)) == 0 ? (char?)null : str[b])));

The output will be:

{empty string}
a
b
ab
c
ac
bc
abc

You can use Enumerable.Range(1, (1 << str.Length) - 1) or .Skip(1) to exclude the empty string in the results.

If you write your own Range function using BigInteger's, like this:

public IEnumerable<BigInteger> Range(BigInteger start, BigInteger count)
{
    while(count-- > 0)
    {
        yield return start++;
    }
}

You can extend this technique to support strings of any length:

var results = 
    from e in Range(0, BigInteger.Pow(2, str.Length))
    let p = 
        from b in Enumerable.Range(1, str.Length)
        select(e & BigInteger.Pow(2, b - 1)) == 0 ? (char?)null : str[b - 1]
    select string.Join(string.Empty, p);
\$\endgroup\$
  • \$\begingroup\$ what about using UInt64 instead of int (as the data type of 'e' above) to work for strings of length up to 63 characters? \$\endgroup\$ – bytefire Jul 8 '13 at 9:07
  • \$\begingroup\$ @bytefire Absolutely. You could do that, but you'd have to write your own version Enumerable.Range for that, which kind of ruins the nice 'one-liner' aspect of this solution, and ultimately it just pushes the hard limit back a few steps. If you use BigInteger's it will work for arbitrary-length strings (see my updated answer), though not as efficiently since BigInteger math is much slower than int or long math. \$\endgroup\$ – p.s.w.g Jul 8 '13 at 10:04
  • \$\begingroup\$ My up vote was, in part, for the one-liner niceness. \$\endgroup\$ – bytefire Jul 8 '13 at 10:25
  • \$\begingroup\$ I'm working on similar function and this gives a good head start, do you have any idea what I should change if I only wanted to find "connected" permutations in "original sequence"? For example, for the case of abc, the result should be only a/b/c/ab/bc/abc. \$\endgroup\$ – Chor Wai Chun Apr 29 at 9:31
  • \$\begingroup\$ @ChorWaiChun I think I'd take a different approach. In that case, each result would be a non-empty substring of str, i.e. from i in Range(0, str.length - 1) from j in Range(1, str.length - i) select str.Substring(i, j); \$\endgroup\$ – p.s.w.g Apr 29 at 15:06

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