BCM0505-15 - Processamento da Informação

Laboratório 04 – 10/03

Permutações

Uma permutação para um conjunto finito $A=\{a_0,a_1,\ldots,a_{n-1}\}$ é uma função bijetora $\sigma:A\to A$ que mapeia elementos distintos de $A$ a elementos distintos de $A$. O mapeamento estabelecido por $\sigma$ pode ser interpretado como substituições entre os elementos de $A$. Informalmente, permutações são rearranjos ou embaralhamentos dos elementos de $A$.

É conveniente indexar os elementos de $A$ — como fizemos — e listá-los como uma sequência, com $a_i$ na posição $i$, para $0\leq i<n$: $$\langle a_0,a_1,\ldots,a_{n-1}\rangle =: \mathsf{id}.$$

Definindo $[\![n]\!]:=\{0,1,\ldots,n-1\}$, podemos abusar da notação e reinterpretar $\sigma$ como uma função bijetora $\sigma:[\![n]\!]\to[\![n]\!]$ que mapeia índices a índices. A sequência $\mathsf{id}$ acima é denominada permutação identidade, pois $$\sigma(A) := \langle a_{\sigma(0)},a_{\sigma(1)},\ldots,a_{\sigma(n-1)}\rangle = \langle a_0,a_1,\ldots,a_{n-1}\rangle,$$ com $\sigma(i)=i$.

A título de ilustração:

• uma permutação $\pi:[\![n]\!]\to[\![n]\!]$ para $A$ definida por $\pi(i)=n-i-1$ equivale a $$\pi(A) := \langle a_{\pi(0)},a_{\pi(1)},\ldots,a_{\pi(n-1)}\rangle = \langle a_{n-1},a_{n-2},\ldots,a_0\rangle,$$ que é a permutação reversa à $\mathsf{id}$;
• uma permutação $\tau:[\![n]\!]\to[\![n]\!]$ para $A$ definida por $\tau(i)=(i+1)\!\!\mod n$ equivale a $$\tau(A) := \langle a_{\tau(0)},\ldots,a_{\tau(n-2)},a_{\tau(n-1)}\rangle = \langle a_1,\ldots,a_{n-1},a_0\rangle,$$ que é a permutação cíclica à esquerda de ordem $1$ à $\mathsf{id}$;
• uma permutação $\rho:[\![n]\!]\to[\![n]\!]$ para $A$ definida por $\rho(i)=(i-2)\!\!\mod n$ equivale a $$\rho(A) := \langle a_{\rho(0)},a_{\rho(1)},a_{\rho(2)},\ldots,a_{\rho(n-1)}\rangle = \langle a_{n-2},a_{n-1},a_0,\ldots,a_{n-3}\rangle,$$ que é a permutação cíclica à direita de ordem $2$ à $\mathsf{id}$;
• uma permutação $\theta:[\![n]\!]\to[\![n]\!]$ para $A$ definida por $$\theta(i)=\begin{cases} i/2 & \text{se}~i~\text{é par}, \\ \lfloor n/2\rfloor + \lfloor i/2\rfloor& \text{se}~i~\text{é ímpar}, \end{cases}$$ equivale a $$\theta(A) := \langle a_{\theta(0)},a_{\theta(1)},a_{\theta(2)},\ldots,a_{\theta(n-1)}\rangle = \langle a_0,a_2,a_4,\ldots,a_1,a_3,a_5,\ldots\rangle,$$ uma permutação em que os elementos de índice par em $\mathsf{id}$ ocorrem antes dos elementos de índice ímpar, ambos os grupos de índices de forma crescente.

Não é difícil perceber que a composição de permutações é uma permutação, que a permutação identidade ($\mathsf{id}$) age como elemento neutro da composição, e que para cada permutação $\sigma$ existe uma única permutação inversa $\sigma^{-1}$ tal que $\sigma\circ\sigma^{-1}=\sigma^{-1}\circ\sigma=\mathsf{id}$.

Representação em Python

