코딩도장 - 단어찾기

출처 : http://club.filltong.net/codingdojo/23148

a,b,c,d,e,f,g,h 의 8 개의 영문자로 만들 수 있는 순열(permutation)의 개수는 8!=40,320 이다.

이 순열들을 사전 순서로 배열하고 이들의 순서를 적어보면 아래와 같다.

문자열 순서 

abcdefgh	1
abcdefhg	2
abcdegfh	3
..	.
fbhacdeg	26521
..	.
hgfedcba	40320

이렇게 8 개의 영문자로 만들어진 순열이 주어질 때,이 순열이 몇 번째에 나오는지를 출력하는 프로그램을 작성하라. 

--------------------------------------------------------------------------------------------------------

아.. 다른분들 푼거 보니 itertools를 써서 간단히 푼것도 있던데..

첨부터 itertools가 있는지도 몰랐으니.. 머리가 부족하니 몸이 고생이다ㅠ

풀기는 했지만.. python을 제대로 사용할지 모르는 상태에서 하다보니 코드가 상당히 지저분하고 엉망이다

더군다나 성능은 완전.. 12초나 걸리다니.. 좀더 연습해서 파이썬 답게 만들어야겠다.

import unittest
import copy

class Words:
    def __init__(self):
        self.pumatationWordList = []
    def getPermutationWordList(self):
        return self.pumatationWordList
    def getPermutationCount(self, findWord ):
        for i in range( 0, len(self.pumatationWordList) ):
            curWord = self.pumatationWordList[i]
            if curWord == findWord:
                return i+1   
        return -1        
    def permutation( self, wordList, words = [] ):
        for i in range( 0, len(wordList) ):
            tmpResultWord = copy.deepcopy( words )
            tmpWordList = copy.deepcopy( wordList )
            curWord = wordList[i]
            tmpWordList.remove( wordList[i] )
            if( len(tmpWordList) != 0 ):
                tmpResultWord.append( curWord )
                self.permutation( tmpWordList, tmpResultWord )
            else:
                tmpResultWord.append( curWord )
                self.pumatationWordList.append( "".join(tmpResultWord) ) 

def getWord( inputWord ):
    inputWordList = []
    for i in range( 0, len(inputWord) ):
        inputWordList.append( inputWord[i] )
    words = Words()
    words.permutation(inputWordList)
    return words.getPermutationWordList()

def getWordCount( targetWordList, findWord ):
    inputWordList = []
    for i in range( 0, len(targetWordList) ):
        inputWordList.append( targetWordList[i] )
    words = Words()
    words.permutation(inputWordList)
    return words.getPermutationCount(findWord)
    
class Test( unittest.TestCase ):
    def test_findwords(self):
        self.assertEquals( [ 'a' ] , getWord( 'a' ) );
        self.assertEquals( [ 'ab', 'ba' ], getWord( 'ab' ) )
        self.assertEquals( ['abc', 'acb', 'bac', 'bca', 'cab', 'cba'] , getWord( 'abc' ) )
        self.assertEquals( ['abcd', 'abdc', 'acbd', 'acdb', 
                            'adbc', 'adcb', 'bacd', 'badc', 
                            'bcad', 'bcda', 'bdac', 'bdca', 
                            'cabd', 'cadb', 'cbad', 'cbda', 
                            'cdab', 'cdba', 'dabc', 'dacb', 
                            'dbac', 'dbca', 'dcab', 'dcba'], getWord( 'abcd' ) )
    def test_findWordCount(self):
        self.assertEquals( 1, getWordCount( 'a', 'a' ) );
        self.assertEquals( 2, getWordCount( 'ab', 'ba' ) );
        self.assertEquals( 24, getWordCount( 'abcd', 'dcba' ) );
        self.assertEquals( 2, getWordCount( 'abcdefgh', 'abcdefhg' ) );
        self.assertEquals( 40320, getWordCount( 'abcdefgh', 'hgfedcba' ) );
        self.assertEquals( 26521, getWordCount( 'abcdefgh', 'fbhacdeg' ) );
        
if __name__ == "__main__":
    unittest.main()