Eu tenho uma pilha de meias limpas que quero separar em pares. Infelizmente, só posso tirar meias de cada extremidade da pilha, não do meio. Além disso, só posso remover da pilha um par correspondente de cada vez. Minha estratégia é primeiro dividir a pilha em uma ou mais pilhas menores. Eu acho que alguns exemplos deixarão isso claro. Vou representar cada meia como um número inteiro positivo (números inteiros correspondentes indicam meias iguais).

Se a pilha inicial de meias for

1 2 3 3 2 1

então não preciso fazer nenhuma divisão. Posso remover as duas 1meias, depois as duas 2meias e as duas 3meias.

Se, em vez disso, a pilha inicial for

1 2 3 2 3 1

então eu tenho que dividi-lo primeiro porque não poderei emparelhar todas as meias apenas removendo-as do final. Uma possibilidade é dividi-lo em duas pilhas

1 2 3 and 2 3 1

Agora posso remover as 1meias, saindo 2 3 and 2 3, seguidas pelas 3meias, saindo 2 and 2e, finalmente, as 2meias.

Seu emprego

Dada a pilha inicial de meias, escreva um programa que o divida em pilhas menores que me permitam classificar as meias. Seu programa deve dividir a pilha no menor número possível de pilhas (se houver várias melhores soluções, você precisará encontrar apenas uma).

A entrada será fornecida como uma lista, sequência delimitada ou outra forma conveniente. Ele conterá apenas números inteiros entre 1e algum valor máximo n, com cada número inteiro ocorrendo exatamente duas vezes.

A saída deve consistir na lista de entrada dividida em listas menores, fornecidas de qualquer forma conveniente.

Exemplos

Input             Sample Output
1 1               1 1
1 2 1 2           1; 2 1 2
1 3 2 4 3 2 1 4   1 3 2; 4 3 2 1 4
1 2 3 4 3 4 1 2   1; 2 3; 4 3 4 1 2
1 1 2 2 3 3       1 1 2; 2 3 3
4 3 4 2 2 1 1 3   4 3 4 2; 2 1 1 3

Observe que essa não é a única saída permitida para a maioria dessas entradas. Para o segundo caso, por exemplo, as saídas 1 2; 1 2ou 1 2 1; 2também seriam aceitas.

Obrigado ao Sp3000 por algumas sugestões de teste!

Eu odeio gastar muito tempo escolhendo minhas roupas, então faça seu código o mais curto possível. Menor resposta em bytes ganha!

Notas

• Não quero ter que olhar atrás de uma meia para ver se o par correspondente está lá; portanto, não é permitido usar as duas meias do mesmo lado. Por exemplo, se a pilha estiver 1 1 2 2, você não poderá deixá-la como uma pilha e tirar as duas 1meias da extremidade esquerda.

Pitão, 25 bytes

hf!u #-R.-F{BhMs_BMGGT)./

Suíte de teste

Explicação:

hf!u #-R.-F{BhMs_BMGGT)./
                       ./    Form all partitions (implicitly) of the input.
 f                           Filter the permutations on
   u                 T)      Run the following function on the partition
                             until it reaches a fixed point:
                _BMG         Bifurcate the lists on reversal
               s             Concatenate
             hM              Take the first element of each list. 
                             These elements are all the ones on the ends of lists.
           {B                Bifurcate on deduplication
        .-F                  Bagwise subtraction.
                             Only elements repeated in ends of lists remain.
      -R            G        Remove these elements from each list.
   ' #'                      Filter out empty lists.
  !                          Negate. Only an empty list as fixed point succeeds.
h                            Output the first successful partition.

JavaScript (ES6), 329

Não é uma tarefa fácil para um idioma que não possui componentes combinatórios.

Provavelmente um pouco mais jogável.

Nota: todas as partições têm pelo menos o tamanho 2, pois uma partição com um único elemento é sempre menos útil.

Example: [1] [2 3 4] // can take 1 or 2 or 4  
Better: [1 2] [3 4] // can take 3 too  

a=>{G=(v,i,u=v)=>{if(i--){for(;r[i]=--u;)if(G(u,i))return 1;}else for(w=[...r,n=l].map((x,i)=>a.slice(z,z=x-~i),z=0),y=w.join`;`;w.map(b=>[0,1].map(q=>(x=b[q*=~-b.length])&&(t[x]?([c,p]=t[x],n-=2,p?c.pop():c.shift(),q?b.pop():b.shift()):t[x]=[b,q])),c=0,t=[]),c;)if(!n)return 1};for(l=a.length,r=[],k=0;!G(l-k-1,k);k++);return y}

Explicação em partes

(é excessivamente detalhado, mas achei difícil de explicar - pule para "juntar tudo")

Uma função recursiva para enumerar todas as divisões possíveis de uma matriz

// v: array length
// i number of splits
// fill the global array r that must exists
G=(v,i,u=v)=>
{
  if(i--)
  {
    for(;r[i]=--u;)
      G(u,i)
  }
  else
  {
    // the current split position are in r, ready to use
    // for instance...
    parts = [...r,a.length].map(x=>a.slice(z,z=x),z=0)
    console.log(r, parts)
  }
};

r=[]
a=['A','B','C','D']
G(4, 2)

// output in console (firebug)
[2, 3] [["A", "B"], ["C"], ["D"]]
[1, 3] [["A"], ["B", "C"], ["D"]]
[1, 2] [["A"], ["B"], ["C", "D"]]

Agora, preciso de partições de tamanho 2 ou mais, portanto, devo usar esta função com parâmetros ligeiramente diferentes. O parâmetro v é "tamanho da matriz - número de partições desejadas - 1". Então eu devo construir as partições de uma maneira ligeiramente diferente.

// Same call (4,2), same r, but the array b is of size 7
part = [...r,b.length].map((x,i)=>
          b.slice(z,z=x+i+1) // add 1 more element to each partition
       ,z=0))
