Mam kupę czystych skarpet, które chcę poskładać w pary. Niestety mogę wziąć skarpetki tylko z dowolnego końca stosu, a nie ze środka. Co więcej, mogę jednocześnie usunąć skarpetki ze stosu pasującej pary. Moją strategią jest najpierw podzielić stos na jeden lub więcej mniejszych stosów. Myślę, że niektóre przykłady to wyjaśnią. Przedstawię każdą skarpetę jako dodatnią liczbę całkowitą (pasujące liczby całkowite oznaczają równe skarpetki).

Jeśli początkowy stos skarpet to

1 2 3 3 2 1

wtedy nie muszę robić żadnego podziału. Mogę usunąć obie 1skarpetki, potem obie 2skarpety, a następnie obie 3skarpetki.

Jeśli zamiast tego początkowy stos to

1 2 3 2 3 1

potem muszę go najpierw podzielić, ponieważ nie będę w stanie sparować wszystkich skarpet po prostu usuwając je z końca. Jedną z możliwości jest podzielenie go na dwa stosy

1 2 3 and 2 3 1

Teraz mogę zdjąć 1skarpetki, odejść 2 3 and 2 3, następnie 3skarpetki, odejść 2 and 2i wreszcie 2skarpetki.

Twoja praca

Biorąc pod uwagę początkowy stos skarpet, napisz program, który podzieli go na mniejsze stosy, które pozwolą mi posortować skarpetki. Twój program powinien podzielić stos na możliwie najmniejszą liczbę stosów (jeśli istnieje wiele najlepszych rozwiązań, potrzebujesz tylko jednego).

Dane wejściowe zostaną podane w postaci listy, łańcucha rozdzielanego lub innej dogodnej formy. Będzie zawierał tylko liczby całkowite pomiędzy 1i pewną maksymalną wartość n, przy czym każda liczba całkowita będzie występować dokładnie dwa razy.

Dane wyjściowe powinny składać się z listy danych wejściowych podzielonej na mniejsze listy, podane w dowolnej dogodnej formie.

Przykłady

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

Zauważ, że nie jest to jedyne dozwolone wyjście dla większości tych danych wejściowych. W drugim przypadku na przykład dane wyjściowe 1 2; 1 2lub 1 2 1; 2byłyby również akceptowane.

Dzięki Sp3000 za sugestie dotyczące testów!

Nienawidzę spędzać długiego czasu na sortowaniu ubrań, więc skróć swój kod tak krótko, jak to możliwe. Najkrótsza odpowiedź w bajtach wygrywa!

Notatki

• Nie chcę patrzeć za skarpetę, aby sprawdzić, czy jest tam pasująca para, więc zabranie obu skarpet w parę z tego samego końca nie jest dozwolone. Np. Jeśli stos jest 1 1 2 2, to nie będziesz mógł zostawić go jako jednego stosu i wziąć obu 1skarpet z lewego końca.

Pyth, 25 bajtów

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

Zestaw testowy

Wyjaśnienie:

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

Nie jest to łatwe zadanie dla języka, który nie ma wbudowanych funkcji kombinatoryki.

Prawdopodobnie nieco bardziej golfowy.

Uwaga: wszystkie partycje mają co najmniej rozmiar 2, ponieważ partycja z jednym elementem jest zawsze mniej przydatna.

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}

Objaśnienie w częściach

(jest to zbyt szczegółowe, ale trudno mi to wyjaśnić - w końcu przejdź do „poskładaj wszystko”)

Funkcja rekurencyjna do wyliczania wszystkich możliwych podziałów tablicy

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

Teraz potrzebuję partycji o rozmiarze 2 lub większym, więc muszę użyć tej funkcji z nieco innymi parametrami. Parametr v to „rozmiar tablicy - liczba pożądanych partycji - 1”. Następnie muszę zbudować partycje w nieco inny sposób.

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

Mogę więc wyliczyć listę partycji dla braku podziału, 1 podziału, 2 podziałów i tak dalej. Kiedy znajdę działającą partycję, zatrzymam się i wyprowadzę znaleziony wynik.

Aby to sprawdzić, zeskanuj listę partycji, zanotuj wartości na początku i na końcu każdej z nich, jeśli znalazłeś powtórzoną wartość, usuń ją. Powtarzaj, aż w końcu nic nie będzie można usunąć: jeśli wszystkie pary zostały usunięte, ta partycja jest dobra.

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)

Zatem brakująca część jest po prostu pętlą calującą funkcję G, zwiększającą liczbę partycji. Pętla kończy się po znalezieniu wyniku.

Poskładać wszystko do kupy

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>