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

What do you create the list for, if you then only use the length? (second argument) and why do you reference fruits from within the function? this way your function would only be restricted to that very list and could never be used for something else. — jottbe
– jottbe, Commented Nov 18, 2020 at 13:21
Desired output is: Apple Banana Orange Peach Avocado \n Apple Banana Orange Avocado Peach \n Apple Banana Peach Avocado Orange \n etc. — Johannes Niemeläinen
– Johannes Niemeläinen, Commented Nov 18, 2020 at 13:24
I am using it later to calculate some variables of the fruits... — Johannes Niemeläinen
– Johannes Niemeläinen, Commented Nov 18, 2020 at 13:26

Yilmaz · Accepted Answer · 2021-11-13 04:11:42Z

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)

answered Nov 13, 2021 at 4:11

Yilmaz

51k19 gold badges226 silver badges278 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

jottbe · Accepted Answer · 2020-11-18 13:47:58Z

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

Hi! Thanks for your response! That certainly works. But how if the need is to print inside the def permutation with two parameters sent into the function?
What do you mean? what parameters do you want to print? I add another way to do it recursively without itertools.
Thanks @jottbe! The second option without itertools is great. It gives the right tools to continue on my task.

Collectives™ on Stack Overflow

Python recursive permutation, fixed first element

2 Answers 2

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related