Python递归置换，固定第一个元素

Question

我正在做一个关于第一个元素固定的递归排列的练习。我需要在每次排列（果1果2果3果4果5）后以特定格式打印，第一个元素始终相同。我找不到这个特定排列问题的答案，因此，我用一个新问题来问它。我试着用两种可选的方法来解决这个问题，但是，第一种方法不断地向同一个结果列表中添加元素，而另一种方法会导致typeError。什么是错误的，需要什么来修复代码。 注意：我可以用itertools.permutations完成；或与所有元素排列；或者先用四个元素进行打印，然后在打印时添加第一个元素； 在这里我要问的是，这个特殊的功能需要如何纠正

fruits = ["Apple", "Banana", "Orange", "Peach", "Avocado"]

def permutation(menu, lst):

    if len(lst) == 0:
        
        #here prints of each permutation
            
        print(' '.join([fruits[i] for i in menu]))
        
        return []

    
      ##the first try which gives the permutations
       ##as ever expanding list
    for i in range(len(lst)):

       fruit = lst[i]
       
       menu.append(fruit)
       
       remLst = lst[:i] + lst[i+1:]
     
       permutation(menu, remLst)
       
       
       ##the second option which gives TypeError:
           ##can only concatenate list (not "int") to list
           ##this is alternative to the one above NOT in the same function
       
      
    for i in range(len(lst)):

        fruit = lst[i]
       
        remLst = lst[:i] + lst[i+1:]
        
  
        for p in permutation(menu, remLst):
            
            menu.append([fruit] + p)
           
    return menu


permutation([0], list(range(1, len(fruits))))

Answer 1

您可以删除固定元素，然后在其余元素上创建置换，并将固定元素添加到结果中，如下所示：

from itertools import permutations

fruits = ["Apple", "Banana", "Orange", "Peach", "Avocado"]
fixed_index= 2 # "Orange"
fixed_element= fruits[fixed_index]
# create a temporary list with all elements that still are
# missing in the permutation
rest_elements= fruits[:fixed_index] + fruits[fixed_index+1:]
for permutation in permutations(rest_elements):
    print((fixed_element,) + permutation)

结果将是：

('Orange', 'Apple', 'Banana', 'Peach', 'Avocado')
('Orange', 'Apple', 'Banana', 'Avocado', 'Peach')
('Orange', 'Apple', 'Peach', 'Banana', 'Avocado')
('Orange', 'Apple', 'Peach', 'Avocado', 'Banana')
('Orange', 'Apple', 'Avocado', 'Banana', 'Peach')
('Orange', 'Apple', 'Avocado', 'Peach', 'Banana')
('Orange', 'Banana', 'Apple', 'Peach', 'Avocado')
('Orange', 'Banana', 'Apple', 'Avocado', 'Peach')
('Orange', 'Banana', 'Peach', 'Apple', 'Avocado')
('Orange', 'Banana', 'Peach', 'Avocado', 'Apple')
('Orange', 'Banana', 'Avocado', 'Apple', 'Peach')
('Orange', 'Banana', 'Avocado', 'Peach', 'Apple')
('Orange', 'Peach', 'Apple', 'Banana', 'Avocado')
('Orange', 'Peach', 'Apple', 'Avocado', 'Banana')
('Orange', 'Peach', 'Banana', 'Apple', 'Avocado')
('Orange', 'Peach', 'Banana', 'Avocado', 'Apple')
('Orange', 'Peach', 'Avocado', 'Apple', 'Banana')
('Orange', 'Peach', 'Avocado', 'Banana', 'Apple')
('Orange', 'Avocado', 'Apple', 'Banana', 'Peach')
('Orange', 'Avocado', 'Apple', 'Peach', 'Banana')
('Orange', 'Avocado', 'Banana', 'Apple', 'Peach')
('Orange', 'Avocado', 'Banana', 'Peach', 'Apple')
('Orange', 'Avocado', 'Peach', 'Apple', 'Banana')
('Orange', 'Avocado', 'Peach', 'Banana', 'Apple')

