How to make next step of a string. C#

Question

The question is complicated but I will explain it in details.

The goal is to make a function which will return next "step" of the given string.

For example

String.Step("a"); //  = "b"
String.Step("b"); //  = "c"
String.Step("g"); //  = "h"
String.Step("z"); // = "A"
String.Step("A"); // = "B"
String.Step("B"); // = "C"
String.Step("G"); // = "H"

Until here its quite easy, But taking in mind that input IS string it can contain more than 1 characters and the function must behave like this.

String.Step("Z"); // = "aa";
String.Step("aa"); // = "ab";
String.Step("ag"); // = "ah";
String.Step("az"); // = "aA";
String.Step("aA"); // = "aB";
String.Step("aZ"); // = "ba"; 
String.Step("ZZ"); // = "aaa";

and so on...

This doesn't exactly need to extend the base String class.

I tried to work it out by each characters ASCII values but got stuck with strings containing 2 characters.

I would really appreciate if someone can provide full code of the function.

Thanks in advance.

EDIT *I'm sorry I forgot to mention earlier that the function "reparse" the self generated string when its length reaches n.

continuation of this function will be smth like this. for example n = 3
String.Step("aaa"); // = "aab";
String.Step("aaZ"); // = "aba";
String.Step("aba"); // = "abb";
String.Step("abb"); // = "abc";
String.Step("abZ"); // = "aca";
.....
String.Step("zzZ"); // = "zAa";
String.Step("zAa"); // = "zAb";
........

I'm sorry I didn't mention it earlier, after reading some answers I realised that the problem was in question.

Without this the function will always produce character "a" n times after the end of the step.

Answer 1

NOTE: This answer is incorrect, as "aa" should follow after "Z"... (see comments below)

Here is an algorithm that might work:

each "string" represents a number to a given base (here: twice the count of letters in the alphabet).

The next step can thus be computed by parsing the "number"-string back into a int, adding 1 and then formatting it back to the base.

Example:

"a" == 1 -> step("a") == step(1) == 1 + 1 == 2 == "b"

Now your problem is reduced to parsing the string as a number to a given base and reformatting it. A quick googling suggests this page: http://everything2.com/title/convert+any+number+to+decimal

How to implement this?

• a lookup table for letters to their corresponding number: a=1, b=2, c=3, ... Y = ?, Z = 0
• to parse a string to number, read the characters in reverse order, looking up the numbers and adding them up:
  • "ab" -> 2*BASE^0 + 1*BASE^1
  • with BASE being the number of "digits" (2 count of letters in alphabet, is that 48?)

EDIT: This link looks even more promising: http://www.citidel.org/bitstream/10117/20/12/convexp.html

Answer 2

Split the input string into columns and process each, right-to-left, like you would if it was basic arithmetic. Apply whatever code you've got that works with a single column to each column. When you get a Z, you 'increment' the next-left column using the same algorithm. If there's no next-left column, stick in an 'a'.

Answer 3

LetterToNum should be be a Function that maps "a" to 0 and "Z" to 51. NumToLetter the inverse.

long x = "aazeiZa".Aggregate((x,y) => (x*52) + LetterToNum(y)) + 1;
string s = "";

do { // assertion: x > 0
    var c = x % 52;
    s = NumToLetter() + s;
    x = (x - c) / 52;
} while (x > 0)

// s now should contain the result

Answer 4

public static class StringStep
{
    public static string Next(string str)
    {
        string result = String.Empty;
        int index = str.Length - 1;
        bool carry;
        do
        {
            result = Increment(str[index--], out carry) + result;              
        }
        while (carry && index >= 0);
        if (index >= 0) result = str.Substring(0, index+1) + result;
        if (carry) result = "a" + result;
        return result;
    }

    private static char Increment(char value, out bool carry)
    {
        carry = false;
        if (value >= 'a' && value < 'z' || value >= 'A' && value < 'Z')
        {
            return (char)((int)value + 1);
        }
        if (value == 'z') return 'A';
        if (value == 'Z')
        {
            carry = true;
            return 'a';
        }
        throw new Exception(String.Format("Invalid character value: {0}", value));
    }
}

