1

文字列内の文字を頻度の順に、次にアルファベット順に並べ替えるアルゴリズムを作成しようとしています。たとえば、「apple」は「aelpp」になります。「バナナ」は「bnnaaa」になります。

私はさまざまな言語を知っていますが、今のところPythonを使用してコーディングしています。これは私がこれまでに持っているものですが、周波数ソートがないため機能しません。

def order(word):
  word = word.lower()
  storage = [0] * 26
  for c in word:
    storage[ord(c) - 97] += 1
  newWord = []
  for l, c in enumerate(storage):
    for i in range(0, storage[l]):
      newWord.append(chr(l + 97))
  return ''.join(newWord)

このアルゴリズムを最も効率的に正しく実装する方法について何かアドバイスはありますか？

4

2 に答える 2

2

これは、Pythonでこの問題に対処する方法の（ほとんど）Pythonの例です。コメントが何が起こっているのかを説明するのに十分であることを願っています：

words = ["apples", "banannas", "oranges"]

def main():
    # our list of jumbled words
    jumbled = []
    for word in words:
        # dictionary of letter / frequency pairs.
        letters = {};
        # get letter frequency
        for letter in word:
            if letter in letters:
                letters[letter] += 1
            else:
                letters[letter] = 1
        # sort the letter / frequency pairs on descending frequency
        jumbled_word = sorted(letters.items(), key = lambda x: x[1],
                                                              reverse = True)
        # join the letters back together and add to our jumbled words
        jumbled.append(''.join([x[0] for x in jumbled_word]))
        letters = {}

    # print out the jumbled words in alphabetical order
    for x in sorted(jumbled):
        print x

if __name__=="__main__":
    main()

この実装では、大文字が大文字のままになります。

于 2012-10-18T04:10:28.410 に答える
1

頻度については、使用する一般的なツールはハッシュテーブル（Pythonの辞書）です。私はPythonにそれほど自信がないので、疑似コードをいくつか紹介します

hashtable table
for character in string
  table[character] +=1;
list partiallySorted = alphabetize(table.keys()) 
list sortedList = stablesort partiallySorted by (table[a]<table[b] iff a<b)

安定ソートは、等しい要素間の相対的な順序を維持するため、順序が維持されます。

幸いなことに、Python 2.2ではすべての並べ替えが安定していることが保証されているため、自分で実装したくない場合は、ライブラリの並べ替え関数を呼び出して安定した並べ替えを行うことができます。

于 2012-10-18T03:59:21.630 に答える