降低字符值的逻辑

Question

我正在处理一个逻辑，它会减少一个包含字母和数字的List<char>。例如，A10变成A9，BBA变成BAZ，123变成122。如果输入的值是最后一个（例如A或0），则应返回-。

另外，用户维护了一个List<char>变量，其中包含要跳过的字符。例如，如果列表中包含A，则值GHB应该变成GGZ而不是GHA。

这个逻辑的基础是简单地使用char进行减少，但在这些条件下，我发现它非常困难。

我的项目使用Silverlight编写，语言是C#。以下是我一直在尝试完成的三种方法的代码：

    List<char> lstGetDecrName(List<char> lstVal)//entry point of the value that returns decreased value
    {
        List<char> lstTmp = lstVal;
        subCheckEmpty(ref lstTmp);
        switch (lstTmp.Count)
        {
            case 0:
                lstTmp.Add('-');
                return lstTmp;
            case 1:
                if (lstTmp[0] == '-')
                {
                    return lstTmp;
                }
                break;
            case 2:
                if (lstTmp[1] == '0')
                {
                    if (lstTmp[0] == '1')
                    {
                        lstTmp.Clear();
                        lstTmp.Add('9');
                        return lstTmp;
                    }
                    if (lstTmp[0] == 'A')
                    {
                        lstTmp.Clear();
                        lstTmp.Add('-');
                        return lstTmp;
                    }
                }
                if (lstTmp[1] == 'A')
                {
                    if (lstTmp[0] == 'A')
                    {
                        lstTmp.Clear();
                        lstTmp.Add('Z');
                        return lstTmp;
                    }
                }
                break;
        }
        return lstGetDecrValue(lstTmp,lstVal);
    }



    List<char> lstGetDecrValue(List<char> lstTmp,List<char> lstVal)
    {
        List<char> lstValue = new List<char>();
        switch (lstTmp.Last())
        {
            case 'A':
                lstValue = lstGetDecrTemp('Z', lstTmp, lstVal);
                break;
            case 'a':
                lstValue = lstGetDecrTemp('z', lstTmp, lstVal);
                break;
            case '0':
                lstValue = lstGetDecrTemp('9', lstTmp, lstVal);
                break;
            default:
                char tmp = (char)(lstTmp.Last() - 1);
                lstTmp.RemoveAt(lstTmp.Count - 1);
                lstTmp.Add(tmp);
                lstValue = lstTmp;
                break;
        }
        return lstValue;
    }






    List<char> lstGetDecrTemp(char chrTemp, List<char> lstTmp, List<char> lstVal)//shifting places eg unit to ten,etc.
    {
        if (lstTmp.Count == 1)
        {
            lstTmp.Clear();
            lstTmp.Add('-');
            return lstTmp;
        }
        lstTmp.RemoveAt(lstTmp.Count - 1);
        lstVal = lstGetDecrName(lstTmp);
        lstVal.Insert(lstVal.Count, chrTemp);
        return lstVal;
    }

我真的需要帮助。请帮帮我突破这个难关。

- vaibhav

---

+1：非常有趣的问题。我已经在下面发布了一个可行的解决方案。我的排除代码中存在一个错误，但应该很容易修复。 - iCollect.it Ltd

Answer 1

您试图解决的问题实际上是如何递减一个字符序列的离散部分，每个部分都有自己的计数系统，每个部分之间由字母和数字之间的更改分隔。一旦确定了这一点，问题的其余部分就很容易解决。

跳过不想要的字符只需在结果中重复递减即可。

一个困难是序列的含义不明确。例如，当您到达A00时该怎么办？下一个是“ A”还是“-”？为了论证，我假设实际应用基于Excel单元格名称（即每个部分独立操作）。

下面的代码完成了您所需的95％，但是在排除代码中存在错误。例如，"ABB"变成了"AAY"。我觉得需要在更高层次上应用排除（例如，重复递减直到没有字符在排除列表中），但我现在没有时间完成它。此外，当它倒数到零时会产生空字符串，而不是您想要的“ -”，但这很容易在过程结束时添加。

