Python recursive permutation, fixed first element

Question

I am doing an exercise on recursive permutations with a fixed first element. I need a print with a certain format after each permutation (Fruit1 Fruit2 Fruit3 Fruit4 Fruit5) with the first element being the same all the time. I cannot find answers to this specific permutation problem, thus, I am asking it with a new question. I have tried to solve with two alternative ways, however, the first one keeps adding elements to the same result list, and the other one results a typeError. What is wrong and what is needed to fix the code. NOTE: I can get it done with itertools.permutations; OR with permutations with all the elements; OR with doing it first with four elements and then adding the first one when printing; Here I am asking how this particular function would need to be corrected?

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

Since you want first element is fixed, let's say "Apple", I discard it from "fruit" and find the permutation for the rest of fruits and add each permutation to `["Apple"] list.

fruits = ["Apple", "Banana", "Orange", "Peach", "Avocado"]
fixed=fruits[1:]
class Solution:
      def permute(self, fruits):
        result = []
        def dfs(fruits,path):
            if len(fruits) == 0:
                result.append(path)
                return
            for i in range(len(fruits)):
                dfs(fruits[:i] + fruits[i + 1:], path + [fruits[i]])

        dfs(fixed,['Apple'])
        return result
s=Solution()
s.permute(fixed)

Answer 2

You could just remove the fixed element, then create the permutation over the rest and add the fixed to the result, like this:

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)

The result would be:

('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')

If you want to create a recursive function without using itertools, you could do it as follows:

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, [])

This returns:

[('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')]

But it works for arbitrary long prefixes, like:

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')]