Podemos utilizar listas para representar permutações. Armazenamos o $i$-ésimo elemento da sequência descrevendo a permutação na $i$-ésima posição da lista. Por exemplo, a permutação identidade $\mathsf{id} = \langle a_0,a_1,\ldots,a_{n-1}\rangle$ pode ser representada por uma lista $$A[0\,..n-1]=[a_0,a_1,\ldots,a_{n-1}].$$ A permutação reversa $\pi(\mathsf{id})=\langle a_{n-1},a_{n-2},\ldots,a_0\rangle$ pode ser representada por outra lista $$B[0\,..n-1]=[a_{n-1},a_{n-2},\ldots,a_0].$$ Observe que a orderm dos elementos na lista corresponde à ordem dos elementos na sequência — como esperado — e não à indexação original dos elementos. Isto é, $B[0]$ é igual a $a_{n-1}$ e não a $a_0$.

Em certas circunstâncias, é conveniente representarmos uma permutação por uma lista $C[1\,..n]$ em vez de $C[0\,..n-1]$. Nestes casos, $C[1\,..n]$ deve ser interpretada como uma lista $C[0\,..n]$ com $n+1$ elementos em que ignoramos a posição $0$.

Ordem entre permutações

Quando os elementos do conjunto $A$ são comparáveis, podemos estabelecer ordens entre diferentes permutações para $A$.

Dadas duas permutações $B[0\,..n-1]$ e $C[0\,..n-1]$ para $A=\{0,1,\ldots,n-1\}$, dizemos que $B$ é lexicograficamente menor que $C$, indicado por $B<C$, se existe um índice $j\in\{0,1,\ldots,n-1\}$ tal que

• $B[i] = C[i]$ para $0\leq i<j$, e
• $B[j] < C[j]$.

Por exemplo, $[1,2,3,4] < [1,3,2,4]$; $[1,2,3,4] < [1,3,4,2]$; e $[1,3,2,4] < [1,3,4,2]$.

Exercícios

• (01) Enumeração I.
  Escreva uma função que devolve em uma lista todas as $4!$ permutações para $\{1,2,3,4\}$, em ordem lexicográfica. Isto é, sua função deve devolver: $$\big[[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],\ldots,[4,3,2,1]\big].$$ Dica: utilize as funções append() e extend() para inserir elementos ao final de uma lista.

  Solução:
  

  def permute_4():
    P = []
    for i in range (1,5):
      for j in range (1,5):
        if i != j:
          for k in range (1,5):
            if k not in (i, j):
              for l in range (1,5):
                if l not in (i, j, k):
                  P.append ([i,j,k,l])
    return P
  

  $\square$

• (02) Enumeração II.
  Agora, escreva uma função que devolve em uma lista todas as $5!$ permutações para $\{1,2,3,4,5\}$.

  Solução:
  

  def permute_5():
    P = []
    for i in range (1,6):
      for j in range (1,6):
        if i != j:
          for k in range (1,6):
            if k not in (i, j):
              for l in range (1,6):
                if l not in (i, j, k):
                  for m in range (1,6):
                    if m not in (i, j, k, l):
                      P.append ([i,j,k,l,m])
    return P
  

  $\square$

Observe que as soluções dos exercícios (01) e (02), baseadas em laços aninhados, podem ser estendidas para qualquer $n\geq 1$ fixo — via incremento de código. Tais soluções são não uniformes, já que são específicas para cada valor de $n$. No exercício (12), vamos revisitar este problema de enumeração e desenvolver um algoritmo uniforme, que funcione para qualquer valor inteiro de $n\geq 1$.

• (03) Pontos fixos e desarranjos.
  Seja $A[1\,..n]$ uma permutação para $\{1,2,\ldots,n\}$. Um ponto fixo de $A$ é um índice $j$ tal que $A[j]=j$.
  Escreva uma função que recebe $A$ e devolve uma lista com os pontos fixos de $A$.
  

  Nota: uma permutação que não possui pontos fixos é chamada desarranjo.

  Solução:
  

  def fixed_pts (A: [int]) -> [int]
    P = []
    for i in range (1, len (A)):
      if A[i] == i: P.append (i)
    return P
  

  $\square$

