Рекурсивная перестановка Python, исправлен первый элемент

ProgramBox

Рекурсивная перестановка Python, исправлен первый элемент

Post author:admin
Запись опубликована:31 января, 2023
Post category:Вопросы по программированию

#python #permutation

#python #перестановка

Вопрос:

Я выполняю упражнение по рекурсивным перестановкам с фиксированным первым элементом. Мне нужна печать с определенным форматом после каждой перестановки (Fruit1 Fruit2 Fruit3 Fruit4 Fruit5), при этом первый элемент всегда остается одним и тем же. Я не могу найти ответы на эту конкретную проблему с перестановкой, поэтому я задаю ее с новым вопросом. Я попытался решить проблему двумя альтернативными способами, однако первый продолжает добавлять элементы в один и тот же список результатов, а другой выдает ошибку типа. Что не так и что нужно для исправления кода. ПРИМЕЧАНИЕ: я могу сделать это с помощью 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))))

1. каков ваш желаемый результат? не могли бы вы привести пример?

2. Для чего вы создаете список, если затем используете только длину? (второй аргумент) и почему вы ссылаетесь на фрукты из функции? таким образом, ваша функция будет ограничена только этим списком и никогда не сможет использоваться для чего-то другого.

3. Желаемый результат: яблоко Банан Апельсин персик Авокадо Яблоко Банан Апельсин Авокадо Персик Яблоко Банан Персик Авокадо апельсин и т.д.

4. Я использую его позже для вычисления некоторых переменных плодов…

Ответ №1:

Поскольку вы хотите, чтобы первый элемент был исправлен, скажем, «Apple», я удаляю его из «fruit» и нахожу перестановку для остальных фруктов и добавляю каждую перестановку в список `[«Apple»].

 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)

Ответ №2:

Вы могли бы просто удалить фиксированный элемент, затем создать перестановку поверх остальных и добавить исправленное к результату, например:

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

1. Привет! Спасибо за ваш ответ! Это, безусловно, работает. Но как, если необходимо напечатать внутри перестановки def с двумя параметрами, отправленными в функцию?

2. Что вы имеете в виду? какие параметры вы хотите распечатать? Я добавляю еще один способ сделать это рекурсивно без itertools .

3. Спасибо @jottbe! Второй вариант без itertools великолепен. Это дает правильные инструменты для продолжения моей задачи.

4. Я рад, что смог помочь.