reduzir Permutation

Question

Eu preciso de um algoritmo que pode mapear as corridas em uma permutação a um único número, mas também reduzir os números subseqüentes.

Assim, uma corrida é um conjunto sequencial de números em uma permutação que é ordenada e em ordem. Na lista, 1; 2; 3; 5; 6; 4 existem duas pistas, 1; 2; 3 e 5; 6. Quero substituir estes com um único número, no mínimo, por isso, se, após a remoção de corridas, temos uma permutação de 4 elementos, a permutação usa os números 1 ... 4. No exemplo acima, temos de reduzir as duas corridas . a primeira execução seria uma, 4 transforma a 2, e [5; 6] transforma a 3, para segurar o segundo critério. Se eu meio a permutação reduzida em seguida, expanda os elementos dentro do mapeamento e classificar a permutação original eu obterá o mesmo resultado. A permutação resultante não deve ter nenhum corre na mesma.

Por exemplo, (i você destacou as corridas):

(1;2;3;4;5;6) => 1 //Mappings: 1->1;2;3;4;5;6
(2;3;4);1;(5;6) => 2 1 3 // Mappings: 2->2;3;4, and 3->5;6
(3;4);(1;2);(5;6) => 2 1 3 // Mappings: 2->3;4, and 1->1;2 and 3->5;6

Por enquanto, eu estou passando sobre a lista e fazer uma lista de listas, agrupando as pistas. Realmente a segunda parte é a parte mais difícil de fazer uma solução limpa. Tenho pensado da abordagem ingênua, curioso, se alguém tem algum truque inteligente que pode fazê-lo melhor, então a minha, eu estou em como O (2n + n log n),

• substituindo as corridas com o elemento de cabeça da corrida e inserir esses dados em uma tabela hash (para recuperação)
• triagem para criar um mapa para os dígitos que faltam com ele do índice ordenado. [1; 6; 5; 4] saída seria [(1,1); (4,2); (5,3); (6,4)]
• substituindo a lista no passo 1 com o mapa criado no passo 2 e atualizar o hashtable para a tradução.

correndo através de um novo exemplo:

step 1: replace runs with the head element of the run and inserting data into a hash table  
    [1;3;4;2;5;6;] -> [1;3;2;5]  
step 2: sort array to create map  
    [1235], so we know that, in the previous array, 1 maps to 1, 2 to 2, 3 to 3, 4 to 5.  
step 3: do above translation on array from step one. 
    [1;3;2;4]

Se este tipo de permutação e reconstruir: [1; 2; 3; 4], 3-> 3; 4 e 4-> 5; 6 fico, 1; 2; 3; 4; 5; 6. Também classificada.

Eu estou usando listas, então uma abordagem funcional seria preferível. Nenhum código necessário. Todas as ideias, naturalmente, bem-vindos.

EDIT:

mweerden:

Não está claro para mim o que as condições precisas sobre o mapeamento é. Por que exatamente não é permitido apenas para produzir a permutação [1,2, ..., N] para uma permutação com corridas N? Você parecem preferir para mapear uma corrida para um número a partir desse prazo, mas (como isso nem sempre é possível) você parecem permitir alguma liberdade. -

Eu não preferem para mapear uma corrida para um número dentro desse prazo (olhar acima!), Mas eu preciso para preservar um ordenação . A permutação [1; 2; 3 ... N] é um prazo, e, assim, pode ser mais reduzido. É por isso que é inválido. A ordem importa em outras operações em outro algoritmo, mas os elementos individuais podem ser expandidas no fim de resgatar a permutação originais.

Answer 1

Notação:

• A contagem começa em 1
• l.i é elemento i da lista l
• l+m é a concatenação de listas l e m
• uma corrida é uma sublista máxima que é uma [n,n+1,n+2,...,m] lista por algum n e m com n <= m

Por isso, estamos dado um p permutação da lista [1,2,...,N]. Dividimos p-se em corridas r_1,r_2,...,r_M tal que p = r_1+r_2+...+r_M. Estamos, então, à procura de um q permutação de [1,2,...,M] tal que r_(q.1)+r_(q.2)+...+r_(q.M) = [1,2,...,N].

Por exemplo, se p = [1,3,4,2,5,6], temos N=6, M=4, r_1 = [1], r_2 = [3,4], r_3 = [2] e r_4 = [5,6]. Neste caso, precisamos q ser [1,3,2,4] como r_1+r_3+r_2+r_4 = [1]+[2]+[3,4]+[5,6] = [1,2,3,4,5,6].

Note que q não pode conter corridas de maior comprimento de um por definição; Se fosse, então não é um i < M com q.i + 1 = q.(i+1) e, portanto, uma r_(q.i)+r_(q.(i+1)) = r_(q.i)+r_(q.i + 1) sublista de [1,2,...,N], mas r_(q.i)+r_(q.i + 1) também é uma sublista de p que contradiz que r_(q.i) e r_(q.i + 1) são corridas.

Agora, para encontrar um q dado um p, assumimos a disponibilidade de uma estrutura de dados de mapeamento com inserções O(1) e pesquisas de números e listas com Anexa O(1) e travessia para a frente. Em seguida, faça o seguinte.

