E05 (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 imprimir 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 não-vazias
$d, b, a, c, bc, ac$
e as subsequências decrescentes não-vazias
$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 imprime 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
$
Note que, nas listagens das $(a, b)$-permutações acima, não exigimos nenhuma ordem particular.
Mais exemplos de execução. Veja alguns exemplos de execução nos arquivos anexos. Os tempos de execução de seu programa devem ser comparáveis aos tempos nesses exemplos.
Entrega. Entregue apenas seu programa ABPerms.java.
- 16 settembre 2021, 19:11
- 16 settembre 2021, 19:11