sorting question

Greg Jorgensen gregj at
Thu Feb 8 10:39:56 CET 2001

In article <tmlg6.61202$Ch.11526305 at>,
  "dsavitsk" <dsavitsk at> wrote:
> i would like to iterate through all possible combinations of the
> in a string, and i am not thinking very clearly about how to approach
> that is, if the initial string is 'bar', i want to print
> ['bar', 'bra', 'abr', 'arb', 'rba', 'rab']
> any hints?

I adapted Sedgewick's permutation function (from Algorithms in C, pp
628-629). My solution (below) first generates a list of all
permutations of integers in the range (1..n), where n is the length of
the string to be permuted. It then translates the original string into
a list of permutations using the list of integers. Because generating
the list of permuted integers is expensive, you could cache the lists
so you wouldn't have to do it for every 3- or 4-character string.

Note that this process gets very slow and the lists get very long for
even short strings... after five characters you can see the hit.

def visit(k, val, id, v, perms):
    "permutation by exhaustive search, from sedgewick"
    id += 1
    val[k] = id
    if id == v:
        for i in range(v):
            if val[i] == 0:
                visit(i, val, id, v, perms)
    id -= 1
    val[k] = 0

def permutations(n):
    "generate list of all permutations of the integers 1..n"
    perms = []
    val = [0] * n
    visit(0, val, -1, n, perms)
    return perms

def permutestring(s):
    "generate list of all permutations of a string"
    perms = permutations(len(s))
    result = []
    for p in perms:
        t = ""
        for i in p:
            t += s[i-1]
    return result

#print permutations(4)
print permutestring("bar")
print permutestring("abcd")


Greg Jorgensen
Portland, Oregon, USA
gregj at

Sent via

More information about the Python-list mailing list