CODEWITHSUNDEEP
c#stringpermutation
jjj
jjj

Reputation: 59

Create all permutations of a string incrementally c#

I am trying to create a function that will create all permutations of a string in an incremental fashion. I would like to start at:

AAAAA
...
AAAAB
...
ACCCC
...
...
ZZZZZ

I have looked around, and can't seem to find anything of that sort. I tried to create it, but it wasn't incrementally.

Any suggestions?

Upvotes: 2

Views: 2332

Answers (5)

Eric Lippert
Eric Lippert

Reputation: 659956

The "permutation" you are describing is better known as the Cartesian product. If you have an arbitrary number of sequences that you need to form the Cartesian product of, see my answer to this question on the subject:

Generating all Possible Combinations

Upvotes: 4

Vlad Bezden
Vlad Bezden

Reputation: 89499

Here is the LINQPad friendly code and it uses lambda expression.

void Main()
{
    var chars = Enumerable.Range(65, 26);

    var strings = chars.SelectMany (a => 
        {
            return chars.SelectMany (b => chars.SelectMany (c => 
                {
                    return chars.SelectMany (d => 
                    {
                        return chars.Select (e => {return new string(new char[] {(char)a, (char)b, (char)c, (char)d, (char)e});});
                    });
                }));
        });

    strings.Dump();
}

Upvotes: 0

Ostemar
Ostemar

Reputation: 5808

A different variant where I had the idea of using modulo arithmetic. Note that I lowered the character to {A,B,C} to test it, since going up to Z for 5 letters is a lot of strings.

public IEnumerable<char[]> AlphaCombinations(int length = 5, char startChar = 'A', char endChar = 'C')
{
    int numChars = endChar - startChar + 1;
    var s = new String(startChar, length).ToCharArray();    
    for (int it = 1; it <= Math.Pow(numChars, length); ++it) 
    {        
        yield return s;

        for (int ix = 0; ix < s.Length; ++ix) 
            if (ix == 0 || it % Math.Pow(numChars, ix) == 0) 
                s[s.Length - 1 - ix] = (char)(startChar + (s[s.Length - 1 - ix] - startChar + 1) % numChars);
    }
}

...

foreach (var s in AlphaCombinations(5))
{
    Console.WriteLine(s);
}

Upvotes: 1

Matthew Whited
Matthew Whited

Reputation: 22433

Normally I wouldn't help these brute force type results... but seeing how many useless result you will get out of the set I figured I'd just toss this in.

var query = from c0 in Enumerable.Range(0, 26)
            from c1 in Enumerable.Range(0, 26)
            from c2 in Enumerable.Range(0, 26)
            from c3 in Enumerable.Range(0, 26)
            from c4 in Enumerable.Range(0, 26)
            select new string(
                new [] {
                    (char)('A' + c0),
                    (char)('A' + c1),
                    (char)('A' + c2),
                    (char)('A' + c3),
                    (char)('A' + c4),
                }
                );

BTW... if you just want the next value you can do something like this...

public static string Increment(string input)
{
    var array = input.ToCharArray();
    if (array.Any(c => c < 'A' || c > 'Z'))
        throw new InvalidOperationException();

    for (var i = array.Length-1; i >= 0; i--)
    {
        array[i] = (char)(array[i] + 1);
        if (array[i] > 'Z')
        {
            array[i] = 'A';
            if (i == 0)
                return 'A' + new string(array);
        }
        else
            break;
    }
    return new string(array);
}

Upvotes: 2

Rup
Rup

Reputation: 34408

Bashed out quickly - I expect this could be done better:

public static IEnumerable<string> GenerateStrings(int length = 5)
{
  var buffer = new char[length];
  for (int i = 0; i < length; ++i)
  {
    buffer[i] = 'A';
  }
  for(;;)
  {
    yield return new string(buffer);

    int cursor = length;
    for(;;)
    {
      --cursor;
      if (cursor < 0)
      {
        yield break;
      }

      char c = buffer[cursor];
      ++c;
      if (c <= 'Z')
      {
        buffer[cursor] = c;
        break;
      }
      else
      {
        buffer[cursor] = 'A';
      }
    }
  }
}

Upvotes: 0

Related Questions