Ordens de soma de subconjuntos

22

Um conjunto de nnúmeros positivos possui 2^nsubconjuntos. Nós chamaremos um conjunto de "bom" se nenhum desses subconjuntos tiver a mesma soma. {2, 4, 5, 8}é um conjunto tão bom. Como nenhum dos subconjuntos tem a mesma soma, podemos classificá-los por soma:

[{}, {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}]

Se rotularmos os números [2, 4, 5, 8]com os símbolos [a, b, c, d]em ordem crescente, obteremos a seguinte ordem abstrata:

[{}, {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}]

Outro bom conjunto de números positivos pode ter a mesma ordem abstrata ou uma ordem diferente. Por exemplo, [3, 4, 8, 10]é um bom conjunto com uma ordem abstrata 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}]

Neste desafio, você deve contar o número de ordenações abstratas distintas de bons conjuntos de nnúmeros positivos. Essa sequência é OEIS A009997 e os valores conhecidos, começando em n=1, são:

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

Por exemplo, para n=3, a seguir estão as duas ordens abstratas possíveis:

[{}, {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, a seguir estão as 14 ordens abstratas possíveis, além de um bom exemplo de conjunto com essa ordem:

[{}, {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]

O seguinte não é uma ordem abstrata válida:

{}, {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}

Essa ordem implica que:

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

A soma dessas desigualdades fornece:

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

o que é uma contradição. Seu código não deve contar com esse pedido. Tais contra-exemplos aparecem pela primeira vez em n=5. Exemplo deste artigo , exemplo 2.5 na página 3.

Essa ordem é inválida, apesar do fato A < Bimplicar que A U C < B U C, para qualquer Cdesunião de Ae B.


Seu código ou programa deve ser rápido o suficiente para que você possa executá-lo n=4antes de enviá-lo.

As submissões podem ser programas, funções etc., como de costume.

As brechas padrão são proibidas, como sempre. Isso é código de golfe, então a resposta mais curta em bytes vence. Sinta-se livre para fazer perguntas esclarecedoras nos comentários.

isaacg
fonte
Muito tempo sem ver Isaac!
orlp
Quando são dois subconjuntos, existe algum cenário em que pode ser deduzido de qualquer informação que não seja ou , sem contar o inicial ? P Q P Q P P , q Q ( p q ) a b c P,QPQPQpP,qQ(pq)abc
orlp 11/07/2018
Resposta: sim. não é suficientemente rígido, por exemplo: . { a , c } , { b , c }pP,qQ(pq){a,c},{b,c}
orlp
@orlp É bom estar de volta! Acho que vou estar fazendo principalmente questões para o futuro previsível
isaacg
Você também pode adicionar as 14 ordens possíveis para n = 4?
22618 Peter Peter

Respostas:

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]))

Experimente online!

Isso agora é executado por n = 5 em cerca de 5 segundos. O if~-(v in u):pode ser removido para -18 bytes, mas uma penalidade de desempenho enorme.

Se você quiser imprimir todas as ordens abstratas como elas são encontradas, em vez de apenas contá-las, adicione if c:print(s.x.round(),y)antes do forloop. (Os subconjuntos são representados por números inteiros binários em que cada bit corresponde à presença ou ausência de um elemento: { a , c , d } ↔ 1101₂ = 13.)

Como funciona

fconta recursivamente as ordens abstratas que satisfazem uma determinada lista de restrições. Começamos com as restrições na , a + nb , b + nc , c + nd . Usando programação linear, encontramos uma solução para as restrições (ou retornamos 0 se não houver uma) - nesse caso, obtemos a = 4, b = 8, c = 12, d = 16. Arredondamos a solução para números inteiros , calcule uma ordem de referência classificando todos os seus subconjuntos por sua soma:

{ 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 }

O arredondamento não pode violar nenhuma restrição por mais de n / 2, motivo pelo qual adicionamos uma margem de n .

Como o Python sortedé estável, quaisquer vínculos entre os subconjuntos são quebrados na mesma ordem lexicográfica reversa na qual os geramos. Então, podemos imaginar substituir { a , b , c , d } por { a · 2 ^ n + 2 ^ 0, b · 2 ^ n + 2 ^ 1, c · 2 ^ n + 2 ^ 2, d · 2 ^ n + 2 ^ 3} para obter a mesma ordem sem vínculos.