第1部分（将问题划分为部分）：

public static string DecreaseName( string name, string exclusions )
{
    if (string.IsNullOrEmpty(name))
    {
        return name;
    }

    // Split the problem into sections (reverse order)
    List<StringBuilder> sections = new List<StringBuilder>();
    StringBuilder result = new StringBuilder(name.Length);
    bool isNumeric = char.IsNumber(name[0]);
    StringBuilder sb = new StringBuilder();
    sections.Add(sb);
    foreach (char c in name)
    {
        // If we change between alpha and number, start new string.
        if (char.IsNumber(c) != isNumeric)
        {
            isNumeric = char.IsNumber(c);
            sb = new StringBuilder();
            sections.Insert(0, sb);
        }
        sb.Append(c);
    }

    // Now process each section
    bool cascadeToNext = true;
    foreach (StringBuilder section in sections)
    {
        if (cascadeToNext)
        {
            result.Insert(0, DecrementString(section, exclusions, out cascadeToNext));
        }
        else
        {
            result.Insert(0, section);
        }
    }

    return result.ToString().Replace(" ", "");
}

第二部分（减少给定字符串）：

private static string DecrementString(StringBuilder section, string exclusions, out bool cascadeToNext)
{
    bool exclusionsExist = false;
    do
    {
        exclusionsExist = false;
        cascadeToNext = true;
        // Process characters in reverse
        for (int i = section.Length - 1; i >= 0 && cascadeToNext; i--)
        {
            char c = section[i];
            switch (c)
            {
                case 'A':
                    c = (i > 0) ? 'Z' : ' ';
                    cascadeToNext = (i > 0);
                    break;
                case 'a':
                    c = (i > 0) ? 'z' : ' ';
                    cascadeToNext = (i > 0);
                    break;
                case '0':
                    c = (i > 0) ? '9' : ' ';
                    cascadeToNext = (i > 0);
                    break;
                case ' ':
                    cascadeToNext = false;
                    break;
                default:
                    c = (char)(((int)c) - 1);
                    if (i == 0 && c == '0')
                    {
                        c = ' ';
                    }
                    cascadeToNext = false;
                    break;
            }
            section[i] = c;
            if (exclusions.Contains(c.ToString()))
            {
                exclusionsExist = true;
            }
        }
    } while (exclusionsExist);
    return section.ToString();
}

当然，可以更有效地进行分割，只需将起始和结束索引传递给DecrementString即可。但是这种方法更易于编写和理解，在实际情况下速度并不会慢太多。

- iCollect.it Ltd

---

我不喜欢你的字典。它在语义上误用了 KeyValuePair，需要将 string 转换为 char，容易出现拼写错误（'Z' => "X"，'0' => ""？），需要比获取所需的 char 和 bool 的简单方法更多的代码行数（即使在你提供的简短形式中也是如此），甚至可能比这样的方法性能更差。 - Rawling

@Rawling：当时代码还在进行中，因此有些错别字。现已转为仅使用代码的方法。 - iCollect.it Ltd

如果我有机会修复它的话，我会修复它的（我可以在自己的项目中使用它进行文件名递增）。 我目前正在运行一个winforms测试应用程序。 - iCollect.it Ltd

@HiTechMagic，看看我发布的代码吧。目前看来它是最合适的选择，也没有发现任何错误。 - vaibhav

@HiTechMagic，性能并不是太大的问题（至少在我的情况下）。 你的代码非常好。但问题是我有自己的时间表要维护，所以我不能太专注于你给出的代码。如果我有更多时间来投入它，我肯定会仔细阅读你的代码，因为这个流程可以清楚地说明正在发生的工作。 无论如何，我希望我的逻辑可以在其他方面对你有所帮助。 :) - vaibhav

Answer 2

进行检查，如果是数字，则执行减法运算，如果是字符串，则将其转换为字符代码，然后将字符代码减1。

- JohnnBlade

---

这并不像看起来那么容易，@Johnn，当我开始为此编写逻辑时，我也有同样的感觉。但是所需的复杂性并不容易弄清楚。 - vaibhav

