Problema interessante na classificação

14

Dado um tubo com bolas numeradas (aleatório). O tubo tem orifícios para remover uma bola. Considere as seguintes etapas para uma operação:

  1. Você pode pegar uma ou mais bolas dos buracos e lembrar a ordem em que as escolheu.
  2. Você precisa inclinar o tubo para o lado esquerdo, para que as bolas restantes no tubo se desloquem para a esquerda e ocupem o espaço vazio criado pela remoção das bolas.
  3. Você não deve alterar a ordem em que você selecionou as bolas numeradas do tubo. Agora você as coloca de volta no cano usando o espaço vazio criado pelo movimento das bolas.

As etapas 1 a 3 são consideradas como uma operação.

Descubra as operações mínimas necessárias para classificar as bolas numeradas em ordem crescente.

Por exemplo: Se o tubo contiver: [1 4 2 3 5 6]

Em seguida, pode tirar e e , e se a inclinação tubo para a esquerda, obtemos , e inserimos , em que para a extremidade de tubo para chegar .456[1 2 3](4 5 6)[1 2 3 4 5 6]

Portanto, o número mínimo de etapas necessárias é 1. Preciso encontrar operações mínimas para classificar o tubo.

Alguma idéia ou dicas sobre como resolver esse problema?

rakesh
fonte
Se eles vierem na ordem inversa, é necessário retirar 2, 3, ... em ordem e adicionar no final, para n operações no total. Este é claramente o pior caso.
vonbrand
2
8,7,6,5,4,3,2,1 -> 75318642 -> 51627384 -> 12345678, sempre tirando posições ímpares.
precisa saber é o seguinte
Resumindo minha resposta: o número mínimo de operações necessárias para classificar uma permutação é log 2 ( d ( π - 1 ) + 1 ) , onde d ( ) é o número de descidas. πlog2(d(π1)+1)d()
Yuval Filmus
Eu gosto de pensar nisso em termos de remoção de inversões. Com cada operação, você pode remover inversões entre qualquer conjunto e S - X (onde S é o conjunto inteiro de bolas). Então, você só precisa escolher seus conjuntos X com cuidado. XSXSX
6133 Joe

Respostas:

10

Defina o número da partição de execução de uma permutação , denotada r ( π ) , usando o seguinte processo. Seja k o número inteiro máximo, de modo que os números min ( π ) , , k apareçam em ordem crescente em π . Remova-os de π e repita o processo. O número de rodadas necessárias para consumir toda a permutação é r ( π ) .πr(π)kmin(π),,kππr(π)

Por exemplo, vamos calcular . Primeiro , para obter . Então separamos , para obter . Em seguida, separamos , para obter . Finalmente, separamos para obter a permutação vazia. Isso leva quatro rodadas, então r ( 62735814 ) = 4 .r(62735814)6273584 234 6758 51627358423467585 678678678r(62735814)=4

Como essa representação é útil para classificar ? Faça cada segunda execução, ou seja, 234 , 678 , e mova esses números para a direita para obter 51627384 (editar: na ordem em que aparecem na permutação, ou seja, 627384 ). Agora, existem apenas duas execuções, 1234 , 5678 , e podemos classificar a lista movendo 5678 para a direita.62735814234,678516273846273841234,56785678

Agora deixe-me fazer a seguinte conjectura: Para uma permutação , vamos Π ser o conjunto de todas as permutações que são acessíveis a partir de π dentro de um movimento. Então min α ¸ r ( α ) = r ( ππΠπ .minαΠr(α)=r(π)/2

Dada essa conjectura, é fácil mostrar que o número mínimo de movimentos necessários para classificar uma permutação é log 2 r ( π ) , e eu verifiquei essa fórmula para todas as permutações em S n paraπlog2r(π)Sn .n8

Edit: Aqui está uma interpretação diferente do número da partição de execução que fornece um algoritmo de tempo linear para computá-lo e permite que eu faça um esboço de uma prova de minha conjectura, verificando assim a fórmula .log2r(π)

Considere a permutação novamente. A razão pela qual a primeira execução termina em 1 é que 2 aparece antes de 1 . Da mesma forma, a segunda execução termina em 4, pois 5 aparece antes de 4 e assim por diante. Portanto, o número da partição de execução de uma permutação é o número de i s, tal que i +62735814121454i aparece antes de i .i+1i

Podemos afirmar isso de forma mais sucinta se olharmos para o inverso da permutação. Considere novamente . Tome π - 1 = 72485136 . Essa permutação possui três descidas: 7 2 48 5 1 36 (uma descida é uma posição menor que a anterior). Cada uma das descidas corresponde ao início de uma nova corrida. Então r ( π ) é igual a um mais o número de descidas em π - 1 .π=62735814π1=7248513672485136r(π)π1

Como é a operação em termos de ? seja B o conjunto de números que movemos para a direita e A seja o conjunto de números que ficam à esquerda. Substituímos os números em A por uma permutação em { 1 , , | Um | } representando sua ordem relativa e substitua os números em B por uma permutação em { | Um | + 1 , , | Um | + | B | }π1BAA{1,,|A|}B{|A|+1,,|A|+|B|}. Por exemplo, considere a movimentação 248136 foi mapeado para 468357 . . Em termos de permutações inversas, são 7 248 5 1362 468 1 357 . Então 75 foi mapeado para 21 e627358145162738472485136246813577521248136468357

Uma descida em π - 1 é perdido após a operação somente se x A e y B . Por outro lado, em termos de π - 1 , a partição em A e B corresponde a A -runs e B -runs; toda vez que um B- run termina e um A- run. Se matarmos duas descidas, teremos mudado no meio de um Bxyπ1xAyBπ1ABABBA corrida começa, há uma descida. Para "matar" uma descida, temos que mudar de um run para um BABB corrida para uma corrida , causando uma descida.A

Este argumento pode ser formalizadas para mostrar que se surge a partir π através de uma operação, em seguida, d ( α - 1 ) d ( π - 1 ) / 2 , onde d ( ) é o número de descidas. Isso é equivalente a r ( α ) r ( π ) / 2 απd(α1)d(π1)/2d()r(α)r(π)/2, provando assim uma direção da minha conjectura. A outra direção é mais fácil, e já foi descrita acima: simplesmente fazemos cada segundo ciclo e empurramos esses movimentos para a direita para obter uma permutação satisfazendo r ( α ) = r ( π / 2 ) .αr(α)=r(π/2)

Yuval Filmus
fonte
Você está tirando várias bolas de uma só vez, eu entendo que não é permitido.
precisa saber é o seguinte
1
Estou levando-os na ordem em que aparecem na permutação . Isso é legal.
Yuval Filmus
estou um pouco confuso. você pode explicar o número mínimo de operações necessárias para classificar [6 5 4 3 2 1] e também mencionou como "Faça cada segunda execução, ou seja, 234.678, e mova esses números para a direita para obter 51627384", você pode explicar isso com detalhes e também como calcular r (π) de forma eficaz?
User6709
1) , portanto, você precisaria de 3 operações. Por exemplo, 654321 531 | 642 51 | 6234 1234 | 56 . r(654321)=6654321531|64251|62341234|56
Yuval Filmus
2) Você pega todos os números pertencentes a essas execuções (na ordem em que aparecem na permutação) e os move para a direita. Nesse caso, você pega o e os move para a direita, deixando 51 para a esquerda. 62738451
Yuval Filmus