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$

Avatar
Aritanan Gruber
Assistant Professor

“See, if y’all haven’t the same feeling for this, I really don’t give a damn. If you ain’t feeling it, then dammit this ain’t for you!“
(desconheço a autoria; agradeço a indicação)