12

私は Stack Overflow を調べましたが、何も機能させることができませんでした。露骨に明らかな投稿を見逃した場合は、お詫び申し上げます。

電話番号を取得し、考えられるすべての単語の組み合わせを取得して、それをテキスト ファイルに書き込むという学校の問題がありました。私はそれを行い、私の課題に対して完全な単位を取得しました. ネストされた 7 つのループでこれを行うことができましたが、これはあまりエレガントではなく、非常に厳格です。私は圧倒され、教科書的な解決策が 7 つのネストされたループであることに完全に失望しました。私のインストラクターも答えを持っていませんでした。

さまざまなアプローチを試しましたが、ダイヤルインできませんでした。再帰とキルポイントを特定しましたが、機能させることができませんでした。文字列を作成することはできますが、本来あるべき数にはほど遠いものです。失敗した思考プロセスを確認できるように、試みをコメントアウトしました :) ご覧になり、アイデアがあればお知らせください。

public partial class TelephoneWorderizer : Form
{
    protected Dictionary<int, IEnumerable<string>> KeyMappings = new Dictionary<int, IEnumerable<string>>();
    protected string[][] ActiveLettersGroups = null;
    protected List<string> Words = new List<string>();
    protected List<string> RecursiveWords = new List<string>();
    protected int Iteration = 0;

    public TelephoneWorderizer()
    {
        InitializeComponent();

        this.KeyMappings = this.GetKeyMappings();
    }

    private void btnGetWords_Click(object sender, EventArgs e)
    {
        string textBoxContent = textBoxNumber.Text;

        int[] digits = this.GetPhoneNumbers(textBoxContent);

        List<string> words = this.GetWords(digits);

        using (StreamWriter writer = new StreamWriter(@"E:\words.txt"))
        {
            foreach (var word in words)
            {
                writer.WriteLine(word);
            }
        }

        textBoxNumber.Clear();
    }

    private List<string> GetWords(int[] digits)
    {
        List<string[]> letterGroupings = new List<string[]>();

        //digits array of numbers
        for (int i = 0, j = digits.Length; i < j; i++)
        {
            int digit = digits[i];

            //if the number has a letter group mapped to it
            if (this.KeyMappings.ContainsKey(digit))
            {
                // letters mapped to a given number
                letterGroupings.Add(this.KeyMappings[digit].ToArray());
            }
        }

        this.WordMakerLoop(letterGroupings);
        //this.WordMaker(letterGroupings);

        return this.Words;
        //return this.RecursiveWords;
    }

    //private void RecursionTest(string word, List<string[]> groups, int letterCtr, int groupCtr)
    //{
    //    string[] Group = groups[groupCtr];

    //    word += Group[letterCtr];

    //    letterCtr += 1;

    //    if (letterCtr < Group.Length - 1)
    //    {
    //        letterCtr = 0;
    //        groupCtr += 1;

    //        // Hit bottom
    //        if (groupCtr == groups.Count - 1)
    //        {
    //            groupCtr -= 1;
    //        }

    //        RecursionTest(word, groups, letterCtr, groupCtr);
    //    }
    //}

    private void WordMaker(List<string[]> letterCollections)
    {
        string newword = "";
        int numberLength = letterCollections.Count;

        this.ActiveLettersGroups = letterCollections.ToArray();

        string[] letterGroup = this.ActiveLettersGroups[0];

        this.RecursiveGetWords(newword, 0, 0);
    }

    /// <summary>
    /// 
    /// </summary>
    /// <param name="word"></param>
    /// <param name="groupIndex"></param>
    /// <param name="letterIndex"></param>
    private void RecursiveGetWords(string word, int groupIndex, int letterIndex)
    {

        /*
         * 
         * 
         * 
         */


        var numActiveLetterGroups = this.ActiveLettersGroups.Length;

        if (this.ActiveLettersGroups.Length > 0 && this.Iteration < numActiveLetterGroups)
        {
            if (groupIndex < numActiveLetterGroups)
            {
                var letters = this.ActiveLettersGroups[groupIndex]; // Picks the a letter group ex: A, B, C 

                if (letterIndex < letters.Length)
                {
                    //var letter1 = letters.Select(x => 
                    string letter = letters[letterIndex]; // Picks a letter from the group ex: A

                    word += letter;

                    this.RecursiveGetWords(word, groupIndex + 1, this.Iteration);
                }
                else
                {
                    //this.RecursiveWords.Add(word);
                    //word = "";

                    //this.RecursiveGetWords(word, 0, 1);
                }
            }
            else
            {
                this.RecursiveWords.Add(word);
                word = "";
                this.Iteration++;

                this.RecursiveGetWords(word, 0, this.Iteration);
            }
        }
    }

