Eu posso definir uma palavra como sendo um conjunto de tuplas formadas por caracter/posição. Assim, a palavra banana
teria a seguinte representação matemática:
{
('b',0),
('a',1),
('n',2),
('a',3),
('n',4),
('a',5)
}
Posso mudar um pouco a definição para que cada letra seja mapeada para um conjunto de posições; então, banana
ficaria assim:
{
('b',{0}),
('a',{1,3,5}),
('n',{2,4})
}
Algo interessante dessa definição é que, se a minha letra não estiver na palavra, posso associar ela ao conjunto vazio:
{
('a',{1,3,5}),
('b',{0}),
('c',{}),
('d',{}),
('e',{}),
('f',{}),
('g',{}),
('h',{}),
('i',{}),
('j',{}),
('k',{}),
('l',{}),
('m',{}),
('n',{2,4}),
('o',{}),
('p',{}),
('q',{}),
('r',{}),
('s',{}),
('t',{}),
('u',{}),
('v',{}),
('w',{}),
('x',{}),
('y',{}),
('z',{})
}
Esse tipo de estrutura de dados, de uma chave mapear para um conjunto de elementos, é chamada de multimapa. De modo geral, o multimapa tem duas operações: inserir valor e resgatar conjunto.
Então, no multimapa de banana
(doravante denominado de mm_banana
), podemos adicionar s
na posição 6
:
mm_banana.put('s', 6)
// conteúdo de mm_banana modificado sem conjuntos vazios:
{
('a',{1,3,5}),
('b',{0}),
('n',{2,4}),
('s',{6})
}
Se adicionamos 's',6
, 'e',7
e 's',8
a mm_banana
, ficaria assim:
mm_banana.put('s', 6)
mm_banana.put('e', 7)
mm_banana.put('s', 8)
// conteúdo de mm_banana modificado sem conjuntos vazios:
{
('a',{1,3,5}),
('b',{0}),
('e',{7}),
('n',{2,4}),
('s',{6,8})
}
A representação decimal de um número é um multimapa de palavra (conforme descrito acima), sendo que o alfabeto da chave são os dígitos decimais.
Para, a partir de um número qualquer x
, obter sua representação decimal, fazemos divisões sucessivas e armazenamos o resto. Por uma questão de simplicidade, vamos considerar a escrita da palavra decimal em little-endian, onde os menos significativos vem primeiro. Assim, o número 0x10
tem sua representação em palavra decimal little-endian 61
. O seguinte código em Python a seguir demonstra isso:
def representacao_base(x, base):
digit_pos = 0
while (x > 0):
digito = x % base
print("digito %d, posição %d" % (digito, digit_pos));
x //= base
digitPos += 1
representacao_base(0x10, 10)
Veja funcionando no ideone.
Notou que eu escrevi de modo generalizado para qualquer base? Pois é, a vantagem disso é que podemos verificar se um número é capicua em qualquer base mais adiante. Então, 12 seria representado como 0011
na base 2 usando little-endian. O endianismo não influi na decisão do número ser capicua ou não, assim como escrever uma palavra ao contrário não influencia no fato de ela ser ou não palíndroma.
Para detectar que um número é capicua, usamos o algoritmo acima para desmembrá-lo e colocar cada dígito como chave do multimapa, cada posição como sendo o valor sendo inserido no multimapa. Em Java, alcancei isso da seguinte maneira:
public class Multimapa {
Set<Integer>[] pos;
int size;
int base;
private void initPos(int base) {
pos = new HashSet[base];
for (int i = 0; i < base; i++) {
pos[i] = new HashSet<>();
}
}
public Multimapa(int n, int base) {
this.base = base;
initPos(base);
if (n == 0) {
pos[0].add(0);
size = 1;
return;
}
if (n < 0) {
n = -n;
}
int digitPos = 0;
while (n > 0) {
int digit = n % base;
pos[digit].add(digitPos);
n /= base;
digitPos++;
}
size = digitPos;
}
}
Note que, como a chave é um dígito, e um dígito por sua vez é um número inteiro, o multimapa é fornecido pelo atributo pos
; pos[7]
vai obter as posições em little-endian que o dígito 7 ocupa na base passada. Detalhe: a chave é um inteiro e o valor é um conjunto (set em inglês significa conjunto em português, no contexto matemático) de inteiros.
Assim, para demonstrar que a classe Multimapa
se comporta como a estrutura de dados multimapa descrita acima, preciso mostrar que ela suporta as mesmas operações de inserção e de resgate.
A operação de resgate é simples. Dado um dígito d
, pos[d]
resgata o conjunto correspondente. Para fazer a adição da posição p
ao dígito d
, basta fazer pos[d].add(p)
. Note que essa é uma operação idempotente, então pos[d].add(p);
tem o mesmo efeito de pos[d].add(p); pos[d].add(p); pos[d].add(p);
.
Lembra da representação da palavra com multimapa usando conjunto vazio para a não existência daquela letra na palavra? Estamos usando o mesmo conceito aqui, para facilitar as operações de resgate e adição sem precisar de tratativas adicionais nem ofender a definição.
Para determinar se o número é repetido, podemos verificar se ele tem mais de um dígito não nulo. Para tal, basta iterar nos dígitos e verificar o tamanho dos conjuntos. Se existir apenas um dígito com tamanho não nulo, então o número é repetido. Para detectar se é não repetido, basta fazer a inversão lógica. Como não há a opção de número sem dígito, então o mínimo de dígitos com pelo menos uma posição no número é 1. Portanto, a negação de ser número com um único dígito é ter a contagem > 1
.
private static boolean ehNaoRepetido(Multimapa mm) {
int nDigitosDistintos = 0;
for (int i = 0; i < mm.base; i++) {
nDigitosDistintos += mm.pos[i].size() > 0? 1: 0;
}
return nDigitosDistintos > 1;
}
Para verificar se um número é capicua na base definida, precisamos garantir que todo dígito na posição p
tem outro dígito na posição especular p'
. Um caso especial é o número da posição intermediária com números de tamanho ímpar: ele é seu próprio especular, portanto ele pode ser ignorado.
A relação entre p
, p'
e o tamanho size
do número é:
p + p' = size - 1
||
\/
p' = size - 1 - p
A posição intermediária t
, que vai ser ignorada, é calculada assim:
t = size % 2 == 1? size/2: -1;
Como só existem posições preenchidas a partir do 0, colocar -1 vai garantir que t
sempre será ignorado para números de um tamanho par de dígitos.
Assim, a seguinte verificação trata disso:
private static boolean ehCapicua(Multimapa mm) {
int somaSimetrica = mm.size - 1;
int posIgnorada = mm.size % 2 == 1? mm.size/2: -1;
for (int d = 0; d < mm.base; d++) {
for (Integer p: mm.pos[d]) {
// só tenta verificar se tem o complemento se e somente se não é ignorado
if (p != posIgnorada) {
int posComplemento = somaSimetrica - p;
// se não existe o dígito na posição complementar, então não é capicua
if (!mm.pos[d].contains(posComplemento)) {
return false;
}
}
}
}
return true;
}
Segue o código completo usado para verificar se um número é capicua não repetido nas bases determinadas:
package capicua;
import java.util.HashSet;
import java.util.Set;
public class Multimapa {
Set<Integer>[] pos;
int size;
int base;
private void initPos(int base) {
pos = new HashSet[base];
for (int i = 0; i < base; i++) {
pos[i] = new HashSet<>();
}
}
public Multimapa(int n, int base) {
this.base = base;
initPos(base);
if (n == 0) {
pos[0].add(0);
size = 1;
return;
}
if (n < 0) {
n = -n;
}
int digitPos = 0;
while (n > 0) {
int digit = n % base;
pos[digit].add(digitPos);
n /= base;
digitPos++;
}
size = digitPos;
}
public static void main(String... args) {
int qntNumerosInteressantes = 0;
for (int i = 0; i < 99999999; i++) {
if (julga(i, 10)) {
System.out.println(i + " é capicua não repetido na base " + 10);
qntNumerosInteressantes++;
}
}
System.out.println("quantidade de números capicua e não repetidos nas base 10: " + qntNumerosInteressantes);
qntNumerosInteressantes = 0;
for (int i = 0; i < 99999999; i++) {
if (julga(i, 16)) {
System.out.println(i + " é capicua não repetido na base " + 16);
qntNumerosInteressantes++;
}
}
System.out.println("quantidade de números capicua e não repetidos nas base 16: " + qntNumerosInteressantes);
meta_julga(0xffeff, 10); // 1048319
meta_julga(121, 10);
meta_julga(1221, 10);
meta_julga(12721, 10);
meta_julga(12721, 16); // 31b1
meta_julga(0xffeff, 16);
meta_julga(0xffdead, 16);
meta_julga(0101, 8);
meta_julga(0171, 8);
meta_julga(01267621, 8);
meta_julga(01267421, 8);
meta_julga(5, 2); // 101
meta_julga(6, 2); // 110
meta_julga(7, 2); // 111
meta_julga(4, 2); // 10
meta_julga(16, 3); // 121
meta_julga(10, 3); // 101
meta_julga(12, 3); // 110
}
private static void meta_julga(int n, int base) {
if (julga(n, base)) {
System.out.println(n + " é capicua não repetido na base " + base);
} else {
System.out.println(n + " não é capicua não repetido na base " + base);
}
}
// retorna verdade se todos os dígitos do número passado forem idênticos
//
// algoritmo de detecção: se, por acaso, existirem pelo menos dois dígitos com 1 ou mais posições, então é não repetido.
// caso seja tudo zero exceto por um único dígito, então é repetido
private static boolean ehNaoRepetido(Multimapa mm) {
int nDigitosDistintos = 0;
for (int i = 0; i < mm.base; i++) {
nDigitosDistintos += mm.pos[i].size() > 0? 1: 0;
}
return nDigitosDistintos > 1;
}
// retorna verdadeiro caso seja capicua
//
// algoritmo: verifica cada dígito; se for de tamanho `t` ímpar, então o dígito da posição `floor(t/2)` deve ser ignorado
// para um dígito `d` na posição `p` não ignorado, é necessário existir um outro dígito `d` na posição complementar `p'`, tal que `p + p' = t - 1`
private static boolean ehCapicua(Multimapa mm) {
int somaSimetrica = mm.size - 1;
int posIgnorada = mm.size % 2 == 1? mm.size/2: -1;
for (int d = 0; d < mm.base; d++) {
for (Integer p: mm.pos[d]) {
// só tenta verificar se tem o complemento se e somente se não é ignorado
if (p != posIgnorada) {
int posComplemento = somaSimetrica - p;
// se não existe o dígito na posição complementar, então não é capicua
if (!mm.pos[d].contains(posComplemento)) {
return false;
}
}
}
}
return true;
}
private static boolean julga(int n, int base) {
Multimapa mm = new Multimapa(n, base);
if (ehNaoRepetido(mm)) {
if (ehCapicua(mm)) {
return true;
}
}
return false;
}
}
Veja funcionando no ideone.