Tengo un montón de calcetines limpios que quiero clasificar en pares. Desafortunadamente, solo puedo tomar medias de cualquier extremo de la pila, no del medio. Además, solo puedo quitar los calcetines de la pila de un par a la vez. Mi estrategia es dividir primero la pila en una o más pilas más pequeñas. Creo que algunos ejemplos aclararán esto. Representaré cada calcetín como un entero positivo (los enteros coincidentes indican medias iguales).

Si la pila inicial de calcetines es

1 2 3 3 2 1

entonces no tengo que hacer ninguna división. Puedo quitar los dos 1calcetines, luego los dos 2y luego los dos 3.

Si en cambio la pila inicial es

1 2 3 2 3 1

luego tengo que dividirlo primero porque no podré emparejar todos los calcetines simplemente quitándolos del final. Una posibilidad es dividirlo en dos pilas

1 2 3 and 2 3 1

Ahora puedo quitar los 1calcetines, irme 2 3 and 2 3, seguidos de los 3calcetines, irme 2 and 2y finalmente los 2calcetines.

Tu trabajo

Dado el montón inicial de calcetines, escriba un programa que lo dividirá en montones más pequeños que me permitirán ordenar los calcetines. Su programa debe dividir la pila en la menor cantidad posible de pilas (si hay varias mejores soluciones, solo necesita encontrar una).

La entrada se dará como una lista, cadena delimitada u otra forma conveniente. Contendrá solo enteros entre 1y un valor máximo n, con cada entero exactamente dos veces.

El resultado debe consistir en la lista de entrada dividida en listas más pequeñas, en cualquier forma conveniente.

Ejemplos

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

Tenga en cuenta que esta no es la única salida permitida para la mayoría de estas entradas. Para el segundo caso, por ejemplo, las salidas 1 2; 1 2o 1 2 1; 2también serían aceptadas.

¡Gracias a Sp3000 por algunas sugerencias de prueba!

Odio pasar mucho tiempo clasificando mi ropa, así que haga su código lo más corto posible. ¡La respuesta más corta en bytes gana!

Notas

• No quiero tener que mirar detrás de un calcetín para ver si su par coincidente está ahí, por lo que no está permitido tomar ambos calcetines en un par del mismo extremo. Por ejemplo, si el montón es 1 1 2 2así, no podría dejarlo como un montón y tomar ambos 1calcetines del extremo izquierdo.

Pyth, 25 bytes

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

Banco de pruebas

Explicación:

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

No es una tarea fácil para un lenguaje que no tiene incorporados combinatorios.

Probablemente un poco más golfable.

Nota: todas las particiones son al menos de tamaño 2, ya que una partición con un solo elemento siempre es 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}

Explicación en partes

(es demasiado detallado, pero me resultó difícil de explicar, eventualmente salte a "poner todo junto")

Una función recursiva para enumerar todas las divisiones posibles de una 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"]]

Ahora, necesito particiones de tamaño 2 o más, por lo que debo usar esta función con parámetros ligeramente diferentes. El parámetro v es "tamaño de matriz - número de particiones deseadas - 1". Luego debo construir las particiones de una manera ligeramente 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"]]

Por lo tanto, puedo enumerar la lista de particiones sin división, 1 división, 2 divisiones, etc. Cuando encuentre una partición que funcione, me detendré y mostraré el resultado encontrado.

Para verificar, escanee la lista de particiones, tenga en cuenta los valores al inicio y al final de cada uno, si encuentra un valor reparado, elimínelo. Repita hasta que no se pueda eliminar nada, por fin: si se eliminaron todos los pares, entonces esta partición es buena.

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)

Entonces, la parte que falta es solo un ciclo que llama a la función G y aumenta el recuento de particiones. La salida del bucle cuando se encuentra un resultado.

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

Prueba

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>