Necklace splitting problem

Jelly, 18 bytes

s2ZFṢ$€E¬,L
ŒṖṖÇÞḢ

Try it online!

Not efficient - the example has 28 jewels which wont work without huge resources since this implementation's first step would be to build a list of the 2²⁷ possible partitions.

Returns a list of lists - the segments in the order to dish them out between alternate thieves. (Re the TIO output: when a list only has a single item the implicit print does not bother with the brackets, [])

How?

s2ZFṢ$€E¬,L - Link 1, get (isUnfair, Slices): A possible partition
s2          - split into slices of length 2 (any odd one on it's own at the end)
  Z         - transpose (first item is one thief's slices, second is the others)
     $€     - last two links as a monad for €ach
   F        -     flatten
    Ṣ       -     sort
       E    - equal? (theif1's jewels == theif2's jewels)
        ¬   - not
          L - length (number of slices in the partition)
         ,  - pair

ŒṖṖÇÞḢ - Main link: necklace
ŒṖ     - all partitions
  Ṗ    - pop, we must remove the rightmost one...
              because Link 1 will say it is fair, and it will have length 1!
              (a list of one thing has all entries equal)
    Þ  - sort by
   Ç   -     last link (1) as a monad
     Ḣ - head (get the first one, i.e. minimal isUnfair, then minimal length)

Mathematica, 118 bytes

Almost beat Jelly ... just 1 off ;)

SelectFirst[l_±c_:=Append[-#±Most@c,#2]&@@l~TakeDrop~Last@c;l_±{}:={l};i=#;(i±#)&/@Range@#2~Subsets~#3,Tr[Tr/@#]==0&]&

Pure function taking three arguments: the necklace, as a list of tokens such as {A, A, A, A, B, C, D, B, C, D, B, B}; the length of the necklace; and the number of distinct jewel times. It returns a list of sublists in the form {{A, A}, {-A, -A, -B, -C, -D, -B}, {C, D, B, B}}, where the tokens without negative signs go to one thief and the tokens with negative signs go to the other thief. (While this is redundant information, the algorithm leads to this representation, and removing the negative signs would cost several bytes.)

First we have to implement a function that takes a list and a set of n cut-places and returns the list of n+1 sublists obtained by cutting the input list at those n cut-places; the binary infix operator ± is used for this purpose, and defined recursively through l_±c_:=Append[-#±Most@c,#2]&@@l~TakeDrop~Last@c;l_±{}:={l};. Because of the negative sign right after Append, the result is that the sublists alternately do and do not have negative signs attached to each token.

Then we generate all possible cut-place sets whose length is at most the number of jewel types, using Range@#2~Subsets~#3, and use i=#;(i±#)&/@ to apply the ± operator (with the input list of jewels) to each of these cut-place sets in turn.

Finally, SelectFirst[...,Tr[Tr/@#]==0&]& picks out the first of the resulting necklace divisions that is fair. It does so by literally adding up all of the elements in all of the sublists; Mathematica is wise enough to cancel the positive and negative copies of each token in the obvious way.

Pyth, 16 bytes

hfqFSMsM.TcT2t./

Try it online: Demonstration or Test Suite

Explanation:

hfqFSMsM.TcT2t./Q   implicit Q (=input) at the end
              ./Q   create all partitions of the input list 
                    (they are already sorted by number of cuts)
             t      remove the partition with zero splits
 f                  filter for partitions T, which satisfy:
          cT2          chop into pieces of length 2
        .T             transpose to get the pieces of each thieve
    SMsM               combine all pieces for each thieve and sort the results
  qF                   check if they got the same jewels
h                   print the first such partition