• (04) Permutações cíclicas I.
  Uma permutação $A[0\,..n-1]$ de $\langle 0,1,\ldots,n-1\rangle$ é cíclica se existe um índice $j$ tal que $$A[0\,..j-1] = \langle n-j,n-j+1,\ldots,n-1\rangle \quad\text{e}\quad A[j\,..n-1] = \langle 0,1,\ldots,n-j-1\rangle.$$ Por exemplo, $\langle 0,1,2,3,4\rangle$ e $\langle 3,4,0,1,2\rangle$ são cíclicas; $\langle 0,3,4,1,2\rangle$ e $\langle 4,3,2,1,0\rangle$ não são.
  

  Escreva uma função que recebe $A$ e determina se ela é uma permutação cíclica de $\langle 0,1\ldots,n-1\rangle$. Em caso afirmativo, devolva um tal índice $j$; em caso contrário, devolva $j=n$.

  Solução:
  

  def cyclic_1 (A: [int]) -> int:
    j, n = 0, len (A)
    while j < n and A[j] != 0: j += 1
    if j == n: return n
    for i in range (1, n):
      if i != A[(i+j) % n]: return n
    return j
  

  $\square$

• (05) Permutações cíclicas II.
  O exercício anterior é um caso particular deste. Dadas duas listas $A[0\,..n-1]$ e $B[0\,..n-1]$, dizemos que $B$ é uma permutação cíclica de $A$ se existe um índice $j$ tal que $$A[0\,..j-1] = B[n-j\,..n-1] \quad\text{e}\quad A[j\,..n-1] = B[0\,..n-j-1].$$ Se $B$ é uma permutação cíclica de $A$, claramente $A$ é uma permutação cíclica de $B$. Escreva uma função que recebe $A$ e $B$ e devolve um tal índice $j$ se $A$ e $B$ são permutações cíclicas, ou devolve $j=n$ em caso contrário.

  Solução:
  Supomos que len (A) == len (B).

  def cyclic_2 (A: [int], B: [int]) -> int:
    j, n = 0, len (A)
    while j < n and A[j] != B[0]: j += 1
    if j == n: return n
    for i in range (1, n):
      if B[i] != A[(i+j) % n]: return n
    return j
  

  $\square$

• (06) Permutações adjacentes.
  Duas permutações $A[0\,..n-1]$ e $B[0\,..n-1]$ para $\{0,1,\ldots,n-1\}$ são adjacentes se existe um índice $j$ tal que $k=(j+1)\!\!\mod n$ e $$A[j]=B[k],\quad A[k]=B[j] \quad\text{e}\quad A[i]=B[i]~\text{para}~i\in\{1,2,\ldots,n\}\setminus\{j,k\}.$$ Em outras palavras, $A$ e $B$ diferem somente nas posições $j$ e $k$. Escreva uma função que recebe $A$ e $B$ e determina se elas são adjacentes.

  Solução:
  Supomos que len (A) == len (B).

  def are_adjacent (A: [int], B: [int]) -> bool:
    n, d = len (A), [] 
    for j in range (n):
      if A[j] != B[j]: d.append (j)
  
    if len (d) != 2 or (d[1] - d[0]) not in (1, n-1):
      return False
  
    return A[d[0]] == B[d[1]] and A[d[1]] == B[d[0]]
  

  $\square$

• (07) Permutações inversas I.
  Duas permutações $A[1\,..n]$ e $B[1\,..n]$ para $\{1,2,\ldots,n\}$ são inversas se $A[B[i]]=B[A[i]]=i$ para todo índice $i$. Em outras palavras, se a composição de $A$ com $B$ ou de $B$ com $A$ resulta na permutação identidade. Escreva uma função que recebe $A$ e $B$ e determina se elas são inversas.

  Solução:
  Supomos que len (A) == len (B).

  def are_inverse (A: [int], B: [int]) -> bool:
    for i in range (1, len (A)):
      if A[B[i]] != i: return False
    return True  
  

  $\square$

• (08) Permutações inversas II.
  Escreva uma função que recebe uma permutação $A[1\,..n]$ para $\{1,2,\ldots,n\}$ e devolve a permutação inversa a $A$.
  Nota: veja exercício anterior para definição.

  Solução:
  

  def perm_invert (A: [int]) -> [int]:
    n = len (A)
    B = [0] * n
    for i in range (n):
      B[A[i]] = i
    return B
  

  $\square$

