CODEWITHSUNDEEP
c#stringpermutationstring-length
Jay Double
Jay Double

Reputation: 57

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

Upvotes: 0

Views: 2361

Answers (4)

Optimistic Peach
Optimistic Peach

Reputation: 4288

List<string> newPermutations = new List<string>();
for(int a = 0; a!=inString.Count; a++)
    for((int b = 0; b!=inString.Count; b++)
        if(noRepetitions && a == b) continue;
        newPermutations.Add(""+inString[a] + inString[b]);

I think that that should work; I am still trying to figure out a way to not only have 2 letters.

Edit: Edited it to work, the old one just didn't work... lol Edit: Thanks to @Bloopy, they helped me spot some errors in my for loops

Upvotes: 1

Bloopy
Bloopy

Reputation: 429

Here's a solution using modulo and division. There are 4² possible strings of length 2 using the letters ABCD. Number them from 0 to 4²-1 and repeatedly divide each number by 4. Use the resulting remainders as array indexes on the ABCD string.

This has the advantage of allowing you to keep the strings with repeated elements (AA, BB, CC, DD) when needed – just skip the discard step.

string alphabet = "ABCD";
int length = 2;

int[] indexes = new int[length];
char[] item = new char[length];

// loop through all possible strings for the given alphabet and length
for (int i = 0; i < Math.Pow(alphabet.Length, length); i++) {

    int dividend = i;
    for (int j = length - 1; j >= 0; j--) {
        indexes[j] = dividend % alphabet.Length;
        dividend /= alphabet.Length;
    }

    // discard any that use the same alphabet element more than once
    if (indexes.Distinct().Count() < length)
        continue;

    for (int k = 0; k < length; k++) {
        item[k] = alphabet[indexes[k]];
    }

    Console.WriteLine(item);
}

Alternatively, here's a really brief solution using LINQ. Note that this one doesn't work correctly if there are duplicate elements in the string (unless you want to remove the call to Where and keep the AA, BB etc.). I'd need to track the indexes like I did in my method above.

IEnumerable<string> prm = alphabet.Select(c => c.ToString());
for (int a = 1; a < length; a++)
    prm = prm.SelectMany(s => alphabet.Where(t => !s.Contains(t)), (x, y) => x + y);

foreach (string s in prm)
    Console.WriteLine(s);

Upvotes: 0

Enigmativity
Enigmativity

Reputation: 117064

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

Upvotes: 1

Meccano
Meccano

Reputation: 537

I made the following recursive function which accomplishes your task:

static void Permutations(List<string> output, string str, int n, string curr)
    {
        if(curr.Length == n)
        {
            output.Add(curr);
            return;
        }
        foreach(char c in str)
            if(!curr.Contains(c.ToString()))
                Permutations(output, str, n, curr + c.ToString());
    }

and then you call it like this:

string str = "ABCD";
int length = 2;
List<string> perms = new List<string>();
Permutations(perms, str, length, "");
// now the list "perms" will contain the permutations of "str" in length "n"

Upvotes: 1

Related Questions