Search code examples
c#stringpermutationstring-length

Generating all variations of certain length out of string

I've seen few implementations of variations of string in C#, but none of them had any limitation on their length. Unfortunately, I cannot modify them to achieve my goal which is e.g.

for:

string = "ABCD" and variationLength = 2

generate new strings:

AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC

I'm looking for exactly this Python's itertools.permutations implementation but in C#. (https://docs.python.org/3/library/itertools.html#itertools.permutations)

Is there anything similar to its in C#? If not, then what is the easiest way to implement it?

Edit_2: so far I came up with an idea to list all unique chars of given string and then get variations out of them

static void PrintAllKLengthPerm(string str, int k)
{
    int n = str.Length;
    PrintAllKLengthPermRec(str, "", n, k);
}

// The main recursive method to print all possible strings of length k
static void PrintAllKLengthPermRec(string str, String prefix, int n, int k)
{
    // Base case: k is 0, print prefix
    if (k == 0)
    {
        Console.WriteLine(prefix);
        return;
    }

    // One by one add all characters from str and recursively 
    // call for k equals to k-1
    for (int i = 0; i < n; ++i)
    {
        // Next character of input added
        String newPrefix = prefix + str[i];

        // k is decreased, because we have added a new character
        PrintAllKLengthPermRec(str, newPrefix, n, k - 1);
    }
}

static void Main(string[] args)
{
    string str = "ABCD";
    int permLen = 2;

    //get all unique characters in string
    string uniqStr = new String(str.Distinct().ToArray());

    // Print all possible strings of length permLen out of uniqStr characters
    PrintAllKLengthPerm(uniqStr, permLen);      
}

However I am looking for more optimal and effective solution

Solution

  • Here's a truly recursive permutation method:

    public IEnumerable<string> Permutate(string source, int count)
{
    if (source.Length == 1)
    {
        yield return source;
    }
    else if (count == 1)
    {
        for (var n = 0; n < source.Length; n++)
        {
            yield return source.Substring(n, 1);
        }
    }
    else
    {
        for (var n = 0; n < source.Length; n++)
            foreach (var suffix in Permutate(
                source.Substring(0, n)
                    + source.Substring(n + 1, source.Length - n - 1), count -1))
            {
                yield return source.Substring(n, 1) + suffix;
            }
    }
}

    It can be called with Permutate("ABCD", 2) and returns this:

    output