Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
568 views
in Technique[技术] by (71.8m points)

python 3.x - all permutations of string without using itertools

All possible strings of any length that can be formed from a given string

Input:

abc

Output:

a b c abc ab ac bc bac bca 
         cb ca ba cab cba acb

I have tried using this but it's limited to string abc, I want to generalize it like if input 'abcd' i will provide me output for the same.

def perm_main(elems):
    perm=[]
    for c in elems:
        perm.append(c)
    for i in range(len(elems)):
        for j in range(len(elems)):
            if perm[i]!= elems[j]:
                perm.append(perm[i]+elems[j])
    level=[elems[0]]
    for i in range(1,len(elems)):
        nList=[]
        for item in level:
            #print(item)
            nList.append(item+elems[i])
                #print(nList)
            for j in range(len(item)):
                #print(j)
                nList.append(item[0:j]+ elems[i] + item[j:])
                #print(nList)
        level=nList
    perm = perm + nList
    return perm
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

You may not need itertools, but you have the solution in the documentation, where itertools.permutations is said to be roughly equivalent to:

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

Or using product:

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)

They are both generators so you will need to call list(permutations(x)) to retrieve an actual list or substitute the yields for l.append(v) where l is a list defined to accumulate results and v is the yielded value.

For all the possible sizes ones, iterate over them:

from itertools import chain
check_string = "abcd"
all = list(chain.from_iterable(permutations(check_string , r=x)) for x in range(len(check_string )))

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...