Permutations

+10

Você recebe uma lista nums de números inteiros distintos. Retorne todas as ordenações desses valores, cada uma como uma lista que usa cada valor exatamente uma vez, de modo que n valores gerem n! ordenações. Liste-as em ordem lexicográfica: compare duas ordenações posição por posição e deixe a primeira diferença decidir. Para [1, 2, 3], isso coloca [1, 2, 3] primeiro e [3, 2, 1] por último.

Função

permute(nums: integer-array) → integer-2d-array

numsinteger-array: os valores, todos diferentes, em qualquer ordem
Retornainteger-2d-array: todas as ordenações dos valores, listadas em ordem lexicográfica

Restrições

1 ≤ nums.length ≤ 6
-10 ≤ nums[i] ≤ 10
Todos os valores em nums são diferentes.
nums pode vir em qualquer ordem.

Exemplos

Entrada: nums = [3, 1, 2]
Saída: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Explicação: Três valores têm 3! = 6 ordenações. Em ordem crescente, os valores são 1, 2, 3; portanto, as ordenações que começam com 1 vêm primeiro, e [1, 2, 3] vem antes de [1, 3, 2] porque 2 é menor que 3 na segunda posição. A ordem da entrada não importa.

Entrada: nums = [2, -1]
Saída: [[-1, 2], [2, -1]]
Explicação: Dois valores podem ser escritos em duas ordens. [-1, 2] vem primeiro porque -1 é menor que 2.

+13 testes ocultos ao enviar

Para ir além

Dada uma ordenação, você consegue produzir a próxima em ordem lexicográfica no próprio lugar, em tempo O(n) e usando O(1) de espaço extra?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Uma lista de n valores diferentes tem n! ordenações, 720 para seis valores, e a resposta precisa listar todas elas, então o trabalho é de pelo menos n × n!. O desafio é construir cada ordenação uma única vez e emiti-las em ordem lexicográfica. Fazer backtracking sobre os valores ordenados, sempre tentando primeiro o menor valor não utilizado, resolve as duas coisas ao mesmo tempo.

Insira em cada lacuna e, em seguida, ordene

Intuição

Construa as ordenações adicionando um valor de cada vez. Sem valores, há uma ordenação: a lista vazia. Para adicionar o valor 3 à ordenação [1, 2], coloque-o em cada um dos seus três espaços: [3, 1, 2], [1, 3, 2] e [1, 2, 3]. Faça isso para cada ordenação que você tiver, e as ordenações de k valores se transformam nas ordenações de k+1 valores.

Cada ordenação de k+1 valores é construída exatamente uma vez: retire dela o valor mais recente e você obtém a única ordenação da qual ela se originou, enquanto a posição do valor mais recente indica o espaço. Portanto, as contagens são 1, 2, 6, 24, e n valores resultam em n! ordenações.

Elas não são geradas na ordem necessária. Para [1, 2, 3], a primeira ordenação construída é [3, 2, 1], então você termina com uma ordenação que compara posição por posição. Essa ordenação é a parte dispendiosa: n! ordenações exigem cerca de n! × log(n!) comparações, e cada uma lê até n valores. Para seis valores, isso dá aproximadamente 720 × 9.5 × 6, cerca de 41,000 leituras. O método também mantém uma geração inteira de ordenações na memória enquanto constrói a seguinte.

Algoritmo

Comece com uma lista que contenha uma ordenação vazia.
Para cada valor em nums, crie uma nova lista: para cada ordenação até então e cada posição de 0 até seu comprimento, copie a ordenação com o valor inserido nessa posição.
Substitua a lista antiga pela nova.
Classifique as ordenações posição por posição e retorne-as.

def permute(nums):
    perms = [[]]
    for value in nums:
        grown = []
        for perm in perms:
            # Put value into every gap of perm, both ends included.
            for gap in range(len(perm) + 1):
                grown.append(perm[:gap] + [value] + perm[gap:])
        perms = grown
    # Insertion order is not lexicographic, so sort at the end.
    perms.sort()
    return perms

Retrocesso com um array de elementos usados

Intuição

Preencha n posições da esquerda para a direita. A primeira posição tem n candidatos, a segunda, n-1, e assim por diante — é daí que vem n!. Represente essas escolhas como uma árvore: a raiz é um caminho vazio, cada aresta adiciona mais um valor, e cada folha, na profundidade n, é uma ordenação completa. Para os valores ordenados 1, 2, 3, a raiz tem os filhos [1], [2] e [3]; [1] tem os filhos [1, 2] e [1, 3]; cada um deles tem uma folha.

