En lingüística recreativa, un exercici interessant a fer amb les paraules és el de construir un graf amb les seves lletres.
Com a exemple simple, s'agafen les diferents lletres de la paraula "PARAIGUA", i es connecten segons l'ordre d'aparició en la paraula, per tant, unint P-A, A-R, etc.
En la majoria de casos, tot i que el dibuix obtingut pot arribar a ser molt complex, el graf serà planar, és a dir, és possible construir-lo sense que les arestes es creuin. Tot i això, hi ha unes poques excepcions que reben el nom d'aodarmdroma (o en anglès, eodermdrome), ja que la mateixa paraula forma un graf no planar perfecte de tipus K5.
La paraula serà no planar si conté algun subconjunt no planar K5 o K3,3.
L'exemple retorna una list que indica que s'ha trobat un subgrup de tipus K5. La primera llista de lletres correspon als nodes del subgrup no planar, mentre que les altres dues llistes indiquen altres subdivisions i arestes que puguin existir a la paraula. Tal com ja s'ha comentat, en aquest cas es tracta d'un graf no planar perfecte, per això les dues darreres llistes estan buides.
Com a exemple simple, s'agafen les diferents lletres de la paraula "PARAIGUA", i es connecten segons l'ordre d'aparició en la paraula, per tant, unint P-A, A-R, etc.
Codi:
P----A----R
/ \
/ \
U--G--IEn la majoria de casos, tot i que el dibuix obtingut pot arribar a ser molt complex, el graf serà planar, és a dir, és possible construir-lo sense que les arestes es creuin. Tot i això, hi ha unes poques excepcions que reben el nom d'aodarmdroma (o en anglès, eodermdrome), ja que la mateixa paraula forma un graf no planar perfecte de tipus K5.
La paraula serà no planar si conté algun subconjunt no planar K5 o K3,3.
Codi
El següent codi lliure d'ús fet amb Python permet buscar tots els subconjunts no planars d'una paraula, i així determinar si és o no un aodarmdroma.Codi:
# ==============================================================================================
# * aodarmdroma.py
# ----------------------------------------------------------------------------------------------
# Aquest codi Python permet trobar els grups no planars d'una paraula
#
# Requereix un format de paraula net, en majúscules, sense accents, ela geminada, o guionets.
# També es recomana substutir 'Ç' per 'c' per treballar amb una versió ASCII amigable.
#
# Autor: Wecoc
# Versió: 1.0 [2 de juny 2022]
# Més info: https://wec-codes.forumotion.com/t20-linguistica-recreativa-el-cas-de-l-aodarmdroma
# ==============================================================================================
from itertools import permutations, combinations
# Comptar quantes vegades apareix una determinada lletra a la paraula
def letter_count(letter, word):
result = 0
for chr in [char for char in word]:
if chr == letter:
result += 1
return result
# Aplicar itertools:combinations per tota N de 0 a la llargada de la llista, i retornar una altra llista
def combination_set(ary):
result = []
for i in range(0, len(ary)+1):
result = result + list(map(lambda x : list(x), combinations(ary, i)))
return result
# Treure repetits de la llista
def unique(list):
unique_list = []
for x in list:
if x not in unique_list:
unique_list.append(x)
return unique_list
class WordChain:
# Iniciar classe WordChain
def __init__(self, word):
self.word = word
# Obtenir un llistat de les lletres que apareixen més d'un cop a la paraula
self.letters = list(set([char for char in self.word]))
self.letters = list(filter(lambda letter: letter_count(letter, self.word) > 1, self.letters))
self.letters.sort(key=word.index)
# Construir ponts entre les lletres
self.bridges = []
self.sub_bridges = []
self.generate_bridge_combinations()
# Obtenir els grups no planars per cada pont generat
self.non_planar_groups = []
self.generate_non_planar_groups()
# Per cada grup no planar obtenir subdivisions i arestes addicionals
self.generate_extra_edges()
# Construir ponts entre les lletres
def generate_bridges(self, bridge_data, letters):
start_index = 0
# Buscar la primera lletra que es troba a la llista
for i in range(0, len(self.word)):
char = self.word[i]
if char in letters:
last_char = char
break
start_index += 1
# Buscar la següent lletra disponible per crear-ne el pont
for i in range(start_index + 1, len(self.word)):
char = self.word[i]
if ((last_char == char) or (char not in letters)):
continue
self.store_bridge(bridge_data, last_char, char)
last_char = char
# Emmagatzemar el pont generat
def store_bridge(self, bridge_data, last, current):
p0 = min(last, current)
p1 = max(last, current)
if [p0, p1] not in bridge_data:
bridge_data.append([p0, p1])
# Construir els ponts a partir de les combinacions possibles
def generate_bridge_combinations(self):
# Obtenir totes les combinacions possibles de ponts
combination = combination_set(self.letters)
combination = list(filter(lambda c: len(c) >= 5, combination))
for c in combination:
current_bridges = []
# Buscar ponts vàlids per cada possible combinació
self.generate_bridges(current_bridges, c)
self.bridges.append(current_bridges)
# Ordenar els ponts obtinguts
self.bridges = list(map(lambda bridge: sorted(bridge), self.bridges))
# Generar grups no planars
def generate_non_planar_groups(self):
candidates = []
bridge_givens = {}
# Buscar les instàncies de cada possible pont obtingut
for bridge_group in self.bridges:
for bridge in bridge_group:
p0 = bridge[0]; p1 = bridge[1]
if p0 not in bridge_givens:
bridge_givens[p0] = 0
if p1 not in bridge_givens:
bridge_givens[p1] = 0
bridge_givens[p0] += 1
bridge_givens[p1] += 1
# Per cada possible pont, buscar k5 i k33 segons les instàncies obtingudes
for bridge_group in self.bridges:
self.search_groups_k5(bridge_givens, bridge_group)
self.search_groups_k33(bridge_givens, bridge_group)
# Eliminar ponts repetits
self.non_planar_groups = unique(self.non_planar_groups)
# Buscar grafs no planars de tipus k5
def search_groups_k5(self, givens, bridge_group):
# Per tenir un graf k5 calen 5 punts amb almenys 4 arestes cadasun
data = list({k: v for k, v in givens.items() if v >= 4}.keys())
if len(data) < 5:
return
# Obtenir les combinacions possibles de 5 punts
c_data = list(map(lambda c : list(c), combinations(data, 5)))
# Per cada possible combinació, buscar si es compleix la necessària per tenir un k5
for c in c_data:
c.sort()
c0 = c[0]; c1 = c[1]; c2 = c[2]; c3 = c[3]; c4 = c[4]
outside = [[c0, c1], [c1, c2], [c2, c3], [c3, c4], [c4, c0]] # Pentàgon
inside = [[c0, c2], [c0, c3], [c1, c3], [c1, c4], [c2, c4]] # Estrella
k_possible = True
for k in (outside + inside):
filtered = list(filter(lambda b: (min(b) == min(k) and max(b) == max(k)), bridge_group))
if len(filtered) == 0:
k_possible = False
# Si després de totes les comprovacions k5 encara és possible, guardar-lo
if k_possible == True:
ary = sorted(c, key=self.word.index)
self.non_planar_groups.append(["k5", ary])
# Buscar grafs no planars de tipus k33
def search_groups_k33(self, givens, bridge_group):
# Per tenir un graf k33 calen 6 punts amb almenys 3 arestes cadasun
data = list({k: v for k, v in givens.items() if v >= 3}.keys())
if len(data) < 6:
return
# Obtenir les permutacions possibles de 6 punts
c_data = list(map(lambda c : list(c), combinations(data, 6)))
p_data = {}
for c in c_data:
p_data[tuple(c)] = list(map(lambda p : list(p), permutations(c, 6)))
# Per cada possible permutació, buscar si es compleix la necessària per tenir un k33
for c in c_data:
for p in p_data[tuple(c)]:
c0 = p[0]; c1 = p[1]; c2 = p[2]; c3 = p[3]; c4 = p[4]; c5 = p[5]
group0 = [[c0, c3], [c0, c4], [c0, c5]]
group1 = [[c1, c3], [c1, c4], [c1, c5]]
group2 = [[c2, c3], [c2, c4], [c2, c5]]
k_possible = True
for k in (group0 + group1 + group2):
filtered = list(filter(lambda b: (min(b) == min(k) and max(b) == max(k)), bridge_group))
if len(filtered) == 0:
k_possible = False
# Si després de totes les comprovacions k33 encara és possible, guardar-lo
if k_possible == True:
ary = [[c0, c1, c2], [c3, c4, c5]]
ary = list(map(lambda x: sorted(x, key=self.word.index), ary)); ary.sort()
self.non_planar_groups.append(["k33", ary])
# Obtenir subdivisions i arestes addicionals
def generate_extra_edges(self):
for group in self.non_planar_groups:
# Obtenir lletres implicades en el grup no planar
if group[0] == "k5":
a = ''.join(group[1])
b = ''.join(group[1])
if group[0] == "k33":
a = ''.join(group[1][0])
b = ''.join(group[1][1])
# Buscar tots els casos possibles d'arestes addicionals
l = ''; s = ''
result = []
others = []
for i in range(0, len(self.word)):
letter = self.word[i]
s = s + letter
# Connexió entre dos lletres del mateix grup k33
if (((l == 'a') and (letter in a) and (letter not in b)) or
((l == 'b') and (letter in b) and (letter not in a))):
# CAS A: Lletres entremig d'un pont
if (len(s) > 2):
others.append(s)
# CAS B: Connexió directa entre lletres del mateix grup
else:
others.append(s)
s = letter
continue
# Connexió entre lletres de grups diferents k33 o bé grup k5
if (letter not in a) and (letter not in b):
continue
# CAS A: Lletres entremig d'un pont
if (len(s) > 2):
result.append(s)
# CAS E1: Aresta inicial (principi de paraula)
elif (len(s) > 1 and l == ''):
others.append(s)
if letter in a:
l = 'a'
if letter in b:
l = 'b'
s = letter
# CAS E2: Aresta final (final de paraula)
if len(s) > 1:
others.append(s)
# Emmagatzemar els resultats al final del grup
result = unique(result)
others = unique(others)
group.append(result)
group.append(others)
# Retornar els non_planar_groups filtrats segons el tipus (k5 o k33)
def filter_groups(self, type):
result = []
for group in self.non_planar_groups:
if group[0] == type:
result.append(group)
return result
Exemple d'ús
El codi es pot utilitzar de la següent manera:Codi:
# ==============================================================================================
# * aodarmdroma_example.py
# ==============================================================================================
# Importar el codi principal
from aodarmdroma import WordChain
# Generar graf a partir de la paraula AODARMDROMA
word = "AODARMDROMA"
chain = WordChain(word)
# Mostrar els grups no planars obtinguts
print(chain.non_planar_groups)
# => [['k5', ['A', 'O', 'D', 'R', 'M'], [], []]]L'exemple retorna una list que indica que s'ha trobat un subgrup de tipus K5. La primera llista de lletres correspon als nodes del subgrup no planar, mentre que les altres dues llistes indiquen altres subdivisions i arestes que puguin existir a la paraula. Tal com ja s'ha comentat, en aquest cas es tracta d'un graf no planar perfecte, per això les dues darreres llistes estan buides.