• (09) Permutações alternantes.
  Uma permutação $A[0\,..n-1]$ é alternante se $$A[0] < A[1] > A[2] < A[3] > \cdots \lessgtr A[n-1] \qquad\text{ou}\qquad A[0] > A[1] < A[2] > A[3] < \cdots \gtrless A[n-1].$$ Escreva uma função que recebe $A$ e determina se ela é alternante.

  Solução:
  Claramente, uma sequência vazia é não alternante, e uma sequência unitária é alternante. Esses dois casos particulares são tratados em separado. O caso à direita pode ser reduzido ao da esquerda multiplicando-se os valores por $-1$ (veja (*) no código).

  def alternating (A: [int]) -> bool:
    n = len (A)
    if n <= 1: return [False, True][n]
  
    sgn = 1 if A[0] < A[1] else -1 # (*)
    for i in range (2, n):
      if sgn * (A[i] - A[i-1]) >= 0:
        return False
      sgn *= -1
    return True
  

  $\square$

• (10) Verificação de permutações.
  Escreva uma função que recebe uma lista de ints $A[1\,..n]$ e determina se $A$ é uma permutação para $\{1,2,\ldots,n\}$.
  Dica: utilize uma lista auxiliar.

  Solução:
  

  def is_permutation (A: [int]) -> bool:
    n = len (A)
    B = [False] * n
    for i in range (1, n):
      if B[A[i]]: return False
      B[A[i]] = True
    for i in range (n):
      if not B[i]: return False
    return True
  

  Nota: Python disponibiliza a função all() que recebe um iterável e devolve True se todos os seus elementos forem True ou se o iterável é vazio, e False em caso contrário. O código acima pode ser então reescrito como segue.

  def is_permutation (A: [int]) -> bool:
    n = len (A)
    B = [False] * n
    for i in range (1, n):
      if B[A[i]]: return False
      B[A[i]] = True
    return all (B)
  

  $\square$

• (11) Inversões em permutações.
  Seja $A[1\,..n]$ uma permutação para $\{1,2,\ldots,n\}$. Dois índices $i<j$ são uma inversão em $A$ se $A[i]>A[j]$.
  Escreva uma função que recebe $A$ e devolve o número de inversões em $A$.

  Solução:
  Um algoritmo consistem em: (i) gere todos os pares $(i,j)$ tais que $0\leq i<j<n$; (ii) para cada par gerado, verifique se $A[i]>A[j]$; (iii) em caso afirmativo, o par $(i,j)$ é uma inversão; (iv) em caso negativo, ele pode ser desconsiderado.

  # recebe uma lista A[1..n] e devolve uma lista contendo as inversões em A.
  def invertions (A: [int]) -> [int]:
    Inv, n = [], len(A)
    for i in range (1, n-1):
      for j in range (i+1, n):
        if A[i] > A[j]:
          # o par (i,j), uma inversão, é incluido no final da lista Inv.
          Inv.append ((i,j))
    return Inv
  

  Nota: O código acima determina todas as inversões em tempo $\Theta(n^2)$. Utilizando as ideias introduzidas na ordenação por intercalação (merge-sort), é possível realizar a tarefa em $\Theta(n\log n)$.
  $\square$