Answer 5

Quite collection of approaches, here is mine:-

The Function:

private static string IncrementString(string s)
{
  byte[] vals = System.Text.Encoding.ASCII.GetBytes(s);
  for (var i = vals.Length - 1; i >= 0; i--)
  {
    if (vals[i] < 90)
    {
      vals[i] += 1;
      break;
    }
    if (vals[i] == 90)
    {
      if (i != 0)
      {
        vals[i] = 97;
        continue;
      }
      else
      {
        return new String('a', vals.Length + 1); 
      }
    }

    if (vals[i] < 122)
    {
      vals[i] += 1;
      break;
    }

    vals[i] = 65;
    break;
  }

  return System.Text.Encoding.ASCII.GetString(vals);
}

The Tests

Console.WriteLine(IncrementString("a") == "b");
Console.WriteLine(IncrementString("z") == "A");
Console.WriteLine(IncrementString("Z") == "aa");
Console.WriteLine(IncrementString("aa") == "ab");
Console.WriteLine(IncrementString("az") == "aA");
Console.WriteLine(IncrementString("aZ") == "ba");
Console.WriteLine(IncrementString("zZ") == "Aa");
Console.WriteLine(IncrementString("Za") == "Zb");
Console.WriteLine(IncrementString("ZZ") == "aaa");

Answer 6

I'm sorry the question is stated partly. I edited the question so that it meets the requirements, without the edit the function would end up with a n times by step by step increasing each word from lowercase a to uppercase z without "re-parsing" it.

Please consider re-reading the question, including the edited part

Answer 7

This is what I came up with. I'm not relying on ASCII int conversion, and am rather using an array of characters. This should do precisely what you're looking for.

    public static string Step(this string s)
    {
        char[] stepChars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".ToCharArray();

        char[] str = s.ToCharArray();
        int idx = s.Length - 1;

        char lastChar = str[idx];


        for (int i=0; i<stepChars.Length; i++)
        {
            if (stepChars[i] == lastChar)
            {
                if (i == stepChars.Length - 1)
                {
                    str[idx] = stepChars[0];
                    if (str.Length > 1)
                    {
                        string tmp = Step(new string(str.Take(str.Length - 1).ToArray()));
                        str = (tmp + str[idx]).ToCharArray();
                    }
                    else
                        str = new char[] { stepChars[0], str[idx] };
                }
                else
                    str[idx] = stepChars[i + 1];

                break;
            }
        }

        return new string(str);
    }

Answer 8

This is a special case of a numeral system. It has the base of 52. If you write some parser and output logic you can do any kind of arithmetics an obviously the +1 (++) here. The digits are "a"-"z" and "A" to "Z" where "a" is zero and "Z" is 51

So you have to write a parser who takes the string and builds an int or long from it. This function is called StringToInt() and is implemented straight forward (transform char to number (0..51) multiply with 52 and take the next char)

And you need the reverse function IntToString which is also implementet straight forward (modulo the int with 52 and transform result to digit, divide the int by 52 and repeat this until int is null)

With this functions you can do stuff like this: IntToString( StringToInt("ZZ") +1 ) // Will be "aaa"

Answer 9

This is a lot like how Excel columns would work if they were unbounded. You could change 52 to reference chars.Length for easier modification.

static class AlphaInt {
    private static string chars =
        "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

    public static string StepNext(string input) {
        return IntToAlpha(AlphaToInt(input) + 1);
    }

    public static string IntToAlpha(int num) {
        if(num-- <= 0) return "a";
        if(num % 52 == num) return chars.Substring(num, 1);
        return IntToAlpha(num / 52) + IntToAlpha(num % 52 + 1);
    }

    public static int AlphaToInt(string str) {
        int num = 0;
        for(int i = 0; i < str.Length; i++) {
            num += (chars.IndexOf(str.Substring(i, 1)) + 1)
                   * (int)Math.Pow(52, str.Length - i - 1);
        }
        return num;
    }
}