Rearrange to a palindrome

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
nananana -> nanaanan
anaan -> anana

• Related: Unsort an array
– tsh
Commented Jul 25, 2022 at 3:20
• Suggested test case(s): Any string with an even length, e.g., nanana. Commented Jul 25, 2022 at 4:44
• Suggested test case: nnaaa (a case where the odd-count element has a count greater than 1). Commented Jul 25, 2022 at 5:18

Brachylog, 3 bytes

p.↔


Try it online!

Explanation

p.         The output is a permutation of the input
.↔        The output reversed is itself


J, 21 bytes

(,~,/@/:2|1#.e.)@/:~


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.
• For those porting this to other langs, reduction by "add the next char and then reverse" or "reverse and then add next char" works equally well. Commented Jul 26, 2022 at 1:40

Python 3, 72 bytes

*r,=s={''}
for c in input():s^={c};r+={c}-s
print(*r,*s,*r[::-1],sep="")


Try it online!

Saved 2 bytes by pxeger and xnor. It could be 66 bytes as xnor pointed out if output as list of characters.

It is $$\O(n)\$$.

• Boring 1 byte save in Python 3.9+: ato.pxeger.com/… Commented Jul 25, 2022 at 10:02
• – xnor
Commented Jul 25, 2022 at 23:51
• If you're OK printing a list of characters, something like this is shorter
– xnor
Commented Jul 25, 2022 at 23:52

05AB1E, 4 bytes

œʒÂQ


Try it online!

Explanation

œ          all permutations of the (implicit) input
ʒ          only keep those such that
Â         push x, reversed(x)
Q         they are equal


Python, 67 bytes

lambda x:(s:=sorted(x,key=lambda e:(x.count(e)%2,e)))[1::2]+s[::-2]

Attempt This Online!

Port of Jonah's excellent J solution.

JavaScript (Node.js), 69 bytes

a=>[...p=a.filter(c=>!(a[c]^=1)),...a.filter(c=>a[c]),...p.reverse()]


Try it online!

JavaScript (Node.js), 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!

Input / Output as strings.

• 69
– l4m2
Commented Jul 5, 2023 at 1:41

C (gcc), 124108 107 bytes

16 bytes saved thanks to 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! 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);
}

• @c-- Thank you! I'll apply the first version, but I'll need to look at the second version a bit more in depth. Commented Jul 25, 2022 at 21:13
• @c-- I think it looks good, I'll post an update with an explanation justifying it Commented Jul 26, 2022 at 5:00
• the initialization of j to 0 isn't a problem, because the loop iterates through the range [0..n], what I was talking about is the fact that i goes one character past the end of the string, which is not always \0 because after calling f() recursively at least once, the character after the string may match *c, which would set j = n, swapping it with c[n-1], what I'm trying to say is that it's broken for a string such as aaaabb or aaabb, sorry for the inconvenience
– c--
Commented Jul 26, 2022 at 15:09
• @c-- Good catch, I'll revert with that in mind Commented Jul 27, 2022 at 17:12

Python, 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!

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, 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!

A little shorter, but runs in $$\ O(n^2) \$$ time.

lin, 19 bytes

perm".+ rev ="?


Try it here!

For testing purposes (use -i flag if running locally):

"nanas" ; _
perm".+ rev ="?


Explanation

Prettified code:

perm (.+ rev = ) ?

• perm permutations
• (...) ? find first...
• .+ rev = palindrome

Curry (PAKCS), 41 bytes

f a@([]?[_])=a
f(a:b++a:c)=a:f(b++c)++[a]


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!.

Vyxal, 4 bytes

Ṗ'Ṙ=


Try it Online! Outputs all possibilities with duplicates. Add ;U to remove them. Takes permutations and only keeps those that are equal after reversal.

Prolog (SWI), 35 bytes

X+P:-permutation(P,X),reverse(P,P).


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! 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!

• And Brachylog's even more perfect lol Commented Sep 2, 2022 at 22:50

Ruby, 41 bytes

->a{a.permutation.select{_1==_1.reverse}}

Attempt This Online!

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.

Wolfram Language (Mathematica), 33 bytes

Select[PalindromeQ]@*Permutations


Try it online!

-1 byte thanks to att

• Select[PalindromeQ]@*Permutations
– att
Commented Jul 26, 2022 at 2:12

Alice, 19 bytes

/@P?w$.R/ \IO>K.-!\  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  Nekomata, 4 bytes ↕:↔=  Attempt This Online! A port of @Fatalize's Brachylog answer. ↕:↔= ↕ Permutation : Duplicate ↔ Reverse = Check equality  Returns all solutions with duplicates. You can add the -1 flag to print only the first solution. 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! 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  • This is also 63 bytes: f=(s,S=s.replace(/(.)(.*)\1|$/,'$2'),q=RegExp.$1)=>q?q+f(S)+q:s
– tsh
Commented Jul 26, 2022 at 1:51

$_=join"",sort@F;s/(.)\1/!push@r,$1/ge;say@r,$_,reverse@r  Try it online! Haskell, 52 bytes import Data.List find(\x->x==reverse x).permutations  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. • Pointfree: \x->x==reverse x -> (==)<*>reverse. Commented Aug 3, 2022 at 2:38 APL (Dyalog Classic), 19 bytes {⌊/⍵=⌽⍵:⍵⋄∇⍵[?⍨≢⍵]}  Try it online! Usage:  palindrome←{⌊/⍵=⌽⍵:⍵⋄∇⍵[?⍨≢⍵]} palindrome 'baba' baab palindrome 'daabbcc' cbadabc  Factor + math.combinatorics, 41 38 bytes [ [ dup reverse = ] find-permutation ]  Try it online! Japt, 5 bytes Outputs all possibilities. Replace f with æ to output just 1. á fêQ  Try it J-uby, 27 bytes Port of Kirill L.’s Ruby answer. :permutation|:select+:==%:~  Attempt This Online! Retina, 35 bytes O. |""L^((.)\2)*.?$
$^$
(.).
$1  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.

Charcoal, 24 bytes

≔Φθ﹪№…θκι²ηηΦΦθ﹪№θι²¬κ⮌η


Try it online! Link is to verbose version of code. Explanation:

≔Φθ﹪№…θκι²ηη


Using my code from Generate an arbitrary half of a string, 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.

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!

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".

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.


JavaScript (SpiderMonkey), 55 bytes

g=a=>a+''==a.reverse()?a:g(a.sort(_=>Math.random()<.5))


Try it online!

Shuffle until meet requirement

Scala, 58 bytes

Golfed version. Try it online!

_.toSeq.permutations.map(_.mkString).find(x=>x==x.reverse)


Ungolfed version. Try it online!

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 = {
`