CCM0128 - Computação II (2025i)

Neste exercício, você implementará o algoritmo de Hammersley, estudado na aula do dia 29/5/2025. Revise também o exercício S06 O teorema de Erdős e Szekeres.

Partições de conjuntos.  Seja \(I\) um conjunto. Uma parte de $I$ é um subconjunto de $I$. Uma partição de $I$ é um conjunto $\mathcal P$ de partes de $I$ tal que (i) todo $X\in{\mathcal P}$ é não vazio, (ii) para quaisquer elementos $X$ e $Y$ distintos de $\mathcal P$, temos que $X\cap Y=\emptyset$ e (iii) a união de todos os elementos de $\mathcal P$ é $I$.

Exemplo 1.  Seja $I=\{0,1,\dots,11\}$. Sejam $X_0=\{0,2\}$, $X_1=\{1,4,7\}$, $X_2=\{3,6,9\}$, $X_3=\{5,8\}$, $X_4=\{10\}$ e $X_5=\{11\}$. Então ${\mathcal P}=\{X_0,\dots,X_5\}$ é uma partição de $I$.

Exemplo 2.  Seja $n$ um inteiro não-negativo e seja $[n]=\{1,\dots,n\}$ (note que $[0]=\emptyset$). Podemos nos perguntar quantas partições o conjunto $[n]$ admite. Seja $B_n$ esse número. Você pode achar interessante determinar $B_n$ para valores pequenos de $n$. (Temos $B_0=1$, $B_1=1$, $B_2=2$ e $B_3=5$.)

Decomposição em subsequências decrescentes (DSD).  Seja \(x\) uma sequência $x_0,x_1,\dots,x_{N-1}$ de inteiros. Uma decomposição em subsequências decrescentes (DSD) de $x$ é uma partição $\mathcal P$ de $I=\{0,\dots,N-1\}$ (o conjunto de índices de $x$), tal que cada parte $X$ de $I$ em $\mathcal P$ determina uma subsequência decrescente de $x$.

Exemplo 3.  Seja $x$ a seguinte sequência: $2$, $7$, $1$, $8$, $2$, $8$, $3$, $1$, $4$, $1$, $5$, $9$. A partição $\mathcal P$ de $I=\{0,\dots,11\}$ no Exemplo 1 acima é uma DSD de $x$. Podemos ilustrar esta DSD de forma mais intuitiva desta forma:

0: 2 1
1: 7 2 1
2: 8 3 1
3: 8 4
4: 5
5: 9

(Note que no diagrama acima, temos os elementos da sequência $x$ e não os seus índices; isto é, os $x_i$ e não os $i$.)

A classe Patience.java.  Neste exercício, você deverá escrever uma classe chamada Patience.java que implementa a seguinte API:

public class Patience
---------------------------------------
       Patience(int[] s)
public Queue<Integer>[] piles()
public int[] lis()

Suponha que o vetor s contenha uma sequência de $N$ inteiros. A chamada do construtor new Patience(s) deve devolver um objeto do tipo Patience, digamos pp, com as propriedades abaixo.

A chamada pp.piles() deve devolver um vetor de filas, digamos qq, que especifica uma DSD de $x$ com o menor número de partes possível. No caso da sequência $x$ do Exemplo 3, o vetor de filas qq deve ter 6 elementos. Cada um desses elementos deve ser uma fila. A fila qq[0] poderia conter os elementos $2$ e $1$, nessa ordem; a fila qq[1] poderia conter os elementos $7$, $2$ e $1$, nessa ordem; etc. Intuitivamente falando, as filas em qq devem conter subsequências decrescentes que decompõe $x$.

A chamada pp.lis() deve devolver um vetor, digamos lis, que contenha uma LIS de $x$. No caso da sequência $x$ acima, poderíamos ter

lis = {1, 2, 3, 4, 5, 9}

Importante.  A chamada do construtor deve executar o algoritmo de Hammersley na sequência dada, e assim deve já obter os objetos que devem ser devolvidos pelas chamadas de piles() e lis() quando elas forem executadas pelo cliente.

Um cliente.  Sua classe Patience.java será testada de várias formas; em particular, ela será testada com o cliente TestPatience.java dado abaixo. O usuário pode fornecer um inteiro na linha de comando a este cliente. Este inteiro é usado para controlar o quão detalhada a saída de TestPatience.java deve ser. A sequência a ser processada por TestPatience.java deve ser dada na entrada padrão.

Alguns exemplos de execução de TestPatience.java.  Os programas RandomPerm.java e RandomSeqNS.java podem ser usados para gerar instâncias para TestPatience.java. Seguem alguns exemplos de execução.

$ java-introcs RandomSeqNS 10 3 8888
-3 1 5 4 4 8 6 5 10 8
$ java-introcs RandomSeqNS 10 3 8888 | java-introcs TestPatience 3
Decomposition in DSs:
0: -3
1: 1
2: 5 4
3: 4
4: 8 6 5
5: 10 8
A LIS (6 elements):
-3 1 4 4 5 8
Time to read data: 0.058
Time to compute decomposition & LIS: 0.005
$ java-introcs RandomSeqNS 10 3 8888 | java-introcs TestPatience 2
A LIS (6 elements):
-3 1 4 4 5 8
Time to read data: 0.048
Time to compute decomposition & LIS: 0.005
$ java-introcs RandomSeqNS 10 3 8888 | java-introcs TestPatience 1
Decomposition in DSs:
0: -3
1: 1
2: 5 4
3: 4
4: 8 6 5
5: 10 8
Time to read data: 0.049
Time to compute decomposition & LIS: 0.004
$ java-introcs RandomSeqNS 10 3 8888 | java-introcs TestPatience
6
Time to read data: 0.049
Time to compute decomposition & LIS: 0.004
$ java-introcs RandomPerm 100000 8888 > tmp; java-introcs TestPatience < tmp; rm tmp
623
Time to read data: 0.245
Time to compute decomposition & LIS: 0.087
$ java-introcs RandomPerm 1000000 8888 > tmp; java-introcs TestPatience < tmp; rm tmp
1976
Time to read data: 0.68
Time to compute decomposition & LIS: 0.361
$ java-introcs RandomPerm 10000000 8888 > tmp; java-introcs TestPatience < tmp; rm tmp
6289
Time to read data: 5.852
Time to compute decomposition & LIS: 3.126
$ java-introcs RandomPerm 20000000 8888 > tmp; java-introcs TestPatience < tmp; rm tmp
8911
Time to read data: 10.855
Time to compute decomposition & LIS: 6.483
$

O arquivo example_runs.txt dado abaixo contém mais exemplos de execução.

Desempenho.  Espera-se que sua implementação de Patience.java seja tal que, quando TestPatience.java for executado com seu Patience.java, veremos tempos de execução não muito diferentes daqueles nos exemplos fornecidos.

Observação.  Se você estivesse interessado em implementar apenas a parte do algoritmo de Hammersley que obtém uma DSD mínima, bastaria usar um vetor de pilhas de inteiros. Entretanto, para implementar a parte do algoritmo que encontra uma LIS, será conveniente usar um vetor de pilhas de objetos do tipo Card, onde Card é uma classe interna auxiliar (veja o esqueleto de Patience.java fornecido).