How to generate all permutations of a string?

Discussion in 'Python' started by Girish Sahani, Jun 22, 2006.

  1. Hi guys,
    I want to generate all permutations of a string. I've managed to
    generate all cyclic permutations. Please help :)

    def permute(string):
    l= []
    l.append(string)
    string1 = ''
    for i in range(0,len(string)-1,1):
    string1 = string[1:len(string)] + string[:1]
    l.append(string1)
    string = string1
    return l
     
    Girish Sahani, Jun 22, 2006
    #1
    1. Advertising

  2. In article <>,
    "Girish Sahani" <> wrote:

    > I want to generate all permutations of a string.


    def permute(Seq) :
    """generator which yields successive permutations of the elements
    of Seq."""
    if len(Seq) == 0 :
    yield ()
    else :
    for i in range(0, len(Seq)) :
    for rest in permute(Seq[:i] + Seq[i + 1:]) :
    yield (Seq,) + rest
    #end for
    #end for
    #end if
    #end permute
     
    Lawrence D'Oliveiro, Jun 22, 2006
    #2
    1. Advertising

  3. > In article <>,
    > "Girish Sahani" <> wrote:
    >
    >> I want to generate all permutations of a string.

    >
    > def permute(Seq) :
    > """generator which yields successive permutations of the elements
    > of Seq."""
    > if len(Seq) == 0 :
    > yield ()
    > else :
    > for i in range(0, len(Seq)) :
    > for rest in permute(Seq[:i] + Seq[i + 1:]) :
    > yield (Seq,) + rest
    > #end for
    > #end for
    > #end if
    > #end permute

    thanks lawrence...however this func doesnt return the permuted strings, so
    i added some code as follows to generate a list of all the permutations:

    def permute(seq):
    l = []
    if len(seq) == 0:
    yield []
    else:
    for i in range(0,len(seq)):
    for rest in permute(seq[:i] + seq[i+1:]):
    yield (seq,) + rest
    for t in permute(seq):
    l.append(''.join(t))
    return l

    This gives me a syntax error!
    I need to output a list that has all the permutations of the input string.



    > --
    > http://mail.python.org/mailman/listinfo/python-list
    >
     
    Girish Sahani, Jun 22, 2006
    #3
  4. Girish Sahani

    bayerj Guest

    Mind, that Lawrence's solution may contain doubles:

    >>> [ i for i in permute("aa") ]

    [('a', 'a'), ('a', 'a')]

    If you don't want this, use sets.
     
    bayerj, Jun 22, 2006
    #4
  5. In article <>,
    Girish Sahani <> wrote:
    >Hi guys,
    > I want to generate all permutations of a string. I've managed to
    >generate all cyclic permutations. Please help :)
    >
    >def permute(string):
    > l= []
    > l.append(string)
    > string1 = ''
    > for i in range(0,len(string)-1,1):
    > string1 = string[1:len(string)] + string[:1]
    > l.append(string1)
    > string = string1
    > return l
    >


    Those so passionate about enumerations as to consider *everything*
    known about them, and not just a specific Python function, will
    want to be aware of the referent of <URL:
    http://www.unixreview.com/documents/s=10089/ur0606j/ur0606j.html >
    and related materials.
    and its referents.
     
    Cameron Laird, Jun 22, 2006
    #5
  6. Anton Vredegoor, Jun 22, 2006
    #6
  7. Gerard Flanagan, Jun 22, 2006
    #7
  8. Girish Sahani

    James Stroud Guest

    Girish Sahani wrote:
    >>In article <>,
    >> "Girish Sahani" <> wrote:
    >>
    >>
    >>> I want to generate all permutations of a string.

    >>
    >>def permute(Seq) :
    >> """generator which yields successive permutations of the elements
    >> of Seq."""
    >> if len(Seq) == 0 :
    >> yield ()
    >> else :
    >> for i in range(0, len(Seq)) :
    >> for rest in permute(Seq[:i] + Seq[i + 1:]) :
    >> yield (Seq,) + rest
    >> #end for
    >> #end for
    >> #end if
    >>#end permute

    >
    > thanks lawrence...however this func doesnt return the permuted strings, so
    > i added some code as follows to generate a list of all the permutations:
    >
    > def permute(seq):
    > l = []
    > if len(seq) == 0:
    > yield []
    > else:
    > for i in range(0,len(seq)):
    > for rest in permute(seq[:i] + seq[i+1:]):
    > yield (seq,) + rest
    > for t in permute(seq):
    > l.append(''.join(t))
    > return l
    >
    > This gives me a syntax error!
    > I need to output a list that has all the permutations of the input string.
    >
    >
    >
    >
    >>--
    >>http://mail.python.org/mailman/listinfo/python-list
    >>

    >
    >


    p = ["".join(s) for s in permute('abcdefg')]

    --
    James Stroud
    UCLA-DOE Institute for Genomics and Proteomics
    Box 951570
    Los Angeles, CA 90095

    http://www.jamesstroud.com/
     
    James Stroud, Jun 22, 2006
    #8
  9. >> thanks lawrence...however this func doesnt return the permuted strings,
    >> so
    >> i added some code as follows to generate a list of all the permutations:
    >>
    >> def permute(seq):
    >> l = []
    >> if len(seq) == 0:
    >> yield []
    >> else:
    >> for i in range(0,len(seq)):
    >> for rest in permute(seq[:i] + seq[i+1:]):
    >> yield (seq,) + rest
    >> for t in permute(seq):
    >> l.append(''.join(t))
    >> return l
    >>
    >> This gives me a syntax error!
    >> I need to output a list that has all the permutations of the input
    >> string.
    >>
    >>
    >>
    >>
    >>>--
    >>>http://mail.python.org/mailman/listinfo/python-list
    >>>

    >>
    >>

    >
    > p = ["".join(s) for s in permute('abcdefg')]


    This fails to work too. I'm trying to call permute func from another func,
    python gives me a TypeError as follows:

    def permute(seq):
    l = []
    if len(seq) == 0:
    yield []
    else:
    for i in range(0,len(seq)):
    for rest in permute(seq[:i] + seq[i+1:]):
    yield (seq,) + rest

    def main(stringList):
    for string in stringList:
    permList = list(permute(string))
    l = ["".join(s) for s in permList]

    >>> l = ['abc','abd','bcd']
    >>> main(l)

    TypeError: can only concatenate tuple (not "list") to tuple



    >
    > --
    > James Stroud
    > UCLA-DOE Institute for Genomics and Proteomics
    > Box 951570
    > Los Angeles, CA 90095
    >
    > http://www.jamesstroud.com/
    > --
    > http://mail.python.org/mailman/listinfo/python-list
    >
     
    Girish Sahani, Jun 23, 2006
    #9
  10. Girish Sahani

    James Stroud Guest

    Girish Sahani wrote:
    >>>thanks lawrence...however this func doesnt return the permuted strings,
    >>>so
    >>>i added some code as follows to generate a list of all the permutations:
    >>>
    >>>def permute(seq):
    >>> l = []
    >>> if len(seq) == 0:
    >>> yield []
    >>> else:
    >>> for i in range(0,len(seq)):
    >>> for rest in permute(seq[:i] + seq[i+1:]):
    >>> yield (seq,) + rest
    >>> for t in permute(seq):
    >>> l.append(''.join(t))
    >>> return l
    >>>
    >>>This gives me a syntax error!
    >>>I need to output a list that has all the permutations of the input
    >>>string.
    >>>
    >>>
    >>>
    >>>
    >>>
    >>>>--
    >>>>http://mail.python.org/mailman/listinfo/python-list
    >>>>
    >>>
    >>>

    >>p = ["".join(s) for s in permute('abcdefg')]

    >
    >
    > This fails to work too. I'm trying to call permute func from another func,
    > python gives me a TypeError as follows:
    >
    > def permute(seq):
    > l = []
    > if len(seq) == 0:
    > yield []
    > else:
    > for i in range(0,len(seq)):
    > for rest in permute(seq[:i] + seq[i+1:]):
    > yield (seq,) + rest
    >
    > def main(stringList):
    > for string in stringList:
    > permList = list(permute(string))
    > l = ["".join(s) for s in permList]
    >
    >
    >>>>l = ['abc','abd','bcd']
    >>>>main(l)

    >
    > TypeError: can only concatenate tuple (not "list") to tuple
    >


    I think I should have provided a context for my example. It was to be
    used with Lawrence D'Olivero's code and not yours.

    James

    >>> def permute(Seq) :

    .... """generator which yields successive permutations of the elements
    .... of Seq."""
    .... if len(Seq) == 0 :
    .... yield ()
    .... else :
    .... for i in range(0, len(Seq)) :
    .... for rest in permute(Seq[:i] + Seq[i + 1:]) :
    .... yield (Seq,) + rest
    ....
    >>> def main(stringList):

    .... for string in stringList:
    .... l = ["".join(s) for s in permute(string)]
    .... print l
    ....
    >>> l

    ['abc', 'abd', 'bcd']
    >>> main(l)

    ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
    ['abd', 'adb', 'bad', 'bda', 'dab', 'dba']
    ['bcd', 'bdc', 'cbd', 'cdb', 'dbc', 'dcb']
     
    James Stroud, Jun 23, 2006
    #10
  11. Girish Sahani

    Boris Borcic Guest

    Another generator solution, based on computing a permutation from its rank
    according to some natural order. Written for strings.

    def perms(s) :
    def nth(n,L,k=1) :
    if k>len(L) :
    if n :
    raise StopIteration
    return ''
    return nth(n/k,L,k+1)+L.pop(n%k)
    for n in xrange(1<<30) :
    yield nth(n,list(s))
     
    Boris Borcic, Jun 23, 2006
    #11
  12. Girish Sahani

    Boris Borcic Guest

    I wrote:
    > Another generator solution, based on computing a permutation from its
    > rank according to some natural order. Written for strings.
    >
    > def perms(s) :
    > def nth(n,L,k=1) :
    > if k>len(L) :
    > if n :
    > raise StopIteration
    > return ''
    > return nth(n/k,L,k+1)+L.pop(n%k)
    > for n in xrange(1<<30) :
    > yield nth(n,list(s))


    Same principle, simpler (no recursion, no helper func, less tokens, easier to
    read) :

    def perms(s) :
    for n in xrange(1<<30) :
    R,L = [],list(s)
    while L :
    n,k = divmod(n,len(L))
    R.append(L.pop(k))
    if n : break
    yield ''.join(R)

    Or if you *really* prefer lisp-style recursions, here is the solution as a
    single lambda that returns a tuple of strings (not a generator as above)

    perms = lambda *S : \
    (len(S)>=len(S[0]) and S[0]==S[-1]) \
    and S[min(1,len(S)-1):] \
    or perms(''.join(L.pop(k)
    for n,L in [[len(S),list(S[-1])]]
    for _ in S[0]
    for n,k in [divmod(n,len(L))]
    )
    ,*S)
     
    Boris Borcic, Jun 26, 2006
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Maric Michaud
    Replies:
    0
    Views:
    400
    Maric Michaud
    Jun 22, 2006
  2. darin dimitrov
    Replies:
    4
    Views:
    1,473
  3. anurag

    print all permutations of string

    anurag, Jul 20, 2006, in forum: C Programming
    Replies:
    20
    Views:
    1,795
    Mark P
    Jul 25, 2006
  4. anurag
    Replies:
    18
    Views:
    9,244
    karteek007
    Apr 17, 2009
  5. sanket
    Replies:
    3
    Views:
    540
Loading...

Share This Page