O plano é categorizar todas as outras ordens abstratas por análise de caso, com base em onde elas discordam primeiro da ordem de referência:

Ou { um }> { b },
ou { um } <{ b }> { c },
ou { um } <{ b } <{ c }> { a , b },
ou { um } <{ b } < { c } <{ a , b }> { d },

Em cada caso, adicionamos essas novas restrições com uma margem de n e chamamos recursivamente fcom as novas restrições adicionadas.

Notas

Por um tempo, conjeturei (mas não presumi) que as soluções lineares do programa com margem 1 nas restrições sempre serão inteiras. Isso acaba sendo falso: um contra-exemplo com n = 7 é {2,5, 30, 62,5, 73,5, 82, 87,5, 99,5}.

Python, 606 bytes (mais rápido, sem 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)))

Experimente online!

Isto funciona para n = 5 em um quarto de segundo, e n = 6 em 230 segundos (75 segundos em PyPy).

Ele inclui um solucionador de programação linear codificado manualmente, usando matemática inteira em coordenadas homogêneas para evitar problemas de arredondamento de ponto flutuante.

Anders Kaseorg
fonte
390 bytes .
Mr. Xcoder
@ Mr.Xcoder Claro, obrigado!
Anders Kaseorg
@Lynn Thanks! I comprometido um pouco porque eu não quero para retardá-lo muito, ele já leva quase três minutos para n = 5.
Anders Kaseorg
1
@AlonAmit Parece que demorou cerca de 55 minutos para n = 6. SciPy não é o melhor no LP; Eu tenho uma versão usando GLPK em vez de SciPy que faz n = 6 em 70 segundos. Mais preocupante, a versão SciPy obteve a resposta errada (e GLPK a correta) ... então, isso é ... interessante ... eu me pergunto se esse é o SciPy # 6690 ?
Anders Kaseorg
1
@AlonAmit # 6690 não é? Mas eu adicionei options={'tol':.1}, o que parece cuidar do problema.
Anders Kaseorg
0

Ruby, 308 bytes, muito mais rápido

Executa o caso 4 em ~ 150ms. Nenhuma biblioteca especializada é usada.

->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)}}}

É resultado recursivamente intercalado de um caso menor, por exemplo

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

com os subconjuntos correspondentes com um elemento adicional adicionado - eles precisam manter a mesma ordem relativa. Também garante que o novo singleton seja adicionado após todos os singletons anteriores.

A parte que verifica a conformidade é a mesma de antes, mas as combinações a serem testadas são muito menos.

Versão expandida e 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

(o caso de três elementos leva << 1s, o caso de quatro ainda está em execução)

->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}

Ele funciona na representação dos subconjuntos de campo de bits, portanto, pode ser necessário massagear a saída, se necessário, para exibir os próprios subconjuntos.

formatado:

-> 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
fonte
Não posso testá-lo acima de 3 na minha máquina, mas isso (139 bytes) deve ser funcionalmente idêntico à sua solução. Alterações: ...x-1=> ..x-2, .select{...}.count=> .count{...}, |(x,y)|=> |x,y|, x&~y==0||y&~x!=0=> x&~y<1||y&~x>0desde a&~bque não possa ser negativo se não me engano
Asone Tuhid
1
Veja o n=5contra - exemplo que acabei de adicionar. Se não me engano, seu código o aceitaria.
Isaacg
2
Link TIO mostrando que não funciona corretamente no contraexemplo: Experimente online!
Isaacg
1
Sua versão mais recente parece ser uma função recursiva chamada P, portanto, não pode ser anônima. Além disso, acho que ainda falha devido ao contra-exemplo que publiquei.
Isaacg
1
Para uma solução mais rápida: 280 bytes Experimente online! . Observe que você deve incluir o nome de uma função recursiva ( P=). Além disso, acho que você deve retornar um número para incorporá-lo .sizeem algum lugar.
Asone Tuhid