Help me sort my socks!

Question

I have a pile of clean socks that I want to sort into pairs. Unfortunately, I can only take socks from either end of the pile, not the middle. Further, I can only remove socks from the pile a matching pair at a time. My strategy is to first split the pile into one or more smaller piles. I think some examples will make this clear. I'll represent each sock as a positive integer (matching integers indicate equal socks).

If the initial pile of socks is

1 2 3 3 2 1

then I don't have to do any splitting. I can remove both 1 socks, then both 2 socks, then both 3 socks.

If instead the initial pile is

1 2 3 2 3 1

then I have to split it first because I won't be able to pair all the socks by just removing them from the end. One possibility is to split it into the two piles

1 2 3 and 2 3 1

Now I can remove the 1 socks, leaving 2 3 and 2 3, followed by the 3 socks, leaving 2 and 2, and finally the 2 socks.

Your Job

Given the initial pile of socks, write a program that will split it into smaller piles that will allow me to sort the socks. Your program should split the pile into the fewest number of piles possible (if there are multiple best solutions, you need only find one).

The input will be given as a list, delimited string, or other convenient form. It will contain only integers between 1 and some maximum value n, with each integer occurring exactly twice.

The output should consist of the input list split into smaller lists, given in any convenient form.

Examples

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

Note that this isn't the only allowed output for most of these inputs. For the second case, for example, the outputs 1 2; 1 2 or 1 2 1; 2 would also be accepted.

Thanks to Sp3000 for some test suggestions!

I hate spending a long time sorting my clothes, so make your code as short as possible. Shortest answer in bytes wins!

Notes

• I don't want to have to look behind a sock to see if its matching pair is there, so taking both socks in a pair from the same end is not allowed. E.g. if the pile is 1 1 2 2 then you wouldn't be able to leave it as one pile and take both 1 socks from the left end.

Answer 1

Pyth, 25 bytes

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

Test suite

Explanation:

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.

Answer 2

JavaScript (ES6), 329

Not an easy task for a language that has no combinatorics builtins.

Probably sligthly more golfable.

Note: all partition are at least of size 2, as a partition with a single element is always less useful.

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}

Explanation in parts

(it's overly verbose, but I found it tough to explain - eventually skip to "put it all together")

A recursive function to enumerate all possible splits of an array

// 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"]]

Now, I need partitions of size 2 or more, so I must use this function with sligtly different parameters. The parameter v is "array size - number of desired partitions - 1". Then I must build the partitions in a slightly different way.

// 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"]]

So, I can enumerate the list of partitions for no split, 1 split, 2 splits and so on. When I find a working partition I will stop and output the result found.

To check, scan the partition list, note the values at start and end of each, if found a repated value then remove it. Repeat until nothing can be removed, at last: if all pairs were removed then this partition is good.

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)

Then, the missing part is just a loop caling the G function increasing the partition count. The loop exit when a result is found.

Put it all together

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
}

Test

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>