• Em primeiro lugar, construir a lista runheads = [r_1.1,r_2.1,...,r_M.1]. Isso pode ser feito trivialmente por p travessia, mantendo a execução atual. Durante esta etapa, nós também lembrar o número máximo encontrado para obter N no final e construir um heads mapeamento com os elementos da runheads como chaves. Esta etapa é claramente O(n). Note que não é relevante que os valores de heads são, para que possamos usar apenas r_i executado como valor para r_i.1 chave.

• Em seguida, iterate de 1 até (e incluindo) N manter um k valor com 1 valor inicial. Para cada i valor que verificar para ver se i está em heads. Se este for o caso, adicionar i -> k a um f mapeamento e aumento k. Esta etapa também é claramente O(n). Para ser capaz de voltar de q para p também pode armazenar um rev mapeamento adicional com k -> i ou mesmo k -> runheads(i), sem nenhum custo big-O extra.

• Finalmente, aplicar o mapeamento f aos elementos da runheads para obter q. Novamente O(n).

Para ilustrar com um exemplo olharmos para o caso que p = [1,3,4,2,5,6].

• Na primeira etapa temos runheads = [1,3,2,5], N=6 e heads = { 1 -> [1], 3 -> [3,4], 2 -> [2], 5 -> [5,6] }.

• Para o segundo passos que quatro casos para os quais temos de fazer alguma coisa: 1, 2, 3 e 5. Para esses casos, temos valores para k que são 1, 2, 3 e 4, respectivamente. Isto significa que f será { 1 -> 1, 2 -> 2, 3 -> 3, 5 -> 4 }. (E rev seria { 1 -> 1, 2 -> 2, 3 -> 3, 4 -> 5 } ou { 1 -> [1], 2 -> [2], 3 -> [3,4], 4 -> [5,6] }, dependendo do que você escolheu a loja.)

• Para obter q calculamos map(f,runheads) que é [f(1),f(3),f(2),f(5)] ou, equivalente, [1,3,2,4].

Então, se eu não cometer um erroe se as estruturas de dados satisfazem os requisitos acima, esta solução deve ser O(n). Note-se que, na prática, pode realmente ser mais útil para usar sua própria solução (O(n*log(n))). Se você tem um grande p mas com apenas um par de corridas, classificação runheads e usar isso para construir os mapeamentos pode ser mais eficiente. Eu acho que p teria que ser muito grande para que este seja o caso.

Answer 2

editado para clarificaton

passo 1: Executar o algoritmo, mas em vez de produzir apenas uma tabela hash produzir uma tabela de Hash (D1) indexados pela cabeça do conjunto é o mapeamento a (por exemplo, para [3,4] que irá ser 3) e uma lista (L1) com o próprio

set

[3; 4; 6; 8; 1; 2]:

   D1              L1

3 -> [3,4]     1 -> [3,4]

6 -> [6]       2 -> [6]

8 -> [8]       3 -> [8]

1 -> [1,2]     4 -> [1,2]

Passo 2: I você olhar para as coleções que temos agora, você verá que, para um dado conjunto temos o índice em que descobrimos que (em L1) eo valor Head. O valor mapa correto será o inteiro mínima entre eles que não é já tomadas. Por exemplo, para o [3,4] teremos que o valor deve ser entre 1 e 3, e, desde 1 já está tomada, o valor correspondente é 2. Leve em conta que, como D1 é indexado pelo Chefe valor, valores inferiores será sempre tomar se o conjunto correspondente existe. No exemplo, [1,2] é mapeado para 1, de modo que esta chave já está "tomadas". Assim, em pseudo-código:

for (int Current = 1; Current  < L1.Length; Current++)
{
  GetHead(L1[Current]);
  Index = Current;
  While Head > Index
  {
    if D1.Empty(Index)
    {
      D1.Add(Index,D2[Current])
      D1.DeleteIfNotEmpty(Head);
    }
    else
      Index++;
  }
}

Por exemplo

• tomamos o primeiro valor em L1 -> [3,4] ...
• obter a cabeça = 3
• A partir do dia 1 nós lookup D1 [1], que já está tomada, de modo que incrementar a 2.
• Procuramos D1 [2] que é vazio, então vamos atribuir D1 [2] = [3,4] e D de exclusão [3]

Isso não fornece O (n), mas algo como O (n + log (n)) (n para a primeira etapa, log (n) para o segundo)

Para o exemplo acima que você fica:

1 -> [1,2]
2 -> [3,4]
3 -> [6]
4 -> [8]

Agora, se você tem [3; 4; 8; 6; 1; 2], que irá resultar em

1 -> [1,2]
2 -> [3,4]
3 -> [8]
4 -> [6]

porque é usando ordenação absoluta na matriz original, eu não sei se isso é certo ou você vai querer 6 para ser no índice 3 e 8 para ser no índice 4, nesse caso, você provavelmente teve para pré-venda L1 com base na cabeça que irá incrementar a sua complexidade, Log (n)

Se você tem que pré-encomenda você terá 0 (n + log ^ 2 (n)), que não é tão ruim (talvez menos assumindo uma QuickSort tem O (log n) encomendar L1 será O (log (log n))