Todos os desafios
Médio 0 resolvidos 0% de aceitação

Permutações caóticas

Conte as permutações de n itens em que nenhum item fica na sua posição original.

O que você vai aprender

  • Transformar um argumento de contagem em uma recorrência
  • Iterar uma recorrência a partir dos casos base
  • Tratar os casos n = 0 e n = 1

Problema

Ver original (inglês)

Cinco amigos deixam os chapéus em uma pilha e cada um pega um de volta ao acaso. De quantas maneiras pode acontecer de ninguém pegar o próprio chapéu? Uma permutação de n itens em que nenhum item fica na posição original é chamada de permutação caótica (em inglês, derangement). As quantidades começam com 1, 0, 1, 2, 9, 44 e seguem D(n) = (n − 1) × (D(n − 1) + D(n − 2)).

Implemente derangements(n).

Entrada

n: o número de itens.

Saída

Retorne o número de permutações caóticas de n itens. D(0) é 1 (a permutação vazia não tira nada do lugar) e D(1) é 0.

Restrições

0 ≤ n ≤ 20

Exemplos

Exemplo 1
Entrada:
n = 3

Saída esperada:
expected = 2
Entrada:
long long n = 3;

Saída esperada:
long long expected = 2;
Entrada:
long n = 3;

Saída esperada:
long expected = 2;

Explicação

Para os itens A, B, C, só BCA e CAB tiram todos do lugar, então a resposta é 2.

Exemplo 2
Entrada:
n = 4

Saída esperada:
expected = 9
Entrada:
long long n = 4;

Saída esperada:
long long expected = 9;
Entrada:
long n = 4;

Saída esperada:
long expected = 9;

Explicação

D(4) = 3 × (D(3) + D(2)) = 3 × (2 + 1) = 9.

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Comece com D(0) = 1 e D(1) = 0.

Dica 2

Cada novo valor usa os dois anteriores e o n atual.

Dica 3

A cada momento só os dois últimos valores são necessários.

Complexidade esperada

tempo O(n), espaço extra O(1)

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.