    #region
    private void WordMakerLoop(List<string[]> letterGroups)
    {
        string word = "";

        // array of string[]
        var newGroup = letterGroups.ToArray();

        //grabs a letter group
        for (int i = 0; i < newGroup.Length; i++)
        {
            var letterGroup1 = newGroup[i];

            //grabs a letter from group 1
            for (int j = 0; j < letterGroup1.Length; j++)
            {
                string letter1 = letterGroup1[j];

                if (i + 1 < newGroup.Length)
                {
                    var letterGroup2 = newGroup[i + 1];

                    //grabs a letter from group 2
                    for (int k = 0; k < letterGroup2.Length; k++)
                    {
                        string letter2 = letterGroup2[k];

                        if (i + 2 < newGroup.Length)
                        {
                            var letterGroup3 = newGroup[i + 2];

                            //grabs a letter from group 3
                            for (int l = 0; l < letterGroup3.Length; l++)
                            {
                                string letter3 = letterGroup3[l];

                                if (i + 3 < newGroup.Length)
                                {
                                    var letterGroup4 = newGroup[i + 3];

                                    //grabs a letter from group 4
                                    for (int m = 0; m < letterGroup4.Length; m++)
                                    {
                                        string letter4 = letterGroup4[m];

                                        if (i + 4 < newGroup.Length)
                                        {
                                            var letterGroup5 = newGroup[i + 4];

                                            //grabs a letter from group 5
                                            for (int n = 0; n < letterGroup5.Length; n++)
                                            {
                                                string letter5 = letterGroup5[n];

                                                if (i + 5 < newGroup.Length)
                                                {
                                                    var letterGroup6 = newGroup[i + 5];

                                                    //grabs a letter from group 6
                                                    for (int o = 0; o < letterGroup6.Length; o++)
                                                    {
                                                        string letter6 = letterGroup6[o];

                                                        if (i + 6 < newGroup.Length)
                                                        {
                                                            var letterGroup7 = newGroup[i + 6];

                                                            //grabs a letter from group 6
                                                            for (int p = 0; p < letterGroup7.Length; p++)
                                                            {
                                                                string letter7 = letterGroup7[p];

                                                                word = letter1 + letter2 + letter3 + letter4 + letter5 + letter6 + letter7;
                                                                this.Words.Add(word);
                                                                word = "";
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    // Sanitizes input text and converts the string into and arra of int
    private int[] GetPhoneNumbers(string content)
    {
        int[] phoneNumbers = null;

        string cleanString = this.SanitizeString(content);

        int numbers;

        if (Int32.TryParse(cleanString, out numbers))
        {
            //phoneNumbers = this.GetIntArray(numbers).OfType<int>().ToList();
            phoneNumbers = this.GetIntArray(numbers);
        }

        return phoneNumbers;
    }

    // Removes potential unwanted characters from the phone number
    private string SanitizeString(string content)
    {
        content = content.Replace("-", "");
        content = content.Replace("(", "");
        content = content.Replace(")", "");

        return content;
    }

    //breaks a number into an array of its individual digits
    private int[] GetIntArray(int num)
    {
        List<int> listOfInts = new List<int>();

        while (num > 0)
        {
            listOfInts.Add(num % 10);
            num = num / 10;
        }

        listOfInts.Reverse();

        return listOfInts.ToArray();
    }

    //gets the mappings for the numerical values
    private Dictionary<int, IEnumerable<string>> GetKeyMappings()
    {
        List<string> alphabet = new List<string>() { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z" };
        Dictionary<int, IEnumerable<string>> mappings = new Dictionary<int, IEnumerable<string>>();

        for (int i = 0; i < 10; i++)
        {
            string[] letters = null;
            switch (i)
            {
                case 0:
                case 1:
                    break;
                case 2:
                case 3:
                case 4:
                case 5:
                case 6:
                case 8:
                    letters = alphabet.Take(3).ToArray();
                    mappings.Add(i, letters);
                    alphabet.RemoveRange(0, 3);
                    break;
                case 7:
                case 9:
                    letters = alphabet.Take(4).ToArray();
                    mappings.Add(i, letters);
                    alphabet.RemoveRange(0, 4);
                    break;
                default:
                    break;
            }
        }

        return mappings;
    }
    #endregion
}

疑わしい人たちのために、学校の割り当ては終わったことを強調させてください。これをもっとうまく、効率的にしたい。それが役立つ場合は、プロジェクトを gitHub に投稿できます。

4

5 に答える 5

3

私は今のところコードを書くのが面倒ですが、7 つのネストされたループの代わりに再帰を介してこれを行うことができるはずです。実際、任意の長さの電話で動作するメソッドを設計できるはずです。番号。

基本的な考え方は、次のような再帰メソッドを設計することです。

void recurse(String phone, int index, StringBuilder sb)
{
   // Get the number at position phone[index]
   // Loop through the possible letters for that particular number (eg. A, B, C):
      // Add the letter to the StringBuilder
      // Call recurse(phone, index + 1, sb)
      // Subtract last letter from the StringBuilder
}

再帰するたびに、次の数字/文字の位置に取り組んでいます。

もちろん、終了条件 (sb length == phone length) に遭遇した場合は、再帰する代わりに、StringBuilder の現在の値をファイルに書き込んで返します。

お役に立てれば。

編集：実際にいくつかのコードを書いてみましょう。本当にシンプルで、LINQ は必要ありません。

   class Program
   {
      static Dictionary<Char, String> DigitMap = new Dictionary<Char, String>()
      {
         {'0', "0"},
         {'1', "1"},
         {'2', "ABC"},
         {'3', "DEF"},
         {'4', "GHI"},
         {'5', "JKL"},
         {'6', "MNO"},
         {'7', "PQRS"},
         {'8', "TUV"},
         {'9', "WXYZ"}
      };

      static void Main(string[] args)
      {
         String phone = Regex.Replace("867-5309", "[^0-9]", "");
         recurse(phone, 0, new StringBuilder());
      }

      static void recurse(String phone, int index, StringBuilder sb)
      {
         // Terminating condition
         if (index == phone.Length)
         {
            Console.WriteLine(sb.ToString());
            return;
         }

         // Get digit and letters string
         Char digit = phone[index];
         String letters = DigitMap[digit];

         // Loop through all letter combinations for digit
         foreach (Char c in letters)
         {
            sb.Append(c);
            recurse(phone, index + 1, sb);
            sb.Length -= 1;
         }
      }
   }
}

このコード (単純なコンソール アプリを作成した場所) では、単に単語をコンソールに書き込んでいますが、文字列を配列に追加したり、代わりにディスクに書き込んだりできます。

于 2012-11-27T00:21:17.500 に答える
2

通常のすべての文字マッピングに加え0て、+. そこで、マッピングを処理するためにこの辞書を作成しました。

var map = new Dictionary<char, string>()
{
    { '0', "+0"},
    { '1', "1" },
    { '2', "2ABC"},
    { '3', "3DEF"},
    { '4', "4GHI"},
    { '5', "5JKL"},
    { '6', "6MNO"},
    { '7', "7PQRS"},
    { '8', "8TUV"},
    { '9', "9WXYZ"},
};

私の順列関数は次のようになります。

Func<IEnumerable<char>, IEnumerable<IEnumerable<char>>> permutate = null;
permutate = cs =>
{
    var result = Enumerable.Empty<IEnumerable<char>>();
    if (cs.Any())
    {
        result = map[cs.First()].Select(c => new [] { c });
        if (cs.Skip(1).Any())
        {
            result =
                from xs in result
                from ys in permutate(cs.Skip(1))
                select xs.Concat(ys);
        }
    }
    return result;
};

それでおしまい。

次のように使用できます。

var digits = "(08) 8234-5678"
    .Where(x => char.IsDigit(x));

var results =
    permutate(digits)
        .Select(x => new string(x.ToArray()));

結果は、各文字列が入力数値の順列である文字列のリストです。

数字を数字にマップしたくない場合は、元の辞書定義からそれらを削除するだけですが、1それが機能するために数字の単一の文字を保持する必要があります。

これがうまくいくかどうか教えてください。

于 2012-11-27T06:19:51.377 に答える
0

これが非再帰的な解決策です。

  • 数値を指定して、その最初の単語を計算します
  • 与えられた単語を「インクリメント」して次の単語を見つける
public static class TelephoneFinder
{
    static char[] firstDigits = new char[]
                   { '0', '1', 'A', 'D', 'G', 'J', 'M', 'P', 'T', 'W' };
    public static string First(string number)
    {
        char[] firstWord = new char[number.Length];
        for (int i = 0; i < number.Length; i++)
        {
            var c = number.Substring(i, 1);
            firstWord[i] = firstDigits[int.Parse(c)];
        }
        return new String(firstWord);
    }

    static Dictionary<char, char> rollovers = new Dictionary<char, char> { 
        { '1', '0' }, { '2', '1' }, { 'D', 'A' }, { 'G', 'D' }, { 'J', 'G' },
        { 'M', 'J' }, { 'P', 'M' }, { 'T', 'P' }, { 'W', 'T' }, { '[', 'W' } };
    public static string Next(string current)
    {
        char[] chars = current.ToCharArray();
        for (int i = chars.Length - 1; i >= 0; i--)
        {
            // Increment current character
            chars[i] = (char)((int)chars[i] + 1);

            if (rollovers.ContainsKey(chars[i]))
                // Roll current character over
                // Will then continue on to next character
                chars[i] = rollovers[chars[i]];
            else
                // Finish loop with current string
                return new String(chars);
        }
        // Rolled everything over - end of list of words
        return null;
    }
}

などと呼ばれる

string word = TelephoneFinder.First("867");
while (!String.IsNullOrEmpty(word))
{
    Console.WriteLine(word);
    word = TelephoneFinder.Next(word);
}

おそらくいくつかの片付けが必要になる可能性がありますが、これは一般的な非再帰的なソリューションであり、同様の「交差積」の状況で機能するように変更できます。

于 2012-11-27T09:02:57.433 に答える
0

これは、Javaish 疑似 codeish 再帰関数です。

void recWords(String number, int ind, String buf, Collection<String> result){
  if(ind==number.length()) {
    result.add(buf);
  } else {
    for(char letter : lettersForNumber(number.charAt(ind)) {
      recWords(number, ind+1, buf+letter, result);
    }
  }
}

上記を C# として記述し、それをコードに適合させた後のさらなる演習:

  1. bufからString1 つの共有 に変更しStringBuilderます。
  2. 次に、これをクラスにラップし、再帰で ind のみを渡し、他のものをクラス メンバー変数として持ちます。
  3. 最後に、再帰をループに変えます (ヒント: 3 つのネストされたループ。内側のループの 1 つで反復回数が増えます)。

私が考えている非再帰バージョンについての注意: 再帰よりも効率的ではありませんが、この再帰バージョンは深さ優先であるのに対し、それは幅優先であり、演習としてコーディングする価値があります。

于 2012-11-27T04:52:26.983 に答える
0

申し訳ありません。これは私の最初の Stack Overflow 投稿であり、質問への回答が投稿されたときにメールが届くことを期待していましたが、メールが届きませんでした。私の質問がスタックオーバーフローの深淵に飲み込まれたと思いました。

私が一緒に働いている開発者のグループは、これを約 5 行で理解しました。現時点では解決策を見つけることができないようですが、エニグマティビティが投稿したものに非常に近いと思います. 順列を使用したことは確かです。私たちが使用した解決策を探します。みんな、ありがとう。

于 2013-03-07T14:57:04.997 に答える