Subconjuntos de pedidos de suma

22

Un conjunto de nnúmeros positivos tiene 2^nsubconjuntos. Llamaremos a un conjunto "agradable" si ninguno de esos subconjuntos tiene la misma suma. {2, 4, 5, 8}Es uno de esos conjuntos bonitos. Como ninguno de los subconjuntos tiene la misma suma, podemos ordenar los subconjuntos por suma:

[{}, {2}, {4}, {5}, {2, 4}, {2, 5}, {8}, {4, 5}, {2, 8}, {2, 4, 5}, {4, 8}, {5, 8}, {2, 4, 8}, {2, 5, 8}, {4, 5, 8}, {2, 4, 5, 8}]

Si etiquetamos los números [2, 4, 5, 8]con los símbolos [a, b, c, d]en orden creciente, obtenemos el siguiente orden abstracto:

[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}]

Otro buen conjunto de números positivos puede tener el mismo orden abstracto o uno diferente. Por ejemplo, [3, 4, 8, 10]es un buen conjunto con un orden abstracto diferente:

[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}]

En este desafío, debe contar el número de ordenamientos abstractos distintos de conjuntos agradables de nnúmeros positivos. Esta secuencia es OEIS A009997 , y los valores conocidos, comenzando en n=1, son:

1, 1, 2, 14, 516, 124187, 214580603

Por ejemplo, para n=3, los siguientes son los dos posibles ordenamientos abstractos:

[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}]

Para n=4, los siguientes son los 14 posibles ordenamientos abstractos, más un buen conjunto de ejemplos con ese ordenamiento:

[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}, {d}, {a, d}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 4, 2, 1]                                       
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {d}, {a, b, c}, {a, d}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 6, 3, 2]                                      
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 7, 4, 2]                                      
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {d}, {a, d}, {b, c}, {a, b, c}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 4, 1]                                       
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 8, 4, 3]                                      
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {a, d}, {b, c}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 7, 4, 2]                                       
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}, {d}, {a, d}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 4, 3, 2]                                      
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {d}, {a, b, c}, {a, d}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 4, 3, 2]                                       
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 5, 4, 2]                                       
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {a, d}, {b, c}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 7, 6, 2]                                      
[{}, {a}, {b}, {c}, {a, b}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 4, 3]                                       
[{}, {a}, {b}, {c}, {a, b}, {d}, {a, c}, {a, d}, {b, c}, {b, d}, {a, b, c}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 8, 6, 3]                                      
[{}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {b, c}, {a, d}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 5, 4]                                       
[{}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [7, 6, 5, 3]

Lo siguiente no es un orden abstracto válido:

{}, {a}, {b}, {c}, {d}, {a,b}, {e}, {a,c}, {b,c}, {a,d}, {a,e}, {b,d}, {b,e}, {c,d}, {a,b,c}, {a,b,d}, {c,e}, {d,e}, {a,b,e}, {a,c,d}, {a,c,e}, {b,c,d}, {b,c,e}, {a,d,e}, {b,d,e}, {a,b,c,d}, {c,d,e}, {a,b,c,e}, {a,b,d,e}, {a,c,d,e}, {b,c,d,e}, {a,b,c,d,e}

Este orden implica que:

d < a + b
b + c < a + d
a + e < b + d
a + b + d < c + e

Sumar estas desigualdades da:

2a + 2b + c + 2d + e < 2a + 2b + c + 2d + e

Lo cual es una contradicción. Su código no debe contar este pedido. Tales contraejemplos aparecen por primera vez en n=5. Ejemplo de este documento , ejemplo 2.5 en la página 3.

Este pedido no es válido a pesar del hecho de que A < Bimplica que A U C < B U C, para cualquier Cdisyunción de Ay B.


Su código o programa debe ser lo suficientemente rápido como para poder ejecutarlo n=4antes de enviarlo.

Las presentaciones pueden ser programas, funciones, etc., como de costumbre.

Las lagunas estándar están prohibidas, como siempre. Este es el código de golf, por lo que la respuesta más corta en bytes gana. Siéntase libre de hacer preguntas aclaratorias en los comentarios.

isaacg
fuente
¡Cuánto tiempo sin verte Isaac!
orlp
P,QPQPQpP,qQ(pq)abc
pP,qQ(pq){a,c},{b,c}
@orlp ¡Qué bueno volver! Creo que haré principalmente preguntas en el futuro previsible
isaacg
¿Podría agregar también los 14 posibles ordenamientos para n = 4?
Peter Taylor

Respuestas:

11

Python 3 + SciPy, 396 390 385 351 336 355 bytes

from scipy.optimize import*
n=int(input())
r=range(n)
def f(u):
 s=linprog(r,u,[-n]*len(u),options={'tol':.1});c=s.success;y=sorted(range(c<<n),key=lambda a:s.x.round()@[a>>i&1for i in r])
 for a,b in zip(y,y[1:]):
  v=[(a>>i&1)-(b>>i&1)for i in r]
  if~-(v in u):c+=f(u+[[-z for z in v]]);u+=v,
 return+c
print(f([[(i==j-1)-(i==j)for i in r]for j in r]))

Pruébalo en línea!

Esto ahora funciona para n = 5 en aproximadamente 5 segundos. Se if~-(v in u):puede eliminar por −18 bytes pero una gran penalización de rendimiento.

Si desea imprimir todos los ordenamientos abstractos tal como se encuentran en lugar de contarlos, agregue if c:print(s.x.round(),y)antes del forciclo. (Los subconjuntos están representados por enteros binarios donde cada bit corresponde a la presencia o ausencia de un elemento: { a , c , d } ↔ 1101₂ = 13.)

Cómo funciona

frecursivamente cuenta los ordenamientos abstractos que satisfacen una lista dada de restricciones. Comenzamos con las restricciones na , a + nb , b + nc , c + nd . Mediante la programación lineal, encontramos una solución a las restricciones (o devolvemos 0 si no hay una); en este caso obtenemos a = 4, b = 8, c = 12, d = 16. Redondeamos la solución a enteros , luego calcule un orden de referencia ordenando todos sus subconjuntos por su suma:

{ a }, { b }, { c }, { a , b }, { d }, { a , c }, { a , d }, { b , c }, { b , d }, { a , b , c }, { c , d }, { a , b , d }, { a , c , d }, { b , c , d }, {a , b , c , d }

El redondeo no puede causar que ninguna restricción sea violada por más de n / 2, razón por la cual agregamos un margen de n .

Dado que Python sortedes estable, cualquier vínculo entre los subconjuntos se rompe en el mismo orden inverso-lexicográfico en el que los generamos. Entonces podríamos imaginar reemplazar { a , b , c , d } con { a · 2 ^ n + 2 ^ 0, b · 2 ^ n + 2 ^ 1, c · 2 ^ n + 2 ^ 2, d · 2 ^ n + 2 ^ 3} para obtener el mismo orden sin ningún vínculo.

El plan es clasificar todos los demás ordenamientos abstractos por análisis de casos basados en donde primero no están de acuerdo con el ordenamiento de referencia:

Ya sea { a }> { b },
o { a } <{ b }> { c },
o { a } <{ b } <{ c }> { a , b }
o { a } <{ b } < { c } <{ a , b }> { d },

Dentro de cada caso, agregamos estas nuevas restricciones con un margen de n , y recurrimos recursivamente fcon las nuevas restricciones agregadas.

Notas

Durante un tiempo supuse (pero no supuse) que las soluciones de programa lineal con margen 1 en las restricciones siempre serán enteros. Esto resulta ser falso: un contraejemplo con n = 7 es {2.5, 30, 62.5, 73.5, 82, 87.5, 99.5}.

Python, 606 bytes (más rápido, sin bibliotecas externas)

n=int(input())
r=range(n)
e=enumerate
def l(u,x):
 for i,v in e(u):
  for j,a in e(v):
   if a<0:break
  else:return[0]*len(x)
  if sum(b*x[k]for k,b in e(v))>0:
   x=l([[b*w[j]-a*w[k]for k,b in e(v)if k!=j]for w in u[:i]],x[:j]+x[j+1:]);x.insert(j,0)
   for k,b in e(v):
    if k!=j:x[j]+=b*x[k];x[k]*=-a
 return x
def f(u,x):
 x=l(u,x);c=any(x);y=sorted(range(c<<n),key=lambda a:sum(x[i]*(a>>i&1)for i in r))
 for a,b in zip(y,y[1:]):
  v=[(a>>i&1)-(b>>i&1)for i in r]+[1]
  if~-(v in u):c+=f(u+[[-z for z in v[:-1]]+[1]],x);u+=v,
 return+c
print(f([[(i==j-1)-(i==j)for i in r]+[1]for j in r],[1]*(n+1)))

Pruébalo en línea!

Esto funciona para n = 5 en un cuarto de segundo, yn = 6 en 230 segundos (75 segundos en PyPy).

Incluye un solucionador de programación lineal codificado a mano que usa matemática entera en coordenadas homogéneas para evitar problemas de redondeo de punto flotante.

Anders Kaseorg
fuente
390 bytes .
Sr. Xcoder
@ Mr.Xcoder Claro, gracias!
Anders Kaseorg
@ Lynn ¡Gracias! Me comprometí un poco porque no quiero ralentizarlo demasiado; ya lleva casi 3 minutos para n = 5.
Anders Kaseorg
1
@AlonAmit Parece que tomó alrededor de 55 minutos para n = 6. SciPy no es el mejor en LP; Tengo una versión que usa GLPK en lugar de SciPy que hace n = 6 en 70 segundos. Más preocupante aún, la versión de SciPy recibió la respuesta incorrecta (y GLPK la correcta) ... así que, eh, eso es ... interesante ... Me pregunto si esta es SciPy # 6690 .
Anders Kaseorg
1
@AlonAmit # 6690 no lo es. Pero agregué options={'tol':.1}, lo que parece solucionar el problema.
Anders Kaseorg
0

Ruby, 308 bytes, mucho más rápido.

Ejecuta el caso 4 en ~ 150 ms. No se utiliza una biblioteca especializada.

->n{t=2**(n-1)
n==0 ?[[0]]:P[n-1].map{|a|b=a.map{|i|i+t}
[*0..t].repeated_combination(t).select{|m|m[0]>=a.index(n-1)}.map{|m|c,d=a.dup,b.dup;m.reverse.map{|i|c.insert(i,d.pop)};c}}.flatten(1).select{|p|p.combination(2).all?{|(x,y)|x&~y==0||y&~x!=0&&n.times.all?{|i|x!=y<<i+1}&&p.index(x&~y)<p.index(y&~x)}}}

Recurre recíprocamente el resultado de un caso menor, por ejemplo

[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}]

