Algoritmo para determinar una función discreta

Question

Hola

No sé muy bien qué título poner a esta pregunta ni qué etiquetas utilizar, porque no es mi especialidad y no estoy familiarizado con la terminología. Es un problema que surgió al tratar de escribir un programa para enumerar algunos grafos, sin embargo no hay teoría de grafos en este problema.

Permítanme empezar definiendo los distintos componentes. Tengo un conjunto $C$ y dos funciones: $s:C\rightarrow \mathbb{N}$ y $r:C\rightarrow \mathbb{N}$ . Los valores de estas funciones son completamente conocidos. También es cierto que $\forall c \in C: r(c)=s(c) \vee r(c)=\frac{s(c)}{2}$ . No sé si esto supondrá una diferencia para la solución de mi problema, pero puede ser una información relevante.

Ahora estoy interesado en encontrar todas las funciones posibles $m:C\rightarrow \mathbb{N}$ que cumplan las siguientes condiciones:

• $\sum_{c\in C}\frac{s(c)}{m(c)}=\sum_{c \in C}\frac{s(c)}{4}$
• $\forall c \in C: r(c) \mid m(c)$

Realmente necesito un algoritmo para encontrar todas las soluciones posibles, pero por supuesto también estoy interesado en cualquier resultado teórico que pueda ayudarme a encontrar dicho algoritmo. Como ya he dicho, no estoy muy familiarizado con este tipo de problemas, así que no tengo ni idea de qué buscar y por dónde empezar. Las primeras condiciones hacen que sea imposible tener un número infinito de soluciones, pero en algunos casos tengo algunos mejores límites superiores y límites inferiores disponibles para el valor de la función $m$ en ciertos puntos. Estaría bien tener esto en cuenta, pero creo que no sería el cuello de botella si simplemente filtrara las soluciones para tener en cuenta estos límites.

Cualquier ayuda es muy apreciada. Y, por supuesto, haré todo lo posible para aclarar cualquier cosa en mi explicación que no esté clara.

Edita: Permítanme decir primero que $C$ siempre será finito.

Un pequeño ejemplo también podría ser más clarificador. Supongamos que tenemos $C=\{1,2\}$ la función $s:C\rightarrow\mathbb{N};c\mapsto 2$ y la función $r:C\rightarrow\mathbb{N};c\mapsto 1$ .

Tenemos entonces tres posibles soluciones para $m$ :

• $m(1)=3$ , $m(2)=6$
• $m(1)=4$ , $m(2)=4$
• $m(1)=6$ , $m(2)=3$

Answer 1

Asumiré que $C$ es finito para mi respuesta.

Sea $n,d:C\to\mathbb{N}$ tal que $n\equiv\left.m/r\right.$ y $r\equiv\left.s/d\right.$ . En otras palabras, $\mathrm{im}(d)\subseteq\{1,2\}$ . Sea $C_1:=d^{-1}(1)$ y $C_2:=C\setminus C_1 = d^{-1}(2)$ . Ahora, queremos encontrar una función $n$ tal que

$R := \displaystyle \sum_{c\in C} \frac{d(c)}{n(c)} = \sum_{c\in C} \frac{s(c)\cdot d(c)}{s(c)\cdot n(c)} = \sum_{c\in C} \frac{s(c)}{r(c)\cdot n(c)}= \sum_{c\in C} \frac{s(c)}{m(c)} = \sum_{c\in C} \frac{s(c)}{4} =: S$

Reclamación. Este problema tiene solución si y sólo si $2\le S\le|C_1|+2|C_2|$ .
Prueba. Consideramos que $S\in\mathbb{Q}$ y realizar la inducción en $r$ où $C=\{c_1,\ldots,c_r\}$ . En el caso $r=1$ la declaración es clara. Supongamos ahora que $S>|C_1|+2|C_2|$ . Entonces, no importa cómo elijamos $n(c_r)$ por inducción no podemos encontrar una solución válida para $S'=S-d(c_r)/n(c_r)$ en $C'=\{c_1,\ldots,c_{r-1}\}$ .

En caso de que $S\le|C_1|+2|C_2|$ sin embargo, se puede calcular una solución fijando $n\equiv 1$ Así que $R=|C_1|+2|C_2|$ . Entonces tenemos que disminuir $R$ hasta alcanzar el valor deseado.

Para $d=1,2$ podemos disminuir $R$ por $dr-1$ de la siguiente manera: Elige $\{c_1,\ldots,c_r\}\subseteq C_d$ y establece $n(c_i):=dr$ para todos $i$ . El siguiente código python

def n(c):
    n=([1]*c[1],[1]*c[2])
    D = 2*c[2] + c[1] - c[0]
    for d in (1,2):
        j,r = 0,c[d]
        ctr = c[d]
        while r > 0 and D != 0:
            if d*r-1 <= D:
                D -= d*r-1
                n[d-1][j:j+r] = [d*r]*r
                j += r
                ctr -= r
                r = ctr
            else:
                r -= 1
    print n[0]+n[1]

espera una entrada de la forma $(S,|C_1|,|C_2|)$ y devuelve la función $n$ con mi anotación. En su ejemplo anterior, $S=1$ , $|C_1|=0$ y $|C_2|=2$ el resultado es

>>> n((1,0,2))
[4, 4]

que es la segunda de sus soluciones. Creo que esto debería funcionar.