Hướng dẫn find all permutations of a string python recursion - tìm tất cả các hoán vị của một chuỗi đệ quy python

12

Mới! Lưu câu hỏi hoặc câu trả lời và sắp xếp nội dung yêu thích của bạn. Tìm hiểu thêm.
Learn more.

Tôi cần một cú đá vào đầu này. Tôi có chức năng đệ quy sau được xác định:

def perms(s):
  if(len(s)==1):
    return s

  res = ''
  for x in xrange(len(s)):

    res += s[x] + perms(s[0:x] + s[x+1:len(s)])

  return res + '\n'

PERMS ("ABC") hiện đang trả về:

abccb
bacca
cabba

Kết quả mong muốn là

abc
acd
bac
bca
cab
cba

Tôi đang đi đâu sai ở đây? Làm thế nào tôi có thể nghĩ về điều này khác nhau để đưa ra giải pháp?

Lưu ý: Tôi nhận thức được chức năng itertools. Tôi đang cố gắng hiểu làm thế nào để thực hiện hoán vị một cách đệ quy cho việc học của tôi. Đó là lý do tại sao tôi thích ai đó chỉ ra điều gì sai với mã của tôi và cách suy nghĩ khác biệt để giải quyết nó. Cảm ơn! I am aware of the itertools function. I am trying to understand how to implement permutations recursively for my own learning. That is why I would prefer someone to point out what is wrong with my code, and how to think differently to solve it. Thanks!

Hỏi ngày 16 tháng 4 năm 2014 lúc 18:04Apr 16, 2014 at 18:04

gnp210gnp210gnp210

1531 Huy hiệu vàng1 Huy hiệu bạc9 Huy hiệu đồng1 gold badge1 silver badge9 bronze badges

3

Kết quả của hoán vị sẽ là một bộ sưu tập, hãy nói một danh sách. Nó sẽ làm cho mã của bạn sạch hơn nếu bạn nghĩ theo cách này và nếu được yêu cầu, bạn có thể tham gia kết quả vào một chuỗi. Một ví dụ đơn giản sẽ là

def perms(s):        
    if(len(s)==1): return [s]
    result=[]
    for i,v in enumerate(s):
        result += [v+p for p in perms(s[:i]+s[i+1:])]
    return result


perms('abc')

['abc', 'acb', 'bac', 'bca', 'cab', 'cba']


print('\n'.join(perms('abc')))

abc
acb
bac
bca
cab
cba

Đã trả lời ngày 5 tháng 1 năm 2016 lúc 20:09Jan 5, 2016 at 20:09

Karakfakarakfakarakfa

65.3K7 Huy hiệu vàng38 Huy hiệu bạc55 Huy hiệu Đồng7 gold badges38 silver badges55 bronze badges

1

Có bạn đi (hoán vị đệ quy):

def Permute(string):
    if len(string) == 0:
        return ['']
    prevList = Permute(string[1:len(string)])
    nextList = []
    for i in range(0,len(prevList)):
        for j in range(0,len(string)):
            newString = prevList[i][0:j]+string[0]+prevList[i][j:len(string)-1]
            if newString not in nextList:
                nextList.append(newString)
    return nextList

Để có được danh sách tất cả các chuỗi hoán vị, chỉ cần gọi hàm ở trên với chuỗi đầu vào của bạn. Ví dụ,

stringList = Permute('abc')

Để có được một chuỗi gồm tất cả các chuỗi hoán vị được phân tách bằng các ký tự dòng mới, chỉ cần gọi

abccb
bacca
cabba

string = '\n'.join(Permute('abc'))

Nhân tiện, kết quả

abccb
bacca
cabba

Đã trả lời ngày 16 tháng 4 năm 2014 lúc 18:31Apr 16, 2014 at 18:31

Barak Manosbarak Manosbarak manos

29K9 Huy hiệu vàng57 Huy hiệu bạc113 Huy hiệu đồng9 gold badges57 silver badges113 bronze badges

22

Đây là mã:

def fperms(elements):
    if len(elements)<=1:
        yield elements
    else:
        for p in fperms(elements[1:]):
            for i in range(len(elements)):
                yield p[:i]+elements[0:1]+p[i:]

S.A.

1.6191 Huy hiệu vàng21 Huy hiệu bạc37 Huy hiệu đồng1 gold badge21 silver badges37 bronze badges

Đã trả lời ngày 17 tháng 10 năm 2016 lúc 10:20Oct 17, 2016 at 10:20

Không chắc chắn về hiệu quả nhưng điều này cũng sẽ hoạt động.

def find_permutations(v):
    if len(v) > 1:
        for i in perms(v):
            nv = i[1:]
            for j in perms(nv):
                print(i[0] + j)
    else:
        print(v)


def perms(v):
    if not hasattr(perms, 'original'):
        perms.original = v
        perms.list = []
    nv = v[1:] + v[0]
    perms.list.append(nv)
    if perms.original == nv:
        l = perms.list
        del perms.original
        del perms.list
        return l
    return perms(nv)

find_permutations('abc')

Đã trả lời ngày 5 tháng 1 năm 2016 lúc 19:08Jan 5, 2016 at 19:08

def get_permutations(sequence):
    if len(sequence) == 1:
        return [sequence]  # base case
    else:
        result = []
        for letter in sequence:
            result += [letter +
                    other_letter for other_letter in get_permutations(sequence.replace(letter, ""))]


 test_1 = 'abc'
print("Input: ", test_1)
print("Expected output: ", ['abc', 'acb', 'bac', 'bca', 'cab', 'cba'])
print("Actual output: ", get_permutations(test_1))

Đã trả lời ngày 11 tháng 11 năm 2021 lúc 8:02Nov 11, 2021 at 8:02

1

Loại điều này là một nơi tốt đẹp cho máy phát điện (https://docs.python.org/3.3/tutorial/classes.html#generatorators) và

abccb
bacca
cabba

Hãy thử một cái gì đó như thế này (không được kiểm tra):

abccb
bacca
cabba

Đây là thuật toán hoán vị cổ điển: bạn giữ ký tự đầu tiên và dành cho nó vào tất cả các hoán vị của các ký tự còn lại. Chức năng đặc biệt này là một trình tạo Python: điều đó có nghĩa là nó có thể tiếp tục chạy trong khi mang lại kết quả của nó từng người một. Trong trường hợp này, nó giúp tập trung vào thuật toán dễ dàng hơn mà không phải lo lắng về các chi tiết về cách đưa dữ liệu trở lại người gọi.

Đã trả lời ngày 16 tháng 4 năm 2014 lúc 18:49Apr 16, 2014 at 18:49

Adrian Ratnapalaadrian RatnapalaAdrian Ratnapala

5.3471 Huy hiệu vàng28 Huy hiệu bạc39 Huy hiệu đồng1 gold badge28 silver badges39 bronze badges

2

Làm thế nào để bạn tìm thấy tất cả các hoán vị của một chuỗi trong Python?

Làm thế nào để bạn có được tất cả các hoán vị của một mảng trong Python?

Python hoán vị là gì?

Làm thế nào để bạn hoán vị một danh sách trong Python?