// output in console (firebug) 
[2, 3] [["A", "B", "C"], ["D", "E"], ["F", "G"]]
[1, 3] [["A", "B"], ["C", "D", "E"], ["F", "G"]]
[1, 2] [["A", "B"], ["C", "D"], ["E", "F", "G"]]

Então, eu posso enumerar a lista de partições para nenhuma divisão, 1 divisão, 2 divisões e assim por diante. Quando encontro uma partição em funcionamento, pararei e exibirei o resultado encontrado.

Para verificar, verifique a lista de partições, observe os valores no início e no final de cada um, se houver um valor repetido e remova-o. Repita até que nada possa ser removido, afinal: se todos os pares foram removidos, esta partição é boa.

t = []; // array to note the repeated values
// t[x] == [
//           subarray holding value x, 
//           position of value x (I care zero or nonzero)
//         ]
n = a.length // counter start, must reach 0
// remember part just in case, because this check will destroy it 
result = part.join(';') // a string representation for return value
do
{
  // in the golfed code there is a forr loop
  // all this body is inside the for condition
  c = 0; // init c to a falsy, if a pair is found c becomes truthy
  part.forEach(b=> // b: array, current partition
    [0,1].forEach(q=> ( // exec for 0 (start), 1 (end)
      q *= b.length-1, // now q is the correct index
      x = b[q]) // x is the value at start or end
      x && ( // b could be empty, check that x is not 'undefined'
        t[x] ? // is there a value in t at position x?
           ( // yes, remove the pair
             n-=2, // pair found, decrement counter
             [c, p] = t[x], // get stored array and position
             p ? c.pop() : c.shift(), // remove from c at start or end
             q ? b.pop() : b.shift()  // remove twin value from b
           )
           : // no, remember the value in t
             t[x] = [b, q]
    )) // end [0,1].forEach
  ) // end part.forEach
}
while (c) // repeat until nothing can be removed
if(!n) return 1 // wow, result found (in 'result' variable)

Em seguida, a parte que falta é apenas um loop para calibrar a função G, aumentando a contagem de partições. O loop sai quando um resultado é encontrado.

Coloque tudo junto

F=a=>{
  G=(v,i,u=v)=>{
    if (i--)
    {
      for(; r[i]=--u; )
        if (G(u,i)) 
          return 1;
    }
    else
    {
      w = [...r,n=l].map((x,i)=>a.slice(z, z = x-~i), z = 0);
      y = w.join`;`;
      for(; // almost all the for body is inside the condition
        w.map(b=>
          [0,1].map(q=>
            (x=b[q*=~-b.length])
             &&(t[x]
                ?([c,p]=t[x],n-=2,
                   p?c.pop():c.shift(),
                   q?b.pop():b.shift())
                :t[x]=[b,q])) // end [0,1].map
          ,c=0,t=[] // init variables for w.map
        ),c; // the loop condition is on c
      )
        if(!n)return 1 // this is the for body
    }
  };
  for(l = a.length, r = [], k = 0; !G(l-k-1, k); k++);
  return y
}

Teste

F=a=>{G=(v,i,u=v)=>{if(i--){for(;r[i]=--u;)if(G(u,i))return 1;}else for(w=[...r,n=l].map((x,i)=>a.slice(z,z=x-~i),z=0),y=w.join`;`;w.map(b=>[0,1].map(q=>(x=b[q*=~-b.length])&&(t[x]?([c,p]=t[x],n-=2,p?c.pop():c.shift(),q?b.pop():b.shift()):t[x]=[b,q])),c=0,t=[]),c;)if(!n)return 1};for(l=a.length,r=[],k=0;!G(l-k-1,k);k++);return y}

console.log=x=>O.textContent+=x+'\n'

TestData=[[1,1],[1,2,1,2],[1,3,2,4,3,2,1,4],[1,2,3,4,3,4,1,2],[1,1,2,2,3,3],[4,3,4,2,2,1,1,3]]

TestData.forEach(t=>console.log(t+' -> '+F(t)))

function RandomTest() {
  var l=I.value*2
  var a=[...Array(l)].map((_,i)=>1+i/2|0)
  a.map((v,i)=>a[a[i]=a[j=0|i+Math.random()*(a.length-i)],j]=v) // shuffle
  Q.textContent=a+''+'\n\n'+F(a).replace(/;/g, ';\n') // better readability
}

Base test
<pre id=O></pre>
Random test. Number of pairs: <input id=I value=15><button onclick="RandomTest()">-></button>
<pre id=Q></pre>