Anagram

Andrew Gaul gaul at spam.utexas.edu
Tue Feb 26 03:42:37 EST 2002


In article <3c4e8efc.1036790726 at news.mch.sni.de>, Nikolai Kirsebom wrote:
> Friend of mine who used to work with lisp (and is a bit interested in
> Python) asked me how compact I could write a program to evaluate the
> number of possible combinations a set of characters (string) can be
> written in - handling two identical characters as different
> characters.
> 
> Example:
> "ab" --> yields 2 ("ab", "ba")
> "abc" --> yields 6
> "aa" --> yields 2

My apologies for the delayed reply; I only recently saw your message.
There is a much better way to compute the number of unique permutations;
I'm suprised no one else has posted this (it's standard material in a
university probability course).

def uniq_perm(l):
    ''' returns the number of unique permutations of a list.

                      n!
            ------------------------
            n_1! * n_2! * ... * n_r!

        computes the number of unique permutations of n objects, of which n_1
        are alike, n_2 are alike, ... n_r are alike.  Take from _A First Course
        in Probability_, 5th edition, Ross, pg 5.
    '''

    acc = fac(len(l))
    l.sort()
    i = 0
    while i < len(l):
        cnt = l.count(l[i])
        acc /= fac(cnt)
        i += cnt
    return acc

def fac(n):
    ''' returns n! '''
    assert n >= 0
    if n == 0:
        return 1
    acc = 1
    for i in range(1, n+1):
        acc *= i
    return acc


Python 2.2 (#5, Jan 23 2002, 16:23:03)
[GCC 3.0.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from perm import *
>>> uniq_perm(list('pepper'))
60
>>> uniq_perm(list('aa'))
1
>>> uniq_perm(list('aba'))
3

-- 
Andrew Gaul
http://gaul.org/



More information about the Python-list mailing list