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