O retrocesso percorre essa árvore com um único path compartilhado e uma flag used para cada valor. Em cada nó, ele percorre os valores em um loop e ignora os que já foram usados. Para cada valor disponível, ele escolhe (marca como usado e o adiciona ao caminho), explora (recorre um nível mais fundo) e, em seguida, desfaz a escolha (remove o valor e o marca como disponível). A etapa de desfazer a escolha restaura exatamente o estado que o loop tinha antes, então o próximo valor é tentado a partir do mesmo nó. Um caminho de comprimento n é uma folha: registre uma cópia e retorne.

A ordem surge naturalmente. O loop tenta primeiro o menor valor disponível, e o percurso conclui todas as ordenações que começam com um determinado prefixo antes de alterá-lo. Assim, todas as ordenações que começam com 1 vêm antes de qualquer uma que começa com 2 e, entre elas, [1, 2, ...] vem antes de [1, 3, ...]. Essa é a ordem lexicográfica. É também por isso que você ordena nums primeiro: o loop percorre os índices, então eles precisam estar na ordem dos valores.

A árvore tem cerca de e × n! nós (e é aproximadamente 2.72), e cada um executa um loop de n, então o tempo é O(n × n!), a mesma ordem do tamanho da resposta. Além da saída, o caminho, as flags e a pilha de chamadas armazenam, cada um, no máximo n elementos.

Algoritmo

Ordene os valores e crie um array used com n sinalizadores falsos.
Escreva explore(). Se path contiver n valores, adicione uma cópia ao resultado e retorne.
Caso contrário, para cada índice i de 0 a n-1 cujo valor esteja livre: marque-o como usado e adicione values[i] (escolha), chame explore() (explore) e, em seguida, remova-o e marque-o como livre (desfaça a escolha).
Chame explore() uma vez e retorne o resultado.

def permute(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    path = []
    used = [False] * n

    def explore():
        # A full path is a leaf of the decision tree: one finished ordering.
        if len(path) == n:
            result.append(path[:])
            return
        # Smallest unused value first, so the leaves come out in lexicographic order.
        for i in range(n):
            if used[i]:
                continue
            used[i] = True
            path.append(values[i])  # choose
            explore()               # explore
            path.pop()              # un-choose
            used[i] = False

    explore()
    return result

Armadilhas e casos extremos

Os bugs de backtracking quase sempre são causados por um estado que não é restaurado ou que é compartilhado por acidente.

Registrar path em vez de uma cópia dele. Todas as n! entradas acabam sendo a mesma lista, que fica vazia quando a busca termina.
Desfazer apenas metade de uma escolha. Se você remover o valor, mas deixar used[i] definido, esse valor nunca mais aparecerá em um ramo posterior, e você retornará menos de n! ordenações.
Não ordenar nums primeiro. A busca ainda encontra todas as ordenações, mas elas seguem a ordem da entrada, então a entrada [3, 1, 2] seria listada primeiro.
Usar o método de troca (trocar nums[start] por cada posição posterior, fazer a recursão e desfazer a troca) sem uma ordenação final. Ele encontra todas as n! ordenações, mas, para [1, 2, 3], lista [3, 2, 1] antes de [3, 1, 2].
Verificar se um valor foi usado procurando em path. Isso funciona aqui apenas porque os valores são diferentes e custa n a cada etapa. Uma flag por índice custa O(1) e ainda funciona quando os valores se repetem.

Perguntas frequentes4

Quantas permutações uma lista de n elementos distintos tem?

n!, leia como n fatorial: n opções para a primeira posição, n-1 para a segunda, até chegar a uma para a última, multiplicadas entre si. Três valores dão 6 ordenações, seis dão 720, e dez já dão 3,628,800, por isso os problemas de permutação mantêm n pequeno.

Qual é a complexidade de tempo para gerar todas as permutações?

O(n × n!). Existem n! ordenações, e escrever cada uma delas leva n etapas; portanto, nenhum método pode ser mais eficiente quando precisa retornar todas elas. A busca com retrocesso atinge esse limite e, além da saída, precisa de O(n) de espaço para o caminho atual, as sinalizações de elementos usados e a recursão.

Por que o retrocesso produz permutações em ordem lexicográfica?

É uma busca em profundidade que tenta primeiro o menor valor disponível. Ela conclui todas as ordenações que começam com um determinado prefixo antes de passar para o próximo prefixo e tenta os prefixos do menor para o maior. Isso corresponde à maneira como um dicionário ordena as palavras, desde que a entrada seja ordenada antes do início da busca.

Como gerar permutações quando a entrada tem elementos duplicados?

Ordene os valores e, em cada posição, ignore um valor que seja igual ao valor anterior enquanto essa cópia anterior não estiver em uso: i > 0, values[i] == values[i-1] e !used[i-1]. Isso força os valores iguais a serem colocados na ordem original, para que cada ordenação distinta seja construída uma única vez.

Python

def permute(nums):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

nums = [3, 1, 2]

Esperado

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]