我写了一段代码来生成可能的单词列表，但我的代码增加了数量而不是减少。 - JohnnBlade

这就是问题最令人沮丧的部分，先生……增加不是问题，减少才是。我已经有完美运行的增加数值的代码，但我的“减少”代码非常有 bug。 - vaibhav

Answer 3

不为你编写所有的代码，这里提供一个建议，让你了解如何分解它：

char DecrementAlphaNumericChar(char input, out bool hadToWrap)
{
    if (input == 'A')
    {
        hadToWrap = true;
        return 'Z';
    }
    else if (input == '0')
    {
        hadToWrap = true;
        return '9';
    }
    else if ((input > 'A' && input <= 'Z') || (input > '0' && input <= '9'))
    {
        hadToWrap = false;
        return (char)((int)input - 1);
    }
    throw new ArgumentException(
        "Characters must be digits or capital letters",
        "input");
}

char DecrementAvoidingProhibited(
    char input, List<char> prohibited, out bool hadToWrap)
{
    var potential = DecrementAlphaNumericChar(input, out hadToWrap);
    while (prohibited.Contains(potential))
    {
        bool temp;
        potential = DecrementAlphaNumericChar(potential, out temp);
        if (potential == input)
        {
            throw new ArgumentException(
                "A whole class of characters was prohibited",
                "prohibited");
        }
        hadToWrap |= temp;
    }
    return potential;
}

string DecrementString(string input, List<char> prohibited)
{
    char[] chrs = input.ToCharArray();
    for (int i = chrs.Length - 1; i >= 0; i--)
    {
        bool wrapped;
        chrs[i] = DecrementAvoidingProhibited(
                      chrs[i], prohibited, out wrapped);
        if (!wrapped)
            return new string(chrs);
    }
    return "-";
}

这里唯一的问题是它会将例如A10缩减为A09而不是A9。我个人更喜欢这样，但应该很容易编写一个最终步骤来删除多余的零。

为了获得更好的性能，请用Hashset<char>替换List<char>，它们应该允许更快的Contains查找。

- Rawling

---

不错，建议很好。我将会应用这个并且寻找一个解决你最后一个指针的方法。 - vaibhav

Answer 4

昨天我一直在想这个问题，所以我有一个想法。请注意，这只是伪代码，没有经过测试，但我认为这个想法是有效的，并且应该可以工作（需要进行一些修改）。

主要思路是直接定义你的“字母表”，并指定其中哪些字符是非法的，应该跳过，然后使用该字母表中的位置列表或数组来定义你要开始的单词。

我现在不能再花更多时间在这上面了，但如果你决定使用它并让它工作，请告诉我！

string[] alphabet = {a, b, c, d, e};
string[] illegal = {c, d};


public string ReduceString(string s){
            // Create a list of the alphabet-positions for each letter:
    int[] positionList = s.getCharsAsPosNrsInAlphabet();
    int[] reducedPositionList = ReduceChar(positionList, positionList.length);

    string result = "";
    foreach(int pos in reducedPositionList){
        result += alphabet[pos];
    }

    return result;
}


public string ReduceChar(string[] positionList, posToReduce){
    int reducedCharPosition = ReduceToNextLegalChar(positionList[posToReduce]);
    // put reduced char back in place:
    positionList[posToReduce] = reducedCharPosition; 

    if(reducedCharPosition < 0){
        if(posToReduce <= 0){
            // Reached the end, reduced everything, return empty array!:
            return new string[](); 
        }
        // move to back of alphabet again (ie, like the 9 in "11 - 2 = 09"):
        reducedCharPosition += alphabet.length;     
        // Recur and reduce next position (ie, like the 0 in "11 - 2 = 09"):
        return ReduceChar(positionList, posToReduce-1); 
    }

    return positionList;
}


public int ReduceToNextLegalChar(int pos){
    int nextPos = pos--;
    return (isLegalChar(nextPos) ? nextPos : ReduceToNextLegalChar(nextPos));
}


public boolean IsLegalChar(int pos){
        return (! illegal.contains(alphabet[pos]));
}
enter code here

- Kjartan

---