如果要在不使用itertools的情况下创建递归函数，可以按如下方式执行：

def create_permutations(base_list, prefix_list):
    result_list= list()
    # create a temporary list with all elements that still are
    # missing in the permutation
    remaining_elements= [el for el in base_list if el not in prefix_list]
    num_remaining= len(remaining_elements)
    if num_remaining == 0:
        # the prefix is a full permutation  > nothing to permute left
        result_list.append(tuple(prefix_list))
    else:
        # recursively create the rest of the permutations prefixed
        # by the old prefix extended by element el
        # and add the permutations to the result list
        for el in remaining_elements:
            result_list.extend(tuple(create_permutations(base_list, prefix_list + [el])))
    return result_list

create_permutations(fruits, [])

这将返回：

[('Apple', 'Banana', 'Orange', 'Peach', 'Avocado'),
 ('Apple', 'Banana', 'Orange', 'Avocado', 'Peach'),
 ('Apple', 'Banana', 'Peach', 'Orange', 'Avocado'),
 ('Apple', 'Banana', 'Peach', 'Avocado', 'Orange'),
 ('Apple', 'Banana', 'Avocado', 'Orange', 'Peach'),
 ('Apple', 'Banana', 'Avocado', 'Peach', 'Orange'),
 ('Apple', 'Orange', 'Banana', 'Peach', 'Avocado'),
 ('Apple', 'Orange', 'Banana', 'Avocado', 'Peach'),
 ('Apple', 'Orange', 'Peach', 'Banana', 'Avocado'),
 ('Apple', 'Orange', 'Peach', 'Avocado', 'Banana'),
 ('Apple', 'Orange', 'Avocado', 'Banana', 'Peach'),
 ('Apple', 'Orange', 'Avocado', 'Peach', 'Banana'),
 ('Apple', 'Peach', 'Banana', 'Orange', 'Avocado'),
 ('Apple', 'Peach', 'Banana', 'Avocado', 'Orange'),
 ('Apple', 'Peach', 'Orange', 'Banana', 'Avocado'),
 ('Apple', 'Peach', 'Orange', 'Avocado', 'Banana'),
 ('Apple', 'Peach', 'Avocado', 'Banana', 'Orange'),
 ('Apple', 'Peach', 'Avocado', 'Orange', 'Banana'),
 ('Apple', 'Avocado', 'Banana', 'Orange', 'Peach'),
 ('Apple', 'Avocado', 'Banana', 'Peach', 'Orange'),
 ('Apple', 'Avocado', 'Orange', 'Banana', 'Peach'),
 ('Apple', 'Avocado', 'Orange', 'Peach', 'Banana'),
 ('Apple', 'Avocado', 'Peach', 'Banana', 'Orange'),
 ('Apple', 'Avocado', 'Peach', 'Orange', 'Banana'),
 ('Banana', 'Apple', 'Orange', 'Peach', 'Avocado'),
 ('Banana', 'Apple', 'Orange', 'Avocado', 'Peach'),
 ('Banana', 'Apple', 'Peach', 'Orange', 'Avocado'),
 ('Banana', 'Apple', 'Peach', 'Avocado', 'Orange'),
 ('Banana', 'Apple', 'Avocado', 'Orange', 'Peach'),
 ('Banana', 'Apple', 'Avocado', 'Peach', 'Orange'),
 ('Banana', 'Orange', 'Apple', 'Peach', 'Avocado'),
 ('Banana', 'Orange', 'Apple', 'Avocado', 'Peach'),
 ('Banana', 'Orange', 'Peach', 'Apple', 'Avocado'),
 ('Banana', 'Orange', 'Peach', 'Avocado', 'Apple'),
 ('Banana', 'Orange', 'Avocado', 'Apple', 'Peach'),
 ('Banana', 'Orange', 'Avocado', 'Peach', 'Apple'),
 ('Banana', 'Peach', 'Apple', 'Orange', 'Avocado'),
 ('Banana', 'Peach', 'Apple', 'Avocado', 'Orange'),
 ('Banana', 'Peach', 'Orange', 'Apple', 'Avocado'),
 ('Banana', 'Peach', 'Orange', 'Avocado', 'Apple'),
 ('Banana', 'Peach', 'Avocado', 'Apple', 'Orange'),
 ('Banana', 'Peach', 'Avocado', 'Orange', 'Apple'),
 ('Banana', 'Avocado', 'Apple', 'Orange', 'Peach'),
 ('Banana', 'Avocado', 'Apple', 'Peach', 'Orange'),
 ('Banana', 'Avocado', 'Orange', 'Apple', 'Peach'),
 ('Banana', 'Avocado', 'Orange', 'Peach', 'Apple'),
 ('Banana', 'Avocado', 'Peach', 'Apple', 'Orange'),
 ('Banana', 'Avocado', 'Peach', 'Orange', 'Apple'),
 ('Orange', 'Apple', 'Banana', 'Peach', 'Avocado'),
 ('Orange', 'Apple', 'Banana', 'Avocado', 'Peach'),
 ('Orange', 'Apple', 'Peach', 'Banana', 'Avocado'),
 ('Orange', 'Apple', 'Peach', 'Avocado', 'Banana'),
 ('Orange', 'Apple', 'Avocado', 'Banana', 'Peach'),
 ('Orange', 'Apple', 'Avocado', 'Peach', 'Banana'),
 ('Orange', 'Banana', 'Apple', 'Peach', 'Avocado'),
 ('Orange', 'Banana', 'Apple', 'Avocado', 'Peach'),
 ('Orange', 'Banana', 'Peach', 'Apple', 'Avocado'),
 ('Orange', 'Banana', 'Peach', 'Avocado', 'Apple'),
 ('Orange', 'Banana', 'Avocado', 'Apple', 'Peach'),
 ('Orange', 'Banana', 'Avocado', 'Peach', 'Apple'),
 ('Orange', 'Peach', 'Apple', 'Banana', 'Avocado'),
 ('Orange', 'Peach', 'Apple', 'Avocado', 'Banana'),
 ('Orange', 'Peach', 'Banana', 'Apple', 'Avocado'),
 ('Orange', 'Peach', 'Banana', 'Avocado', 'Apple'),
 ('Orange', 'Peach', 'Avocado', 'Apple', 'Banana'),
 ('Orange', 'Peach', 'Avocado', 'Banana', 'Apple'),
 ('Orange', 'Avocado', 'Apple', 'Banana', 'Peach'),
 ('Orange', 'Avocado', 'Apple', 'Peach', 'Banana'),
 ('Orange', 'Avocado', 'Banana', 'Apple', 'Peach'),
 ('Orange', 'Avocado', 'Banana', 'Peach', 'Apple'),
 ('Orange', 'Avocado', 'Peach', 'Apple', 'Banana'),
 ('Orange', 'Avocado', 'Peach', 'Banana', 'Apple'),
 ('Peach', 'Apple', 'Banana', 'Orange', 'Avocado'),
 ('Peach', 'Apple', 'Banana', 'Avocado', 'Orange'),
 ('Peach', 'Apple', 'Orange', 'Banana', 'Avocado'),
 ('Peach', 'Apple', 'Orange', 'Avocado', 'Banana'),
 ('Peach', 'Apple', 'Avocado', 'Banana', 'Orange'),
 ('Peach', 'Apple', 'Avocado', 'Orange', 'Banana'),
 ('Peach', 'Banana', 'Apple', 'Orange', 'Avocado'),
 ('Peach', 'Banana', 'Apple', 'Avocado', 'Orange'),
 ('Peach', 'Banana', 'Orange', 'Apple', 'Avocado'),
 ('Peach', 'Banana', 'Orange', 'Avocado', 'Apple'),
 ('Peach', 'Banana', 'Avocado', 'Apple', 'Orange'),
 ('Peach', 'Banana', 'Avocado', 'Orange', 'Apple'),
 ('Peach', 'Orange', 'Apple', 'Banana', 'Avocado'),
 ('Peach', 'Orange', 'Apple', 'Avocado', 'Banana'),
 ('Peach', 'Orange', 'Banana', 'Apple', 'Avocado'),
 ('Peach', 'Orange', 'Banana', 'Avocado', 'Apple'),
 ('Peach', 'Orange', 'Avocado', 'Apple', 'Banana'),
 ('Peach', 'Orange', 'Avocado', 'Banana', 'Apple'),
 ('Peach', 'Avocado', 'Apple', 'Banana', 'Orange'),
 ('Peach', 'Avocado', 'Apple', 'Orange', 'Banana'),
 ('Peach', 'Avocado', 'Banana', 'Apple', 'Orange'),
 ('Peach', 'Avocado', 'Banana', 'Orange', 'Apple'),
 ('Peach', 'Avocado', 'Orange', 'Apple', 'Banana'),
 ('Peach', 'Avocado', 'Orange', 'Banana', 'Apple'),
 ('Avocado', 'Apple', 'Banana', 'Orange', 'Peach'),
 ('Avocado', 'Apple', 'Banana', 'Peach', 'Orange'),
 ('Avocado', 'Apple', 'Orange', 'Banana', 'Peach'),
 ('Avocado', 'Apple', 'Orange', 'Peach', 'Banana'),
 ('Avocado', 'Apple', 'Peach', 'Banana', 'Orange'),
 ('Avocado', 'Apple', 'Peach', 'Orange', 'Banana'),
 ('Avocado', 'Banana', 'Apple', 'Orange', 'Peach'),
 ('Avocado', 'Banana', 'Apple', 'Peach', 'Orange'),
 ('Avocado', 'Banana', 'Orange', 'Apple', 'Peach'),
 ('Avocado', 'Banana', 'Orange', 'Peach', 'Apple'),
 ('Avocado', 'Banana', 'Peach', 'Apple', 'Orange'),
 ('Avocado', 'Banana', 'Peach', 'Orange', 'Apple'),
 ('Avocado', 'Orange', 'Apple', 'Banana', 'Peach'),
 ('Avocado', 'Orange', 'Apple', 'Peach', 'Banana'),
 ('Avocado', 'Orange', 'Banana', 'Apple', 'Peach'),
 ('Avocado', 'Orange', 'Banana', 'Peach', 'Apple'),
 ('Avocado', 'Orange', 'Peach', 'Apple', 'Banana'),
 ('Avocado', 'Orange', 'Peach', 'Banana', 'Apple'),
 ('Avocado', 'Peach', 'Apple', 'Banana', 'Orange'),
 ('Avocado', 'Peach', 'Apple', 'Orange', 'Banana'),
 ('Avocado', 'Peach', 'Banana', 'Apple', 'Orange'),
 ('Avocado', 'Peach', 'Banana', 'Orange', 'Apple'),
 ('Avocado', 'Peach', 'Orange', 'Apple', 'Banana'),
 ('Avocado', 'Peach', 'Orange', 'Banana', 'Apple')]

但它适用于任意长前缀，如：

create_permutations(fruits, ['Orange', 'Banana'])
# which returns:
[('Orange', 'Banana', 'Apple', 'Peach', 'Avocado'),
 ('Orange', 'Banana', 'Apple', 'Avocado', 'Peach'),
 ('Orange', 'Banana', 'Peach', 'Apple', 'Avocado'),
 ('Orange', 'Banana', 'Peach', 'Avocado', 'Apple'),
 ('Orange', 'Banana', 'Avocado', 'Apple', 'Peach'),
 ('Orange', 'Banana', 'Avocado', 'Peach', 'Apple')]