Projete em pseudocódigo uma função recursiva permutar(L) que recebe uma lista L com n elementos distintos e…

Questão

Projete em pseudocódigo uma função recursiva permutar(L) que recebe uma lista L com n elementos distintos e retorna uma lista contendo todas as permutações de L. Descreva o caso base, o passo recursivo, as variáveis usadas e explique como a função evita duplicações. Indique a complexidade temporal em função de n.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Pseudocódigo: funcao permutar(L): se L == [] entao retorne [[]] senao primeiro <- L[0] resto <- L[1:] perms_resto <- permutar(resto) resultado <- [] para cada p em perms_resto faca para pos de 0 ate comprimento(p) faca nova <- copiar(p) inserir primeiro em nova na pos adicionar nova em resultado retorne resultado Explicação: o caso base retorna a lista que contém a lista vazia, representando a permutação única de uma lista vazia. No passo recursivo, retiramos o primeiro elemento e geramos todas as permutações do resto; em seguida inserimos o elemento em todas as posições possíveis de cada permutação obtida, construindo novas listas (variáveis: primeiro, resto, perms_resto, resultado, p, pos, nova). Não há duplicações porque os elementos de L são distintos e cada inserção em posições diferentes produz sequências distintas. Complexidade temporal: T(n)=n*T(n-1)+O(n!*n) = O(n!*n). Profundidade de recursão: n. Espaço requerido: O(n!*n) para armazenar todas as permutações.

Explicação

A solução apresentada descreve claramente a lógica de permutação, detalhando o caso base e o passo recursivo, além de explicar como as permutações são geradas sem duplicações devido à distinção dos elementos. A complexidade temporal é adequadamente analisada, considerando o número de permutações e o tempo necessário para inserções. A descrição das variáveis utilizadas facilita a compreensão do funcionamento da função e sua implementação.

Raio-X da questão

Questões parecidas com resolução

• Projete em pseudocódigo uma função recursiva subsequencias(L) que recebe uma lista L de inteiros e retorna a lista de…
• Projete uma função recursiva em pseudocódigo flatten(L) que recebe uma lista L que pode conter inteiros e sublistas…
• Projete em pseudocódigo uma função recursiva duplicar(L) que recebe uma lista L de inteiros e retorna uma nova lista em…
• Projete em pseudocódigo uma função recursiva maximo(L) que recebe uma lista não vazia de inteiros e retorna o maior…
• Projete um algoritmo em pseudocódigo que receba uma lista L de n inteiros (com repetições possíveis) e retorne uma nova…
• Projete em pseudocódigo um algoritmo recursivo map_recursive(L,f) que recebe uma lista L e uma função f e retorna uma…

Todas as questões de Programação - Programação usando grafos e árvores