Classificação da pilha de livros

21

Ao empilhar livros, você geralmente deseja colocar os maiores na parte inferior e os menores na parte superior. No entanto, meu TOC latente me deixa muito desconfortável se tiver dois livros em que um é mais baixo (em altura), mas mais largo que o outro. Independentemente da ordem em que os colocar, o livro superior se estenderá além do livro inferior de um lado.

Como exemplo, digamos que um livro tenha dimensões (10,15)e outro tenha dimensões (11,14). Não importa de que maneira eu os coloque, recebo uma saliência. Mas se eu tiver livros com dimensões (4,3)e (5,6), posso evitar um balanço, colocando o último abaixo do primeiro.

Para os propósitos deste desafio, consideraremos saliências apenas em relação ao livro imediatamente abaixo . Por exemplo, se eu tenho uma pilha (5,5), (3,3), (4,4)(não que qualquer pessoa em sã consciência faria isso), as contagens top livro como uma saliência, embora não se estende além do livro de fundo. Da mesma forma, a pilha (3,3), (3,3), (4,4)também tem apenas uma saliência, apesar do livro superior estendendo-se para além do inferior.

O desafio

Dada uma lista de pares inteiros para as dimensões do livro, classifique esses pares / livros de modo que o número de saliências seja mínimo. Você não deve girar os livros - eu quero todos os espinhos voltados para a mesma direção. Se houver várias soluções com o mesmo número de balanços, você poderá escolher qualquer ordem desse tipo. Seu algoritmo de classificação não precisa ser estável. Sua implementação pode assumir que as dimensões do livro são menores que 2 16 cada.

Complexidade de tempo: para tornar isso um pouco mais interessante, a pior complexidade assintótica do seu algoritmo deve ser polinomial no tamanho da pilha. Então você não pode simplesmente testar todas as permutações possíveis. Inclua uma prova curta da otimização e complexidade do seu algoritmo e, opcionalmente, um gráfico que mostre a escala para grandes entradas aleatórias. Obviamente, você não pode usar o tamanho máximo da entrada como argumento de que seu código é executado em O (1).

Você pode escrever um programa ou função, receber entradas via STDIN, ARGV ou argumento de função em qualquer formato de lista conveniente (não pré-processado) e imprimir ou retornar o resultado.

Isso é código de golfe, então a resposta mais curta (em bytes) vence.

Estou confiante de que existe uma solução polinomial, mas se você puder me provar que está errado, poderá enviar essa prova em vez de uma apresentação de golfe. Nesse caso, você pode assumir P ≠ NP . Vou aceitar a primeira prova correta e conceder uma recompensa a ela.

Exemplos

In:  [[1, 1], [10, 10], [4, 5], [7, 5], [7, 7], [10, 10], [9, 8], [7, 5], [7, 5], [3, 1]]
Out: [[10, 10], [10, 10], [9, 8], [7, 7], [7, 5], [7, 5], [7, 5], [4, 5], [3, 1], [1, 1]]

In:  [[4, 5], [5, 4], [5, 4], [5, 4], [5, 4], [4, 5], [4, 5], [4, 5], [5, 4], [4, 5]]
Out: [[4, 5], [4, 5], [4, 5], [4, 5], [4, 5], [5, 4], [5, 4], [5, 4], [5, 4], [5, 4]]
  or [[5, 4], [5, 4], [5, 4], [5, 4], [5, 4], [4, 5], [4, 5], [4, 5], [4, 5], [4, 5]]

In:  [[2, 3], [1, 1], [5, 5], [7, 1]]
Out: [[5, 5], [2, 3], [7, 1], [1, 1]]
 or  [[5, 5], [2, 3], [1, 1], [7, 1]]
 or  [[7, 1], [5, 5], [2, 3], [1, 1]]
 or  [[7, 1], [1, 1], [5, 5], [2, 3]]

Eu os criei à mão, então, deixe-me saber se você encontrar algum erro.

Martin Ender
fonte
3
Você tem certeza de que encontrar uma solução com um número mínimo de saliências pode ser resolvido em tempo polinomial?
COTO 24/10
@COTO Estou bastante confiante, sim.
Martin Ender
Hmm. Normalmente, eu lidava com isso com um algoritmo ganancioso, mas posso facilmente obter entradas que levam a resultados abaixo do ideal para qualquer critério de "ganância" que eu possa apresentar (por exemplo, área, maximizar uma dimensão, maximizar a menor dimensão etc.). As únicas outras abordagens em que posso pensar envolvem a divisão dos livros em panelinhas, e todas elas têm uma complexidade exponencial do pior caso. Eu estarei interessado em ver quais respostas surgem. Você também pode solicitar uma breve prova da otimizar a classificação como parte da especificação.
COTO 24/10
@ COTO Adicionei um parágrafo sobre isso, caso eu esteja realmente errado, mas não conte com isso. ;)
Martin Ender
Apenas no caso, provas potenciais de que não existe um algoritmo de tempo polinomial devem ser assumidas que P não seja igual a NP.
Xnor 24/10