• (12) Enumeração III.
  Escreva uma função que recebe um inteiro $n\geq 1$ e imprime todas as $n!$ permutações de $\{1,2,\ldots,n\}$ em ordem lexicográfica.

  Descrevemos um algoritmo a seguir.
  Comece com uma lista $p[0\,..n]=[0,1,2,\ldots,n]$; a entrada $p[0]=0$ funciona como sentinela.

  • (1) Imprima a permutação em $p[1\,..n]$.
  • (2) Faça $i=n-1$. Se $p[i]\geq p[i+1]$, faça $i=i-1$ até que $p[i]< p[i+1]$. Se $i=0$, o algoritmo termina.
  • (3) Faça $j=n$. Se $p[i]\geq p[j]$, faça $j=j-1$ até que $p[i]< p[j]$. Troque $p[i]$ com $p[j]$.
  • (4) Faça $j=i+1$ e $k=n$. Enquanto $j<k$, troque $p[j]$ com $p[k]$ e faça $j=j+1$ e $k=k-1$. Volte ao passo (1).

  Por que o algoritmo acima funciona? Em outras palavras, quais são os invariantes após os passos (2) e (3)?
  

  Solução:
  

  def permute_n (n: int):
    p = [i for i in range (0,n+1)]
    i = n
    while i > 0:
      print (p)
  
      i = n-1
      while i > 0 and p[i] >= p[i+1]: i -= 1
      if i == 0: break
  
      j = n
      while p[i] >= p[j]: j -= 1
      p[i], p[j] = p[j], p[i]
  
      j, k = i+1, n
      while j < k:
        p[j], p[k] = p[k], p[j]
        j, k = j+1, k-1
  

  Observe que, ao final do passo (2), $i$ é o menor índice tal que todas as permutações com prefixo $p[1],p[2],\ldots,p[i]$ já foram geradas. Logo, a próxima permutação em ordem lexicográfica aumenta o valor de $p[i]$. Ao final do passo (3), temos que $p[i+1]\geq\cdots \geq p[n]$; $p[j]$ é o menor elemento maior que $p[i]$ que pode suceder $p[1],p[2],\ldots,p[i-1]$ em uma permutação. Após a troca, temos que $$p[i+1]\geq \cdots\geq p[j-1]\geq p[i]> p[j]\geq p[j+1]\geq \cdots\geq p[n].$$

  Python possui a palavra reservada yield que possibilita uma construção fácil de geradores (iteráveis). Para tal, basta substituirmos a linha print (p) no código acima por yield p. Para conveniência, copiamos o código com a modificação.

  def permute (n: int) -> [int]:
    p = [i for i in range (0,n+1)]
    i = n
    while i > 0:
      yield p
  
      i = n-1
      while i > 0 and p[i] >= p[i+1]: i -= 1
      if i == 0: break
  
      j = n
      while p[i] >= p[j]: j -= 1
      p[i], p[j] = p[j], p[i]
  
      j, k = i+1, n
      while j < k:
        p[j], p[k] = p[k], p[j]
        j, k = j+1, k-1
  

  yield p devolve p e guarda o estado da função permute() no momento do yield. Em uma próxima chamada a permute(), a execução começa do ponto onde ocorreu a parada anterior — e não do início da função. O exemplo

  for q in permute (4):
    print (q)
  

  imprime todas as permutações de $\{1,2,3,4\}$ em ordem lexicográfica, prefixadas por um $0$.
  $\square$

• (13) Caminho do cavalo.
  Suponha dado um tabuleiro de xadrez $n\times n$, com $n\geq 1$, e cujas casas são numeradas por $$(1,1), (1,2),\ldots,(1,n),(2,1),(2,2),\ldots,(2,n),(3,1),(3,2),\ldots,(n,n). \qquad{(*)}$$ Determine se é possível a um cavalo de jogo de xadrez partir da posição $(1,1)$ e visitar todas as demais casas do tabuleiro uma única vez, em $n^2-1$ passos válidos. Por exemplo, para um tabuleiro $5\times 5$ uma solução é $$\begin{array}{r|rrrrr} & 1& 2& 3& 4& 5\\ \hline 1& 1& 6& 15& 10& 21\\ 2& 14& 9& 20& 5& 16\\ 3& 19& 2& 7& 22& 11\\ 4& 8& 13& 24& 17& 4\\ 5& 25& 18& 3& 12& 23 \end{array}$$ em que um número $k$ na casa $(i,j)$ representa que ela é a $k$-ésima casa visitada ao longo do caminho.
  Dica: represente o tabuleiro em uma lista, como sugerido por $(*)$; para cada permutação de $\{1,2,\ldots,n^2\}$, verifique se ela representa um caminho válido.

  Solução:
  Vamos seguir a sugestão apresentada e utilizar o algoritmo do item anterior para gerar, em ordem lexicográfica, as $n^2!$ permutações de $L:=\{1,2,\ldots,n^2\}$. Cada permutação representa uma alocação dos números em $L$ nas casas de um tabuleiro $n\times n$.
  

  Dada uma permutação, a função auxiliar is_horse_path() verifica se ela descreve um caminho válido para o cavalo. A função find_horse_path() coordena a enumeração e devolve o primeiro caminho válido encontrado, ou uma lista vazia caso um tal caminho não exista.

  def is_horse_path (n: int, m: int, p: [int]) -> bool:
    def kth_horse_step (n: int, p: [int], k: int, ci: int, cj: int) -> (bool, int, int):
      for (di, dj) in ((-1,+2),(-2,+1),(-2,-1),(-1,-2),(+1,-2),(+2,-1),(+2,+1),(+1,+2)):
        ni, nj = ci+di, cj+dj
        if 1 <= ni <= n and 1 <= nj <= n and p[(ni-1)*n + nj] == k:      
          return (True, ni, nj)
      return (False, 0, 0)
  
    ci, cj = 1, 1
    for k in range (2, m+1):
      good_step, ci, cj = kth_horse_step (n, p, k, ci, cj)
      if not good_step:
        return False
    return True            
  
  def find_horse_path (n: int = 8) -> [int]:
    m = n*n
    for q in permute (m):
      if is_horse_path (n, m, q):
        return q
    return []    
  

