順列を作るプログラム

先日のcodejamで痛い目にあったので、今更だけど書いてみた。

思ったよりあっさり書けて唖然。ただしDeepCopyしてたりして効率は良くないと思う。

def p(str):
    print str
    
def permutation(array):
    """
        make permutation list
        >>> permutation(['a','b'])
        ['ab', 'ba']
        >>> permutation(['a', 'b', 'c'])
        ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
        >>> permutation([1,0,5,1])
        ['0115', '0151', '0511', '1015', '1051', '1105', '1150', '1501', '1510',
 '5011', '5101', '5110']

    """

    def perm(answer,array,answers):    
        """
            p("answer,array,answers="),                                         
            p(answer),
            p(array),
            p(answers)                                                          
        """
        if len(array) == 0:                             
            strs = "" 
            for ans in answer:                                                  
                strs += str(ans)                                                
            #p(str)  
            if strs not in answers: answers.append(strs)                        
            return
        for a in array:                       
            tmpAnswer = answer[:]             
            tmpArray = array[:]
            tmpAnswer.append(a)
            tmpArray.remove(a)
            perm(tmpAnswer, tmpArray, answers)  
    
    answers = []
    array.sort()
    perm([],array,answers)
    p(answers)

if __name__ == "__main__":
    import doctest
    doctest.testmod()

実行結果

$ python permutation.py -v

Trying:
    permutation(['a','b'])
Expecting:
    ['ab', 'ba']
ok
Trying:
    permutation(['a', 'b', 'c'])
Expecting:
    ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
ok
Trying:
    permutation([1,0,5,1])
Expecting:
    ['0115', '0151', '0511', '1015', '1051', '1105', '1150', '1501', '1510', '50
11', '5101', '5110']
ok
2 items had no tests:
    __main__
    __main__.p
1 items passed all tests:
   3 tests in __main__.permutation
3 tests in 3 items.
3 passed and 0 failed.
Test passed.

先日のgoogle code jam 1B-Bならl,permutation(数値→リスト),int(l[i])==数値としたときのl[i+1]を返せばいいと思う。尤もnext_permutationとかは順列全部作るんじゃなくて次の答えができたらそれで打ち切りそうだけど。