sorting question

[Greg Jorgensen]

In article <tmlg6.61202$Ch.11526305 at newsrump.sjc.telocity.net>,
  "dsavitsk" <dsavitsk at e-coli.net> wrote:
> i would like to iterate through all possible combinations of the
characters
> in a string, and i am not thinking very clearly about how to approach
this.
> 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:
        perms.append(val[:])
    else:
        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]
        result.append(t)
    return result

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

`````````````````````````````````````


--
Greg Jorgensen
Portland, Oregon, USA
gregj at pobox.com


Sent via Deja.com
http://www.deja.com/