19
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ Related: Unsort an array \$\endgroup\$
    – tsh
    Jul 25 at 3:20
  • \$\begingroup\$ Suggested test case(s): Any string with an even length, e.g., nanana. \$\endgroup\$ Jul 25 at 4:44
  • \$\begingroup\$ Suggested test case: nnaaa (a case where the odd-count element has a count greater than 1). \$\endgroup\$
    – Jonah
    Jul 25 at 5:18

22 Answers 22

13
\$\begingroup\$

Brachylog, 3 bytes

p.↔

Try it online!

Also acts as a generator for all possible outputs.

Explanation

p.         The output is a permutation of the input
 .↔        The output reversed is itself
\$\endgroup\$
9
\$\begingroup\$

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.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Bubbler
    Jul 26 at 1:40
8
\$\begingroup\$

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)\$.

\$\endgroup\$
3
6
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

C (gcc), 124 108 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);
}
\$\endgroup\$
5
  • \$\begingroup\$ @c-- Thank you! I'll apply the first version, but I'll need to look at the second version a bit more in depth. \$\endgroup\$ Jul 25 at 21:13
  • \$\begingroup\$ that's probably for the best \$\endgroup\$
    – c--
    Jul 26 at 3:01
  • \$\begingroup\$ @c-- I think it looks good, I'll post an update with an explanation justifying it \$\endgroup\$ Jul 26 at 5:00
  • \$\begingroup\$ 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 \$\endgroup\$
    – c--
    Jul 26 at 15:09
  • \$\begingroup\$ @c-- Good catch, I'll revert with that in mind \$\endgroup\$ Jul 27 at 17:12
4
\$\begingroup\$

JavaScript (Node.js), 71 bytes

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

Try it online!

Input / Output as array of characters.


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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
0
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 33 bytes

Select[PalindromeQ]@*Permutations

Try it online!

-1 byte thanks to att

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Select[PalindromeQ]@*Permutations \$\endgroup\$
    – att
    Jul 26 at 2:12
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ This is also 63 bytes: f=(s,S=s.replace(/(.)(.*)\1|$/,'$2'),q=RegExp.$1)=>q?q+f(S)+q:s \$\endgroup\$
    – tsh
    Jul 26 at 1:51
1
\$\begingroup\$

Perl 5 -F , 57 bytes

$_=join"",sort@F;s/(.)\1/!push@r,$1/ge;say@r,$_,reverse@r

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Pointfree: \x->x==reverse x -> (==)<*>reverse. \$\endgroup\$
    – alephalpha
    Aug 3 at 2:38
1
\$\begingroup\$

APL (Dyalog Classic), 19 bytes

{⌊/⍵=⌽⍵:⍵⋄∇⍵[?⍨≢⍵]}

Try it online!

Usage:

      palindrome←{⌊/⍵=⌽⍵:⍵⋄∇⍵[?⍨≢⍵]}
      palindrome 'baba'
baab
      palindrome 'daabbcc'
cbadabc
New contributor
atpx8 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
1
\$\begingroup\$

Factor + math.combinatorics, 41 38 bytes

[ [ dup reverse = ] find-permutation ]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.