con los subconjuntos correspondientes con un elemento adicional agregado: deben mantener el mismo orden relativo. También asegura que el nuevo singleton se agregue después de todos los singleton anteriores.

La parte que verifica el cumplimiento es la misma que antes, pero no las combinaciones para probar son mucho menos.

Versión ampliada y comentada:

->n{
    t=2**(n-1)
    if n==0
        [[0]]
    else
        # for each one of the previous nice orderings
        P[n-1].map { |a|
            # create the missing sets, keep order
            b = a.map{|i|i+t}
            # intersperse the two sets
            [*0..t].repeated_combination(t) # select t insertion points
                .select do |m|
                    # ensure the new singleton is after the old ones
                    m[0] >= a.index(n-1)
                end
                .map do |m|
                    # do the interspersion
                    c,d=a.dup,b.dup
                    m.reverse.map{|i|c.insert(i, d.pop)}
                    c
                end
        }.flatten(1).select{ |p|
            # check if the final ordering is still nice
            p.combination(2).all? { |(x,y)|
                (x&~y==0) || 
                (y&~x!=0) && 
                n.times.all?{|i|x!=y<<i+1} && 
                (p.index(x&~y)<p.index(y&~x))
            }
        }
    end
}

Ruby, 151 bytes, bastante lento

(el caso de tres elementos toma << 1s, el caso de cuatro todavía se está ejecutando)

->n{[*1...2**n-1].permutation.select{|p|p.combination(2).all?{|(x,y)|x&~y==0||y&~x!=0&&n.times.all?{|i|x!=y<<i+1}&&p.index(x&~y)<p.index(y&~x)}}.count}

Funciona en la representación de campo de bits de los subconjuntos, por lo que es posible que tenga que dar masajes a la salida si es necesario para mostrar los subconjuntos.

formateado:

-> n {
  [*1...2**n-1]. # prepare permutations of non-empty and non-full sets
    permutation.
    select { |p|
      p.combination(2). # check all ordered pairs
        all? { |(x, y)|
          # first is subset of second 
          x &~ y == 0 ||
          # second is not subset of first
          y &~ x != 0 &&
          # first is not a right shift of second
          # (this normalizes the ordering on atoms)
          n.times.all? { |i| x != y << i+1 } &&
          # after taking out common elements, ordering agrees 
          p.index(x &~ y) < p.index(y &~ x)
        }
    }.
    count
}
reescrito
fuente
No puedo probarlo por encima de 3 en mi máquina, pero esto (139 bytes) debería ser funcionalmente idéntico a su solución. Cambios: ...x-1=> ..x-2, .select{...}.count=> .count{...}, |(x,y)|=> |x,y|, x&~y==0||y&~x!=0=> x&~y<1||y&~x>0ya a&~bque no puede ser negativo si no me equivoco
Asone Tuhid
1
Mire el n=5contraejemplo que acabo de agregar. Si no me equivoco, su código lo aceptaría.
isaacg
2
El enlace TIO que lo muestra no funciona correctamente en el contraejemplo: ¡ Pruébelo en línea!
isaacg
1
Su nueva versión parece ser una función recursiva llamada P, por lo que no puede ser anónima. Además, creo que todavía falla debido al contraejemplo que publiqué.
isaacg
1
Para la solución más rápida: 280 bytes ¡ Pruébelo en línea! . Tenga en cuenta que debe incluir el nombre de una función recursiva ( P=). Además, creo que debe devolver un número, por lo que es posible que tenga que incorporarlo .sizeen algún lugar.
Asone Tuhid