CODEWITHSUNDEEP
c#stringcombinations
Junior
Junior

Reputation: 13

All combination (and not permutation) of a string in c#

I'm just want to find all combinations of an input string, so if i use this world: "cat" i want to get something like:

c
a
t
ca
ct
ac
at
ta
tc
cat
cta
 ... etc

but NOT

ccc
cca
... etc

I found a lot of similar, but those get permutations just as long as the input string, or it just knocks out some. If i have 4 char long string how do I get it to give me 1, 2 and 4 char long strings?

Upvotes: 0

Views: 1942

Answers (1)

Rami Yampolsky
Rami Yampolsky

Reputation: 475

Actually you have here 3 phases:

  1. Select the letters from the input word. I do that by using counter which is promoted, then looking at it as bits representation, if bit i is '1', then I choose character i. If '0' then don't.
  2. Generate permutations based on selected letters. Here I use recursive helper function Permutations
  3. Remove duplicates from the final result. Duplicates can occure in case your original word duplicate characters. for example: "catt"

Solution:

static void Main(string[] args)
{
    string word = "catt";

    List<string> result = new List<string>();

    int total = (int)Math.Pow(2, word.Length);


    for (int i = 0; i < total; i++)
    {
        string tempWord = string.Empty;
        // pick the letters from the word

        for (int temp = i, j = 0; temp > 0; temp = temp >> 1, j++)
        {
            if ((temp & 1) == 1)
            {
                tempWord += word[j];
            }
        }

        // generate permutations from the letters
        List<string> permutations;
        Permutations(tempWord, out permutations);

        foreach (var prm in permutations)
            result.Add(prm);
    }

    // remove duplicates
    var resultWithoutDuplicates = result.Distinct();

    foreach (var w in resultWithoutDuplicates)
        Console.WriteLine(w);


    Console.ReadLine();

}


static void Permutations(string str, out List<string> result)
{
    result = new List<string>();

    if (str.Length == 1)
    {
        result.Add(str);
        return;
    }


    for (int i = 0; i < str.Length; i++)
    {
        char c = str[i];
        string temp = str.Remove(i, 1);

        List<string> tempResult;
        Permutations(temp, out tempResult);

        foreach (var tempRes in tempResult)
            result.Add(c + tempRes);
    }
}

Instead of doing the final step (remove duplication) we can use hashset instead of list, to ensure no duplication during results adding to final data structure.

Hope it helps.

Upvotes: 1

Related Questions