[Question]
  [
Given a string, shuffle it so that it becomes a palindrome.
For example, `adadbcc` can be arranged into `dacbcad`, or `dcabacd`, `acdbdca` and more. Any of these (or all) is acceptable, and duplicates are allowed if outputting all. Something like `abc` cannot be shuffled into a palindrome, and you can assume it won't be inputted.
(if it helps) input will only contain lowercase letters.
## Testcases
These show one possible solution.
```
nanas -> nasan
coconutnut -> conuttunoc
apotato -> atopota
manplancanalpanamaaaa -> amanaplanacanalpanama
canadadance -> canadedanac
nananana -> nanaanan
anaan -> anana
```
  
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog), 3 bytes
```
p.↔
```
[Try it online!](https://tio.run/##SypKTM6ozMlPN/r/v0DvUduU//@VkvOT8/NKS4BI6X8UAA "Brachylog – Try It Online")
[Also acts as a generator for all possible outputs](https://tio.run/##SypKTM6ozMlPN/r/qG3Do6bGh9sW/C/Qe9Q25f9/pbzEvMRipf9RAA).
### Explanation
```
p.         The output is a permutation of the input
 .↔        The output reversed is itself
```
[Answer]
# [J](http://jsoftware.com/), 21 bytes
```
(,~`,/@/:2|1#.e.)@/:~
```
[Try it online!](https://tio.run/##y/qvpKeepmBrpaCuoKNgoGAFxLp6Cs5BPm7/NXTqEnT0HfStjGoMlfVS9TSBzLr/mlypyRn5CmkK6sn5yfl5pSVApA4Xy0vMSyxGcBML8ksSS/JR5UEQSSQvMTFR/T8A "J – Try It Online")
A non brute force approach which runs in n\*log(n) time.
* `/:~` Sort. This ensures that like elements are grouped together.
* `/:2|1#.e.` Then sort by number of occurrences, modded by 2. This puts any items with an odd number of elements at the end of the array, while keeping like elements together.
* `,~`,/@` Reduce that from the right by alternately appending and prepending elements. The upshot is that we start with the middle element, and then build outward by adding pairs of elements to opposite sides.
[Answer]
# [Python 3](https://docs.python.org/3/), 72 bytes
```
*r,=s={''}
for c in input():s^={c};r+={c}-s
print(*r,*s,*r[::-1],sep="")
```
[Try it online!](https://tio.run/##HU2xbgMxCN35CstL7q6XIermymO6ZslWtRIlVDn1gi3sUxNF@fYL7nsPEKAH@VbPSV5XSid20Xnv10HHWOJ9s3nAT1JHbhJTXmrXh/IV7/R405dWtgWyTlI7cwxlHPQjhO3ucyyco/f9ascA/s7TzO6oCwdwhqq34PjK1LWX/f@Mr8S5uv3hfa@aNLhvZfxdBQULUKIkSzUB5lSxJrig5BmFbD9nSxc0QGtPRiGGZm0ECxR4Ag "Python 3 – Try It Online")
Saved 2 bytes by [pxeger](https://codegolf.stackexchange.com/users/97857/pxeger) and [xnor](https://codegolf.stackexchange.com/users/20260/xnor). It could be [66 bytes](https://tio.run/##HU2xbsNACN35CuTJjpUh6naVx3TN0s1yJEqoYtXhTtxZTRTl212u7z1APASkR7lGfds4XgQHbJpms2GcIA/Pnb3gOxoyzupKa2m7kM/Dk1/v1teyz5Bs1tJaP@7y1NsYwv4wdZufAfi9zovgp60SAB3FHgHlLtzWZ92/J3eWVPB4@jiaRQv4ZUI/m5JSBo4cdS0uoBQLlQg30rSQss@X5OlGDqjtxaksUFcrwYP0Dw) as xnor pointed out if output as list of characters.
It is \$O(n)\$.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 4 bytes
```
œʒÂQ
```
[Try it online!](https://tio.run/##yy9OTMpM/f//6ORTkw43Bf7/n1iQX5JYkg8A "05AB1E – Try It Online")
# Explanation
```
œ          all permutations of the (implicit) input
ʒ          only keep those such that
 Â         push x, reversed(x)
 Q         they are equal
```
[Answer]
# [Python](https://www.python.org), 67 bytes
```
lambda x:(s:=sorted(x,key=lambda e:(x.count(e)%2,e)))[1::2]+s[::-2]
```
[Attempt This Online!](https://ato.pxeger.com/run?1=PU9NqsJADF7bUwyCOINVsKvHwKw8hnYRpynP99rM0EmhnsVNQfQeHsPbWNvREPLzfeFLcrn7M_866q-lOdxaLtc_z10F9bEA0WkZtAmuYSxkl_7j2UQGtew21rXEEtUiS1Eptd9qneWrsNd6neVR6lFgKRgDSwsBlU5mDYa2YmFEOUHJzDenQWe53Py5E8mJV6n4DJpYvXW3eSriPXHuzUdklFNJMq6bW2cdtTz4XEUIvGNg9-1rIF8BWSCo_BBqGOzLEo3d9EjfT_kF)
Port of [Jonah's excellent J solution](https://codegolf.stackexchange.com/a/250289/85334).
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 69 bytes
```
a=>[...p=a.filter(c=>!(a[c]^=1)),...a.filter(c=>a[c]),...p.reverse()]
```
[Try it online!](https://tio.run/##bczBCoMwDAbg@95iXmxhK@wB4ouIg1CjKDUpbfX1u7jTYCYhh/@Df8UDs09LLE@WkeoMFaHrnXMR0E1LKJSMh@5usPfDG17WPhR/6YRvGF2ig1ImY4c6QYZuNmdTHqxbZWHTtvbmhbMEckFmM5mGkTE39i/3osFe9C4QoxQsciEbcgzIXltD1LehzlW92qjLnlTrBw "JavaScript (Node.js) – Try It Online")
---
# [JavaScript (Node.js)](https://nodejs.org), 78 bytes
```
f=(s,c='',r=s.replace(/^(.)(.*)\1|./,'$2'),t=RegExp.$1)=>s?t+f(r,t?c:s[0])+t:c
```
[Try it online!](https://tio.run/##bY7NCsIwEITvPkYpJLExtR4LsSdfwKs/sGzToqRJaFbx4LvXPUtnhz3MB8M84Q0Z50eiXYi9WwbLllmjFULPNpvZJQ/oZH2XRkmzVdfma2otyoNQmuzZjadPMmWj7DF3VA1y1tRhmy/7m6qoxQVjyNE74@MoB1kECJALpTZ/OUYOXsRegZAiAcUVMkHgfQG51Sd@E7DW6pn1fAEd0@UH "JavaScript (Node.js) – Try It Online")
Input / Output as strings.
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~124~~ ~~108~~ 107 bytes
*16 bytes saved thanks to [c--](https://codegolf.stackexchange.com/users/112488/c)! 1 byte saved thanks to ceilingcat!*
```
f(c,n,i,j,k)char*c;{for(i=j=0;i<n;i++)j=*c-c[i]?j:i;k=c[i=j?n--,n--:i/2];
c[i]=c[j];c[j]=k;n>2&&f(c+!!j,n);}
```
[Try it online!](https://tio.run/##ZY/RboMgFIbv@xTUZA1WzFYvy2gfZOvFKdUN1IMRtmRr@uzuaF0WmRhy@P7//Bx0/qb1MFRcCxRGWFGn@h36rZbXyvXcKKuepHlGabIstWqrc/1iTke7N7JWVCp7xFwVwuS7vXksTnKUSbBjZU@qlngoNhvKz9ZrKzCVt@HTmQsLpQ98uor5XqfsumL0GQysKZEp5kNPBR81OUl3L5DUQtM4zb35Ll01ZaRbTuZsl85eatbdFwfB/vq7nsIrnjzkxc6z/MASwWDWqtFKCbHVv@Lsuq1W42wtGOS/w05PSJK56X6C5fEMEQA4LwECgo8ReFwiT64IIdngf9a4llQTudBCXUaC0w4/Av3RjJ0LEFwEgxvxEraAXUPBdEPT0dbCPNNt@AE "C (gcc) – Try It Online") Linebreak added for clarity. Function `f` which takes as input a pointer to the start of a `char` array and its length as `n`. Modifies the input array in place, yielding a single result.
Annoying that I can't save a few bytes by using `c[i]^=c[j]^=c[i]^=c[j]` instead of a standard switch, but this expression fails when `i == j`, and accounting for that doesn't end up saving any bytes.
## Commented explanation
*Slightly outdated, but the same general concept is the same. In the current version, we infer the count by observing that `k` is 1 if and only if `j` is 0.*
```
f(c,n,i,j,k,t) char*c; {
    // count the number of instances of the first character, *c
    for(i = k = 0; i < n; i++)
        // if we found *c in the string
        *c == c[i]
            ? k++, j = i // then note it in our tally, and note its index as j
            : 0;         // else do nothing
    
    // i is now the original length n
    // j is now the index of the last occurrence of *c
    
    // we will check if there is more than one occurrence of *c
    --k
        // this is truthy iff k > 1. in this case, we set up further recursion
        ? n -= 2,   // deduct the two solved characters from the solve length
          i--       // we want to swap with the end of the string (i=n-1)
        // else, if k == 1, then we need to put this character in the middle
        // to properly palindromize it
        : (j = 0,   // we want to swap the lone character (at j=0)
           i /= 2); // with the center character (at i=n/2).
    
    // swap characters at positions j and i
    // when k>1,  swaps the last occurrence of *c with the end of the string
    // when k==1, swaps the first character with the middle of the string
    t = c[i];
    c[i] = c[j];
    c[j] = t;
    
    // if n < 2, the string is solved
    // otherwise, we will recurse as follows:
    //  - when k was initially >1, k is now k-1, and !!k evaluates to 1,
    //    letting us recurse starting with c+1.
    //    in this case, n is now n-2, letting us recur on the string without
    //    the bookending characters
    //  - when k was initially 1, k is now 0, and !!k evaluates to 0.
    //    this means we recurse with c, and examine the character we
    //    just swapped there. n is also unchanged in this branch.
    //    furthermore, this swap only ever happens once because
    //    we check n > 2 before attempting to recurse.
    n > 2 && f(c + !!k, n);
}
```
[Answer]
# [Python](https://www.python.org), 120 bytes
```
lambda a,j="".join:[C:=Counter(a),x:=j(C[c]//2*c for c in C)][1]+j(C[c]%2*c for c in C)+x[::-1]
from collections import*
```
[Attempt This Online!](https://ato.pxeger.com/run?1=XY1RCsIwEET_PUUoCK1tLfolgX71GLXCGg2mJLshbqGexZ-C6J28jYWKUIdlBt4szP3lb3whHB663D871vnu3VtwxxMIyNoyitYtGZR1JcuKOuRziCHJelm2cVWrpii2KyU0BaGEQVElTb1p0qlb_lVpX0uZb5qFDuSEImvPig3hVRjnKfDqu3_wwSDHOo4UKcKOx4uSZPHD4ImBacYcoLeAChCsH83BqNkH4kSmlWGY8gM)
There's probably a much shorter way to do this in \$ O(n!n) \$ time or something silly like that, but this is linear I think.
# [Python](https://www.python.org), 94 bytes
```
lambda a,j="".join:(x:=j(a.count(c)//2*c for c in{*a}))+j(a.count(c)%2*c for c in{*a})+x[::-1]
```
[Attempt This Online!](https://ato.pxeger.com/run?1=ZY1bCsIwEEX_XUUICElrW_RLAlmJDxhHgi3tTCgpVMSV-FMQ3ZO7MVAUi8MwF84cuLenP4cT03B3dvvogsvWr30NzeEIAhaVlTKvuCSjemMrBTlyR0GhLopVgsJxK1CUdEngqnX6K8z__mm_MSZb7j4tvi2j6ZRERqYuxJVaz74YPAcIPGENkK-BEAhqH08DcSYG0UjGlmEY8w0)
A little shorter, but runs in \$ O(n^2) \$ time.
[Answer]
# [lin](https://github.com/molarmanful/lin), 19 bytes
```
`perm".+ `rev `="`?
```
[Try it here!](https://replit.com/@molarmanful/try-lin)
For testing purposes (use `-i` flag if running locally):
```
"nanas" ; `_
`perm".+ `rev `="`?
```
## Explanation
Prettified code:
```
`perm (.+ `rev `= ) `?
```
* ``perm` permutations
* `(...) `?` find first...
	+ `.+ `rev `=` palindrome
[Answer]
# [Curry (PAKCS)](https://www.informatik.uni-kiel.de/%7Epakcs/), 41 bytes
```
f a@([]?[_])=a
f(a:b++a:c)=a:f(b++c)++[a]
```
[Try it online!](https://tio.run/##Sy4tKqrULUjMTi7@/z9NIdFBIzrWPjo@VtM2kStNI9EqSVs70SoZyLNK0wCykzW1taMTY//nJmbmKdgqpCkoJecn5@eVlgCR0n8A "Curry (PAKCS) – Try It Online")
This may returns multiple results, with duplicates, but not necessarily all of them. If this is not allowed, you can add the flag `:set +first` to print only the first result: [Try it online!](https://tio.run/##DcdBCoAgEEbhfaeQVsbQBYSoe4jE39REVBJaiy7fJG/zPX5SetsLO2dVMRisD70fQ9OhEgs3EcFxOSe2mBsij6Antmg6I6ZmRMylyEutH8uBNavLy60kW8r3Dw "Curry (PAKCS) – Try It Online").
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal), 4 bytes
```
Ṗ'Ṙ=
```
[Try it Online!](https://vyxal.pythonanywhere.com/#WyIiLCIiLCLhuZYn4bmYPSIsIiIsImFwb3RhdG8iXQ==) Outputs all possibilities with duplicates. Add `;U` to remove them. Takes permutations and only keeps those that are equal after reversal.
[Answer]
# [Prolog (SWI)](http://www.swi-prolog.org), 35 bytes
```
X+P:-permutation(P,X),reverse(P,P).
```
[Try it online!](https://tio.run/##KyjKz8lP1y0uz/z/P0I7wEq3ILUot7QksSQzP08jQCdCU6cotSy1qDgVyAnQ1PtvpauQkJyfnJ9XWgJECdp@Ogpp@UW5iSUaSnXFSjrRfrFARQA "Prolog (SWI) – Try It Online")
Prolog is perfect for this. I/O as a list of char codes (or list of atoms or list of strings, doesn't matter).
If there are multiple solutions, each solution is its own choice point (may contain duplicates): [Try it online!](https://tio.run/##KyjKz8lP1y0uz/z/P0I7wEq3ILUot7QksSQzP08jQCdCU6cotSy1qDgVyAnQ1PtvpauQkJiSmJKUnJyg7aejkJZflJtYoqFUVxyTp6QT7RerCRRLzClO1fsPAA "Prolog (SWI) – Try It Online") If there are none, the goal will simply fail.
In fact, the first argument doesn't even have to be instanciated. If you run with both non-initialized, the first one will just infinitely produce all possible ways to arrange variables in a list where it is possible to rearrange to a palindrome, and the second one will be it rearranged to a palindrome.
You can even do the reverse operation - given a palindromic string for the output, it will give all inputs that will produce that output. [Try it online!](https://tio.run/##DchBCoAgEADAr4inRO0BvcLjQgVtsYVQGbtWt75uHmcuTnvavLyxFLCh8xfxcWfMMZ1NcGAc00MsVBFMWzqvwE44LzNOTq2JD8yN/mQ4tVM9jKYm7kJt@QE "Prolog (SWI) – Try It Online")
[Answer]
# [Ruby](https://www.ruby-lang.org/), 41 bytes
```
->a{a.permutation.select{_1==_1.reverse}}
```
[Attempt This Online!](https://ato.pxeger.com/run?1=RU9bCsJADPzvKcoKomAX-idCvUgRiWuKFc2WfQhSehJ_iuhhPIK3MdGqJJBkJjMhl5uLm3N_rYp7DFU2f06zJbSgG3THGCDUlrTHA5rQrvOiWOfa4Qmdx64bBI8yUQQEXs3SUbZMefBAKlHGGksxcH6Z9xwiWcM0NJb97ZfjVgDRsdmWgwz-hAIhQyBKuSbxP0gggJhKpwbH906y0ghm1zYx-LQq-QGzA-dX-gjNZLzY25qmuqqdD8NDff-pLw)
Inputs and outputs array of chars. Output contains all answers with duplicates, but test suite prints only the first one, so that it doesn't flood the output.
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 33 bytes
```
Select[PalindromeQ]@*Permutations
```
[Try it online!](https://tio.run/##DcoxCoAwDEDRq0hH7yAUvEDFURxCTWmhaSSN548Z/vDhEWhFAm0ZrGx2YsesV4LexiNMeNxxTSj0qRse05K0oUtcirdXEMiKMn0CvOyIg/0 "Wolfram Language (Mathematica) – Try It Online")
-1 byte thanks to att
[Answer]
# [Alice](https://github.com/m-ender/alice), 19 bytes
```
/@P?w$.R/
\IO>K.-!\
```
[Try it online!](https://tio.run/##S8zJTE79/1/fIcC@XEUvSJ8rxtPfzltPVzHm///EgvySxJJ8AA "Alice – Try It Online")
```
/IP>w..!R-$K?O@      Full program
/                    Switch to ordinal mode
 IP                  Read the input and generate all the possible permutations
   >w     $K         For each permutation
      .!             Store a copy of the permutation on the tape
     .  R            Reverse the permutation
         -           Subtract the reversed permutation from the permutation (leaving "" if it is a palindrome, exiting the loop)
            ?O@      Print the tape
```
[Answer]
# [Nekomata](https://github.com/AlephAlpha/Nekomata), 4 bytes
```
↕:↔=
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m70iLzU7PzexJHFNtJJurpKOgpKuoVLsgqWlJWm6FisetU21etQ2xXZJcVJyMVRwwU17pbzEvMRiJS6l5Pzk_LzSEiACchIL8ksSS_JBwkDpFCDMS04F8kCKQRCkJC8xMU8JYg4A)
A port of [@Fatalize's Brachylog answer](https://codegolf.stackexchange.com/a/250297/9288).
```
↕:↔=
↕       Permutation
 :      Duplicate
  ↔     Reverse
   =    Check equality
```
Returns all solutions with duplicates. You can add the `-1` flag to print only the first solution.
[Answer]
# JavaScript (ES6), ~~63~~ 62 bytes
Expects and returns a string.
```
f=s=>s==(S=s.replace(/(.)(.*)\1/,(_,A,B)=>(s=A,B)))?s:s+f(S)+s
```
[Try it online!](https://tio.run/##ZU9BTgMxDLzvK6w9NA5dUnFtla1A4gU9lgpZaRZabZNVHHpB/ACJC0f4B@/pB3jC4tWWC9iW5fHYHnlPR2KXdl2@DHHr@76xbGu2FleWTfJdS87jDI1Gc6HvrmYV3lfX1Y22NbIdCq2XPOdpgys95X6xLgDKQIG4rIbSRRfDU5YYMXUxU44jOFAQgeBkvO0kHUjsvCdwKx6cHxvDzcHPZwJRKItNYZqYbsk9IoOt4Vm41mdIYKFB1gvBos@x9aaND5gqWBtj0kZeO/rEHrXZx11ApTRYK3uTye8Ex5T/0APD/5klqO@vt9PHu2QFc1Cnz1cl2i@6/wE "JavaScript (Node.js) – Try It Online")
### Commented
```
f =              // f is a recursive function
s =>             // taking the input string s
s == (           // test whether s is unchanged
  S = s.replace( // when turned into the reduced string S
                 // obtained by looking in s for:
    /(.)(.*)\1/, //   a character A, followed by some string B
                 //   (which may be empty), followed by A
    (_, A, B) => //   if found,
      (s = A, B) //   copy A into s and replace the match with B
  )              //   (i.e. both instances of A are removed)
) ?              // if S is equal to s:
  s              //   we're left with either an empty string or a
                 //   single character; either way, this ends up
                 //   in the middle of the output
:                // else:
  s + f(S) + s   //   append s, followed by the result of a
                 //   recursive call with S, followed by s again
```
[Answer]
# [Perl 5](https://www.perl.org/) `-F` , 57 bytes
```
$_=join"",sort@F;s/(.)\1/!push@r,$1/ge;say@r,$_,reverse@r
```
[Try it online!](https://tio.run/##K0gtyjH9/18l3jYrPzNPSUmnOL@oxMHNulhfQ08zxlBfsaC0OMOhSEfFUD891bo4sRLEjtcpSi1LLSpOdSj6/z8pMQ8Ik/7lF5Rk5ucV/9d1@6/ra6pnYGgAAA "Perl 5 – Try It Online")
[Answer]
# [Haskell](https://www.haskell.org/), 52 bytes
```
import Data.List
find(\x->x==reverse x).permutations
```
[Try it online!](https://tio.run/##HYxNDsIgEIX3nmLCqk2UG@DKpZ5Au5hQjMQyM4Gp4fYIzfc2L@/ng@Ubtq3FJJwVbqho77HoKWEkcJBQHjBJjqRWZngaQsJizmA8e6Zdu4ZDYUXlI@iNtUM@DDsGg6NFiGSWJu4daZ1e9XKtzuXwC7kEqLOVkNPejyJTae0P "Haskell – Try It Online")
Pretty new to Haskell so I'm very open to suggestions on how this could be improved, because I have a feeling it can be a lot - especially concerning that lambda, but I couldn't find how to make it pointfree.
[Answer]
# [APL (Dyalog Classic)](https://www.dyalog.com/), 19 bytes
```
{⌊/⍵=⌽⍵:⍵⋄∇⍵[?⍨≢⍵]}
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT9dNzkksLs5M/v@/IDEnMy@lKD839VHbhOpHPV36j3q32j7q2QukrID4UXfLo452ICPa/lHvikedi4DM2Nr///8DAA "APL (Dyalog Classic) – Try It Online")
**Usage:**
```
      palindrome←{⌊/⍵=⌽⍵:⍵⋄∇⍵[?⍨≢⍵]}
      palindrome 'baba'
baab
      palindrome 'daabbcc'
cbadabc
```
[Answer]
# [Factor](https://factorcode.org/) + `math.combinatorics`, ~~41~~ 38 bytes
```
[ [ dup reverse = ] find-permutation ]
```
[Try it online!](https://tio.run/##DcoxDsIwDAXQvaf46t4eAMRcsbAgpqpDSF0RkTjGcZA4fcj83uG8ZW2P@/W2nPAmZYoo9KnEngqSs9fsc3oGdv0FXyBKZj/RwIbzMIxOsnUb24oVexUofUkL4YINR@B9EtJU@wmZsTXvYsTc/g "Factor – Try It Online")
[Answer]
# [J-uby](https://github.com/cyoce/J-uby), 33 bytes
Port of [Kirill L.’s Ruby answer](https://codegolf.stackexchange.com/a/250300/11261).
```
:permutation|:select+:==%:reverse
```
[Attempt This Online!](https://ato.pxeger.com/run?1=RU9LCsJADN33FHWKoqgFdzJQl15CpMQYacVmynwEUU_ipgjexgt4G2eqVRJI8t7LC7k99rnbnJr7Mns4u5vOXz1Zk66cBVsqvkhDB0I7llnWl5qOpA19hc9VJBgYjJjEyXQR-8EAi0igQsXO-uyYdraOFXoaauXNVcf5NgAiSgR6t60PRvptBog8BBgU4V6I_0mGAASubcXXtBVF65QAi3PtrImXq3yWYgHarNMK6uFA7lXJo3RXamOvn5-a5lPf)
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 5 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
Outputs all possibilities. Replace `f` with `æ` to output just 1.
```
á fêQ
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=4SBm6lE&input=ImFkYWRiY2Mi)
[Answer]
# [Retina](https://github.com/m-ender/retina/wiki/The-Language), 35 bytes
```
O`.
|""L^`((.)\2)*.?
$
$^$`
(.).
$1
```
[Try it online!](https://tio.run/##FUtBCoQwELvnGdKFuoeCfmCPexH8wCIN1YOg01Lrzb93p8kkkAzJW9mFQ33Zr6@zd3i6blq8ta7/jf3bfWBgFuOhhYMZahUKL4QYotxFD0yxsESclHRQgv6PpHZSgRZXpYQNbdoIFQUrc@Yf "Retina – Try It Online") Link includes test cases. Explanation: Based on @Jonah's J solution.
```
O`.
```
Sort the characters into order.
```
|""L^`((.)\2)*.?
```
If there's an odd character, split the string after that point and exchange (`^`) and join (`|""`) the two halves. (There's also an empty string in the results but obviously it doesn't have any effect.)
```
$
$^$`
```
Append the reverse of the string.
```
(.).
$1
```
Drop every other character.
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 24 bytes
```
≔Φθ﹪№…θκι²ηηΦΦθ﹪№θι²¬κ⮌η
```
[Try it online!](https://tio.run/##S85ILErOT8z5/9@xuDgzPU/DLTOnJLVIo1BHwTc/pTQnX8M5vzSvRMO5Mjkn1TkjvwAkk62po5AJxEaaQCJD05oroCgTqAbBghqCw6xCJN1@@SUa2ZqacJ1BqWWpRcWpQLM0rf//T0ksKkr8r1uWAwA "Charcoal – Try It Online") Link is to verbose version of code. Explanation:
```
≔Φθ﹪№…θκι²ηη
```
Using my code from [Generate an arbitrary half of a string](https://codegolf.stackexchange.com/q/250213), extract half (rounded down) of the characters from the string, but also save it in a variable.
```
ΦΦθ﹪№θι²¬κ
```
If there was a character that appeared an odd number of times then output it. (Now if only `Maximum("")` returned the empty string...)
```
⮌η
```
Output the reverse of the half string.
[Answer]
# x86-64 machine code, 31 bytes
```
31 C9 FF CA AC 0F BB C1 73 FA 88 04 17 AA 83 EA 02 77 F1 75 09 0F BC C1 75 01 AC 0C 60 AA C3
```
[Try it online!](https://tio.run/##VZPBjtowEIbPmaeYpkJKlrBiacthKb3suZeeKrEcjD0h3jp2ZBsainj10jEBVpUSK575/2/GHkV23WQr5fksQosF/sgLeNwatxEGa6ifIeudR5J9lRbIFEkk1YOnjkTktHEqbCDbRHlVCVa9WYmDArLW7XHllR571a8rFAayEF3yhN0msSqcsUPcDW/2D5JVzAx1wl0rp3D4pbtbyfTN9bk7YSqc9vPpDcxmTniKUOZYLoD6SN5i/pLjce@0wrqQjfD44CnsTKxQOhsiDrFQobYRgyFbLk4AH7WVZqcIv4aotHtsvv0X8tpuUwySqRXaFiUcIbuwtO12cTX7MudjD6UumwVkvxttCIsgha2LfBTyahCXuFziUwkZI7JENLhELsLNFIOAzVld3Bq/xCo0l/C1hFmzZ5oCHTcXE3/yNA@j8Grzu2PQJtsJ7rpX@13IRlviC1H0nKd0aqJPwAoPvFUOjzc5jqazn4w8LItiZ4PeWlKXS3wo63LVj8drvkC8HvWAHxjSv3xK0DuhGGncHCKF8tJcz8nT@RyIAiinHETh@QHRdcIYiCTaVkQCnpfUQfPUIDoHztUQml1oYK/3WkGgyAPnHFfh8bzLwYgN8WsIOk9Sd1oOMIbaBPbEFtp6kXx/ZW3ENpwn7fwzL/x/LFPW/AM "C++ (gcc) – Try It Online")
Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes the address of the input, as an array of single-byte characters, in RSI and its length in RDX, and takes in RDI an address at which to place the result, as a non-overlapping array of single-byte characters of the same length.
Part of this is similar to [my answer to "Generate an arbitrary half of a string"](https://codegolf.stackexchange.com/a/250369/104752).
In assembly:
```
f:
    xor ecx, ecx    # Set ECX to 0.
    dec edx         # Subtract 1 from the length in EDX.
repeat:
    lodsb           # Load a byte from the string into AL, advancing the pointer.
    btc ecx, eax    # Invert the bit in ECX indexed by the low 5 bits of that byte.
                    #  Set CF to the previous value of that bit.
    jnc repeat      # Jump back if CF is 0.
    mov [rdi+rdx], al   # Place the byte at a position that starts from the end of
                        #  the output string and will move backwards.
    stosb           # Add it to the start of the output, advancing the pointer.
    sub edx, 2      # Subtract 2 from EDX. (= # of unfilled places - 1)
    ja repeat       # Jump back if it is still positive.
    jnz end         # Jump if it is -1 (all places filled: happens for even length).
    bsf eax, ecx    # Set EAX to the index of the 1 bit in ECX.
                    # (If the input is valid, there is at most one 1 bit here.)
    jnz skip        # Jump if there was a 1 bit in ECX.
    lodsb           # (Otherwise, the final instance of the odd-count character
                    #  is at the end of the string and has not yet been read.)
                    # Load a byte from the string into AL, advancing the pointer.
skip:
    or al, 0x60     # Set bits 5 and 6 in AL, making the correct lowercase letter.
    stosb           # Add it to the output (in the centre), advancing the pointer.
end:
    ret             # Return.
```
[Answer]
# [JavaScript (SpiderMonkey)](https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/Releases/45), 55 bytes
```
g=a=>a+''==a.reverse()?a:g(a.sort(_=>Math.random()<.5))
```
[Try it online!](https://tio.run/##bYzBCsIwEETvfkYvTRD35kVM/QK/QESWNI3VZDdkY8Gvr3u3M8Mc5sG8cEHxdS7tIGUeQ81M7/Bdo9OgG3Df984h1LCEKsHYC56iQRCuzTzccMX2hIo0cjb2DEdr18mJG6K5AYDcLbx4JtP3dueZhFOAxNFMpiMklM7@7Z51@DTNBsTCDRtvkIxUEpLX11S0Mqq27pWNavJB6foD "JavaScript (SpiderMonkey) – Try It Online")
Shuffle until meet requirement
[Answer]
# [Scala](http://www.scala-lang.org/), 58 bytes
Golfed version. [Try it online!](https://tio.run/##TU9Na8MwDL3nV4icEhj@AQEHdt/HIfQ0RtEctfMWy57tdhmjvz2T0w5iWWBJT@89J4MTLv7tg0yGR7QMv1V1xglCN@Ro@aj755Ct55dr@Qp62avsB/pSgaI7ZSzTpByGZq/c5xXWqoPlsZl1P2s9q0hnionaBWCkAzjRaTAeUwf3MeLPP3fbwY5tBi0mQE7x8e3jmKTzYFNuakbGVN9BbbzxfMpyS4XBiw@/DgQxSrChUpaFEiuKEbluV@qVdjUdxKuPhOb9pgpgMBEM3lETcJJ/RHm2oHsIYjNPvG1vV5480xZWl8ZN8FKVvFTLHw)
```
_.toSeq.permutations.map(_.mkString).find(x=>x==x.reverse)
```
Ungolfed version. [Try it online!](https://tio.run/##dVBNS8QwEL33Vww9tSABrwsVvPsFiycRGdPZbjSdlCS7Vpb97XWS7UoVJclhXt68eW@CRovT5F7fSEe4RcNwKAqAljYwkO93EaNxHKqwgnX0hrt6BTcmxKdT9QwNCB3AbKAKyhJ3cQtNA5d1plWhzt9kA0FQ0SVQLZVVj0P1ovr3WX7mfJtAa7j1rqeH/@zcDwn7bein@1ptRKYaobmCMfkblac9@UD1eVIv4Sv0nUhfe4@fZ0GZ8Mgmiu4hC@/RwofzbRAkRywZGUN5AaV22vEuyk0VDk7mu/whjFYOa0plakgnsxiRy9OWsmxeyN@xJYXzhHo7WwHQKHtdC23RUaeQg3iPlpfwsuXOMS1pZQJmF8civWMxTV8)
```
object Main {
  def permutations(s: String): List[String] = 
    if (s.length == 1) List(s)
    else s.toList.permutations.map(_.mkString).toList
  def palindromePermutations(s: String): Option[String] = 
    permutations(s).find(x => x == x.reverse)
  def main(args: Array[String]): Unit = {
    val words = List("nanas", "coconutnut", "apotato", "canadadance", "nananana", "anaan")
    words.map(palindromePermutations).foreach {
      case Some(palindrome) => println(palindrome)
      case None => println("None")
    }
  }
}
```
]