Create all permutations of a string incrementally c#

Question

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?

What do you mean by incrementally? Do you whant to add all permutations in a List or do you want a function that produce the next permutation from the given string ? — fluminis, Feb 02 '11 at 17:31
Voted to close. Those are not permutations. The specifications are not enough. — Dr. belisarius, Feb 02 '11 at 17:36
Search around for "C# increment alpha" (no quotes). Lots of examples to be found. — Clinton Pierce, Feb 02 '11 at 17:38
Think of it as counting in base 26. Just add one to the last number you use, then convert it to a base-26 string (using A-Z rather than 0-9,A-P, but the algorithm stays much the same) — The Archetypal Paul, Feb 02 '11 at 17:41
looks like a brute force password generator question. Is SO helping hackers now? — Chase Florell, Feb 02 '11 at 17:45
@belisarius - while I agree that it is not permuations, there is still enough specification to see what he wants. Although 26^5 is a lot of strings.... — Ostemar, Feb 02 '11 at 18:57
@Ostemar 26^5=11,881,376 It seems nonsensical to print-generate-whatever that. — Dr. belisarius, Feb 02 '11 at 19:02

score 4 · Answer 1 · edited May 23 '17 at 12:33

4

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

edited May 23 '17 at 12:33

Community

1
1

answered Feb 02 '11 at 21:04

Eric Lippert

647,829
179
1,238
2,067

Matthew Whited · Answer 2 · 2011-02-02T18:05:12.437

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);
}

score 1 · Accepted Answer · answered Feb 02 '11 at 19:05

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);
}

This is a lot better than what I had! – jjj Feb 02 '11 at 20:05 — jjj, Feb 02 '11 at 20:05

score 0 · Answer 4 · answered Feb 02 '11 at 17:42

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';
      }
    }
  }
}

score 0 · Answer 5 · answered Feb 02 '11 at 19:36

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();
}

Create all permutations of a string incrementally c#

5 Answers5