我很感激你所付出的努力。是的，没错，在伪代码中你试图表达的想法正是实际工作流应该遵循的。我已经以类似的方式实现了我的代码。:) 只是我需要使我的代码更加严格以消除bug，而我已经在做了。 - vaibhav

Answer 5

我找到了解决方案，并使用其他解决方法。

调用函数：

    MyFunction()
    {
        //stuff I do before
        strValue = lstGetDecrName(strValue.ToList());//decrease value here
        if (strValue.Contains('-'))
        {
            strValue = "-";
        }
        //stuff I do after
    }

总共有4个函数。2个主要函数和2个辅助函数。

    List<char> lstGetDecrName(List<char> lstVal)//entry point, returns decreased value
    {
        if (lstVal.Contains('-'))
        {
            return "-".ToList();
        }
        List<char> lstTmp = lstVal;
        subCheckEmpty(ref lstTmp);
        switch (lstTmp.Count)
        {
            case 0:
                lstTmp.Add('-');
                return lstTmp;
            case 1:
                if (lstTmp[0] == '-')
                {
                    return lstTmp;
                }
                break;
            case 2:
                if (lstTmp[1] == '0')
                {
                    if (lstTmp[0] == '1')
                    {
                        lstTmp.Clear();
                        lstTmp.Add('9');
                        return lstTmp;
                    }
                    if (lstTmp[0] == 'A')
                    {
                        lstTmp.Clear();
                        lstTmp.Add('-');
                        return lstTmp;
                    }
                }
                if (lstTmp[1] == 'A')
                {
                    if (lstTmp[0] == 'A')
                    {
                        lstTmp.Clear();
                        lstTmp.Add('Z');
                        return lstTmp;
                    }
                }
                break;
        }

        List<char> lstValue = new List<char>();
        switch (lstTmp.Last())
        {
            case 'A':
                lstValue = lstGetDecrTemp('Z', lstTmp, lstVal);
                break;
            case 'a':
                lstValue = lstGetDecrTemp('z', lstTmp, lstVal);
                break;
            case '0':
                lstValue = lstGetDecrTemp('9', lstTmp, lstVal);
                break;
            default:
                char tmp = (char)(lstTmp.Last() - 1);
                lstTmp.RemoveAt(lstTmp.Count - 1);
                lstTmp.Add(tmp);
                subCheckEmpty(ref lstTmp);
                lstValue = lstTmp;
                break;
        }
        lstGetDecrSkipValue(lstValue);
        return lstValue;

    }


    List<char> lstGetDecrSkipValue(List<char> lstValue)
    {
        bool blnSkip = false;
        foreach (char tmpChar in lstValue)
        {
            if (lstChars.Contains(tmpChar))
            {
                blnSkip = true;
                break;
            }
        }
        if (blnSkip)
        {
            lstValue = lstGetDecrName(lstValue);
        }
        return lstValue;
    }


    void subCheckEmpty(ref List<char> lstTmp)
    {
        bool blnFirst = true;
        int i = -1;
        foreach (char tmpChar in lstTmp)
        {
            if (char.IsDigit(tmpChar) && blnFirst)
            {
                i = tmpChar == '0' ? lstTmp.IndexOf(tmpChar) : -1;
                if (tmpChar == '0')
                {
                    i = lstTmp.IndexOf(tmpChar);
                }
                blnFirst = false;
            }
        }
        if (!blnFirst && i != -1)
        {
            lstTmp.RemoveAt(i);
            subCheckEmpty(ref lstTmp);
        }
    }


    List<char> lstGetDecrTemp(char chrTemp, List<char> lstTmp, List<char> lstVal)//shifting places eg unit to ten,etc.
    {
        if (lstTmp.Count == 1)
        {
            lstTmp.Clear();
            lstTmp.Add('-');
            return lstTmp;
        }
        lstTmp.RemoveAt(lstTmp.Count - 1);
        lstVal = lstGetDecrName(lstTmp);
        lstVal.Insert(lstVal.Count, chrTemp);
        subCheckEmpty(ref lstVal);
        return lstVal;
    }

- vaibhav