Respostas:

2

Pyth , 30

FN_SQFbYIgeeYeb~b]NB)E~Y]]N;sY

Este é um golfe direto do incrível algoritmo do grc. Aqui está o equivalente preciso do programa pyth acima, em seu código python compilado.

Q = eval(input())
Y = []
for N in sorted(Q)[::-1]:
     for b in Y:
         if Y[-1][-1] >= b[-1]:
             b += [N]
             break
     else:
         Y += [[N]]
print(Psum(Y))

Nesse contexto, a Psum(Y)função é equivalente ao python sum(Y,[]).

Código compilado e de execução real (de pyth -d):

Y=[]
Q=copy(eval(input()))
for N in neg(Psorted(Q)):
 for b in Y:
  if gte(end(end(Y)),end(b)):
   b+=[N]
   break
 else:
  Y+=[[N]]
Pprint("\n",Psum(Y))
isaacg
fonte
11
A tradução do Python precisa de "Y = []", remova a avaliação se você estiver no Python 2 e a soma precisará de um segundo argumento sum(Y,[]). Tudo isso deve funcionar em Pyth, apenas a tradução não a inclui automaticamente.
Xnor
@xnor A última linha realmente lê: Pprint("\n",Psum(Y)). Eu acho que ele pode ter simplificado por conveniência, junto com todos os -1s etc., Psumna verdade, seria mais parecido reduce(lambda x,y:x+y, Y[1:], Y[0]).
FryAmTheEggman
20

Python, 113

P=[]
for n in sorted(input())[::-1]:
 for p in P:
  if p[-1][1]>=n[1]:p+=[n];break
 else:P+=[[n]]
print sum(P,[])

Depois de classificar a lista de livros em ordem decrescente (primeiro pela largura e depois pela altura), isso divide os livros em pilhas sem sobreposições. Para determinar onde colocar cada livro, sua altura é comparada com a altura do livro superior em cada pilha. É colocado na primeira pilha possível, ou então uma nova pilha é criada.

Eu não sou muito bom com complexidade de tempo, mas eu acredito que teria um pior caso de O ( N 2 ). Existem dois loops, cada um com no máximo N iterações. Eu também uso a classificação incorporada do Python, que é O ( n log n ).


Minha primeira prova de que esse algoritmo produz soluções ideais acabou incorreta. Agradecemos imensamente a @xnor e @ Sp3000 por uma ótima discussão no bate-papo sobre provar isso (que você pode ler a partir daqui ). Depois de elaborar uma prova correta, o @xnor descobriu que parte dela já havia sido realizada ( teorema de Dilworth ).

De qualquer maneira, aqui está uma visão geral da prova (crédito para @xnor e @ Sp3000).

Primeiro, definimos a noção de um antipile, ou antichain, ( citado em @xnor ):

Um antipile é uma sequência de livros com altura decrescente, mas com largura crescente.
Portanto, cada livro sucessivo é estritamente mais alto, mas estritamente menos largo.
Observe que qualquer livro em um antipile se sobressai sobre qualquer outro livro em um antipile.
Portanto, não há dois livros em um antipile. estar na mesma pilha
Como conseqüência, se você puder encontrar um antipile de x livros, esses livros deverão estar em pilhas diferentes.
Portanto, o tamanho do antipile maior é um limite inferior ao número de pilhas

Em seguida, classificamos os livros em ordem decrescente pela largura (primeiro) e altura (segundo) *.

Para cada livro B , fazemos o seguinte:

  1. Se B pode caber na primeira pilha, nós a colocamos lá e seguimos em frente.
  2. Caso contrário, encontramos a pilha * mais antiga x, na qual B pode ser colocado em cima. Esta pode ser uma nova pilha, se necessário.
  3. A seguir, vinculamos B a P , onde P é o livro principal da pilha anterior x - 1 .
  4. Agora sabemos que:
    • B é estritamente * menor em largura que P , pois os livros são classificados em ordem decrescente por largura
    • B é estritamente maior em altura que P , ou teríamos colocado B em cima de P

Agora, construímos um link de todos os livros (exceto os da primeira pilha), para um livro da pilha anterior que tenha maior largura e menor altura.

O excelente diagrama do @ Sp3000 ilustra bem isso:

Ao seguir qualquer caminho da última pilha (à direita) até a primeira pilha (à esquerda), obtemos um antipile. É importante ressaltar que o comprimento deste antipilha é igual ao número de pilhas. Portanto, o número de pilhas utilizadas é mínimo.

Por fim, como organizamos os livros no número mínimo de pilhas sem sobreposições, podemos empilhá-las umas sobre as outras para obter uma pilha com o número mínimo de sobreposições.

* este comentário útil explica algumas coisas

grc
fonte
3
+1 para a prova expositiva e link para a discussão. Adereços para xnor et al.
COTO 24/10
Devo esclarecer que o Teorema de Dilworth não cobre toda a prova, apenas o fato de que o menor número de pilhas é igual ao antipile de maior tamanho.
xnor 24/10