14

再帰を使用して順列コードを作成しようとすると問題が発生します。これは、各文字の可能なすべての位置を使用してリストを返すと想定されています。そのため、単語catは を返すと想定され['cat','act',atc,'cta','tca','tac']ます。これまでのところ、私はこれを持っています

def permutations(s):
    lst=[]
    if len(s) == 1 or len(s) == 0 :
        # Return a list containing the string, not the string
        return [s]
    # Call permutations to get the permutations that don't include the
    # first character of s
    plst = permutations(s[1:])
    print(plst)
    for item in plst:
        print (item)
        plst= permutations(s[1+1:])

         # Now move through each possible position of the first character
        # and create a new string that puts that character into the strings
        # in plst
        for i in range(len(s)):
            pass
            # Create a new string out of item
            # and put it into lst
        # Modify
    for item in lst:
        print(index)

そこにステップがありますが、それらを使用する方法がわかりません

4

10 に答える 10

39

再帰を行いたいので、最初に再帰がどのように機能するかを調べる必要があります。この場合は次のとおりです。

permutation [a,b,c,...] = [a + permutation[b,c,...], b + permutation[a,c,..], ...]

そして最終条件として：

permutation [a] = [a]

そのため、再帰はリストをサブリストに分割し、毎回 1 つの要素を抽出します。次に、この要素がサブリストの各順列の先頭に追加されます。

したがって、擬似コードでは：

def permutation(s):
   if len(s) == 1:
     return [s]

   perm_list = [] # resulting list
   for a in s:
     remaining_elements = [x for x in s if x != a]
     z = permutation(remaining_elements) # permutations of sublist

     for t in z:
       perm_list.append([a] + t)

   return perm_list

これは役に立ちますか？

于 2012-10-28T13:59:00.047 に答える
14

再帰的に、基本ケースについて考え、その直感から構築します。

1) 文字「c」が 1 つしかない場合はどうなりますか? その要素の順列は 1 つだけなので、その要素だけを含むリストを返します。

2) 最後の順列から次の順列を生成するにはどうすればよいですか? 前の順列「c」のすべての可能な位置に文字「a」を追加すると、「ca」、「ac」が得られます。

3) 以前の順列のすべての可能な位置に追加の文字を追加することにより、より大きな順列を構築し続けることができます。

次のコードは、文字列が 1 文字以下の場合、1 文字のリストを返します。それ以外の場合、文字列 s[-1] の最後の文字を含まないすべての順列について、その文字を含めることができる位置ごとに新しい文字列を生成し、新しい文字列を順列の現在のリストに追加します。

def permutations(s):
    if len(s) <= 1:
        return [s]
    else:
        perms = []
        for e in permutations(s[:-1]):
            for i in xrange(len(e)+1):
                perms.append(e[:i] + s[-1] + e[i:])
        return perms
于 2016-06-13T21:09:47.077 に答える
7

再帰関数に迷ったときは、コール ツリーを描画する必要があります。次のバージョン（@Benの回答に触発された）では、入力順序が維持されます（入力が辞書順の場合、順列のリストは'012' -> ['012', '021', '102', '120', '201', '210'].

def permut2(mystr):
    if len(mystr) <= 1:
        return [mystr]
    res = []
    for elt in mystr:
        permutations = permut2(mystr.replace(elt, ""))
        for permutation in permutations:
            res.append(elt + permutation)
    return res

次のバージョンは文字列とリストで機能しますが、再構築の手順が同じではないことに注意してください。

def permut(array):
    if len(array) == 1:
        return [array]
    res = []
    for permutation in permut(array[1:]):
        for i in range(len(array)):
            res.append(permutation[:i] + array[0:1] + permutation[i:])
    return res

演習として、これらの関数のコール ツリーを描画する必要があります。

于 2013-04-08T14:54:19.183 に答える
2 
def permutations(string_input, array, fixed_value=""):
    for ch in string_input:
        permutations(string_input.replace(ch, ""), array, fixed_value + ch)
    if not string_input:
        array.append(fixed_value)

あなたはそれを呼び出すことができます

array = []
permutations("cat", array)
print array
于 2017-10-16T14:04:14.483 に答える