E08 (a, b)-Permutações
Vamos considerar aqui permutações das letras 'a', \(\dots\), 'z'. Mais precisamente, dado \(1\leq N\leq26\), vamos considerar permutações das $N$ primeiras letras de 'a' a 'z'. Seja $\Sigma_N$ o conjunto das $N$ primeiras letras em 'a', $\dots$, 'z'. Seu programa deve receber $N$ e dois outros inteiros $a$ e $b$, e deve determinar todas as $(a, b)$-permutações das letras em $\Sigma_N$. Neste exercício, $(a, b)$-permutações são definidas como segue.
Considere a permutação
\(p = dbac\)
das letras em $\Sigma_4$. Note que esta permutação $p$ contém as subsequências crescentes
$d, b, a, c, bc, ac$
e as subsequências decrescentes
$d, b, a, c, db, da, dc, ba, dba$.
Como todas as subsequências crescentes de $p$ têm comprimento menor ou igual a $2$ e as subsequências decrescentes de p têm comprimento menor ou igual a $3$, dizemos que $p$ é uma $(2, 3)$-permutação. Por definição, a permutação $p$ é também uma $(a, b)$-permutação para quaisquer $a$ e $b$ com $a\geq2$ e $b\geq3$.
Escreva um programa chamado ABPerms.java que recebe $N$, $a$ e $b$ como argumentos de linha de comando e que determina todas as $(a, b)$-permutações das letras em $\Sigma_N$. Você deve supor que $1\leq N\leq26$.
Quando executado com os três argumentos $N$, $a$ e $b$, seu programa deve simplesmente devolver na saída padrão o número de $(a, b)$-permutações de $\Sigma_N$.
$ java-introcs ABPerms 6 3 2
25
$
Escreva seu programa de forma que ele também possa receber um quarto argumento na linha de comando. Quando este argumento é "-v", seu programa deve devolver na saída padrão todas as $(a, b)$-permutações de $\Sigma_N$.
$ java-introcs ABPerms 6 3 2 -v
badcfe
badfce
baecfd
baefcd
bdacfe
bdafce
bdface
beacfd
beafcd
befacd
cadbfe
cadfbe
caebfd
caefbd
cdabfe
cdafbe
cdfabe
ceabfd
ceafbd
cefabd
daebfc
daefbc
deabfc
deafbc
defabc
$
Quando este quarto argumento for "-V", seu programa deve imprimir tanto a lista das (a, b)-permutações de $\Sigma_N$ quanto o número total delas.
$ java-introcs ABPerms 6 3 2 -V
badcfe
badfce
baecfd
baefcd
bdacfe
bdafce
bdface
beacfd
beafcd
befacd
cadbfe
cadfbe
caebfd
caefbd
cdabfe
cdafbe
cdfabe
ceabfd
ceafbd
cefabd
daebfc
daefbc
deabfc
deafbc
defabc
25
$
Mais exemplos de execução. Veja alguns exemplos de execução nos arquivos anexos (execuções em máquinas diferentes). Os tempos de execução de seu programa devem ser comparáveis aos tempos nesses exemplos.
Entrega. Entregue apenas seu programa ABPerms.java.
- 19 outubro 2021, 12:28 PM
- 19 outubro 2021, 12:28 PM