Nota: O algoritmo acima é extremamente lento para valores modestos de $n$, e impraticável para valores maiores. A razão: no pior caso, o tempo consumido pelo algoritmo é $O(n\cdot n^2!)$.

Por exemplo: se $n=5$, temos que $n\cdot n^2! = 7.75560502\times 10^{25}$; se $n=8$, temos que $n\cdot n^2! = 1.01509546\times 10^{90}$.

Em Novembro/2019, o supercomputador mais rápido em operação é o Summit - IBM Power System AC922, em operação no Oak Ridge National Laboratory, United States, com $148.6$ petaflops (em que um petaflop é igual a $10^{15}$ operações com pontos flutuantes por segundo).

As operações no algoritmo acima são sobre inteiros e não pontos flutuantes. Suponha que temos um supercomputador que realiza operações com inteiros $100$ vezes mais rápido que com pontos flutuantes (totalmente hipotético) e que nosso supercomputador é $1$ milhão de vezes mais rápido que o Summit. Isto é, nosso supercomputador hipotético realiza $148.6\times 10^{23}$ operações inteiras por segundo (não existe, no momento, um supercomputador com esse poder; e levará muitos anos até atingirmos esta marca).

O tempo necessário para processar $n\cdot n^2!$ (vamos desconsiderar as constantes envolvidas) operações, com $n=8$, seria: $$T = \frac{1.01509546\times 10^{90}}{148.6\times 10^{23}} = 6.83105962\times 10^{64} ~ \text{segundos}.$$ Um ano possui aproximadamente $60\cdot 60\cdot 24\cdot 365.25 = 31557600 < 3.2\times 10^7$ segundos. Logo, $$T > 2.13470613\times 10^{57} ~ \text{anos.}$$ Compare o valor acima com a idade estimada do universo: $1.38\times 10^{10}$ anos.

Uma observação positiva. A estrutura do grafo subjacente ao problema do caminho do cavalo é especial e altamente simétrica. Explorando estas características, é possível desenvolvermos um algoritmo linear em $n^2$.

E uma negativa. Inúmeros problemas de interesse teórico e prático possuem a mesma estrutura combinatória, mas carecem de subestruturas especiais. Para estas variantes, o melhor que sabemos fazer é um algoritmo de tempo $O(m\cdot 2^m)$, às custas de um uso de memória da ordem de $O(2^m)$ — note que nosso algoritmo acima requer $O(m)$ de memória, para $m=n^2$. Até o momento, não sabemos se é possível resolvê-los exatamente em tempo sub-exponencial em $m$. Uma resposta (afirmativa ou negativa) a esta questão conferirá US$ 1 milhão a seu autor, além de reconhecimento e fama.

$\square$

• (14) Permutações aleatórias uniformes.
  Escreva uma função que devolve uma permutação aleatória de $\{0,1,\ldots,n-1\}$.
  Dica: utilize as funções random.seed() e random.randrange() do módulo random.

  Solução:
  

  import random
  
  def shuffle (A: [int]):
    random.seed()
    for i in range (len(A) - 1, 0, -1):
      j = random.randrange (i + 1)
      A[i], A[j] = A[j], A[i]
  

  Nota: Compare a solução acima com o exercício 8 da L1 .
  $\square$