BCM0505-15 - Processamento da Informação

Aula A03 – 01/05: Permutações em vetores

• Permutações cíclicas, alternantes e adjacentes.
• Enumeração de permutações em ordem lexicográfica.
• Geração de uma permutação aleatória de forma uniforme.

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]$.

Problemas

Problema A3.1: 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$.

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

Versão utilizando enumerate:

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

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

Problema A3.2: 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\}$.

Vamos utilizar uma lista auxiliar $B$.

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)

Problema A3.3: 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$.

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

Problema A3.4: Permutações cíclicas II.
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.

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

Problema A3.5: 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.

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]]

Problema A3.6: 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.

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  

Problema A3.7: 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$.

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

Problema A3.8: 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.

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

Problema A3.9: 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$.

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)$.

Problema A3.10: Permutações aleatórias uniformes.
Escreva uma função que devolve uma permutação aleatória de $\{0,1,\ldots,n-1\}$.

Utilizamos as funções random.seed() e random.randrange() do módulo random.

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 .

Problema A3.11: 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].$$

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

Problema A3.12: Enumeração II.
Escreva uma função que devolve em uma lista todas as $5!$ permutações para $\{1,2,3,4,5\}$.

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

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$. Abaixo, desenvolvemos um algoritmo uniforme, que funciona para qualquer valor inteiro de $n\geq 1$.

Problema A3.13: 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.

Considere o seguinte algoritmo:
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).

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$.

Problema A3.14: 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.
Sugestão: 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.

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.