Number of string permutations that are palindromes

Question

Your input will be a string consisting of small english letters.

Your task is to determine the number of distinct permutations of the original string that are a palindrome.

The input string has up to 100 letters. In the case of a longer string the result might be very big so the output should be the number of permutations modulo 666013.

For example,

cababaa -> 3

The possible permutations are:

aabcbaa
abacaba
baacaab

This is code-golf, so the shortest answer wins!

Answer 1

Brachylog (2), 15 bytes

{p.↔}ᶠdl%₆₆₆₀₁₃

Try it online!

Explanation

{p.↔}ᶠdl%₆₆₆₀₁₃
{   }ᶠdl          Count (l) the number of distinct (d) results (ᶠ) obtainable by:
 p                  permuting {the input}
  .                 to produce an output
   ↔                that, if reversed, is still the output
        %₆₆₆₀₁₃   then take that number modulo 666013

Answer 2

05AB1E, 17 16 13 bytes

-1 byte from Jonathon Allan

-3 bytes from Emigna and Adnan

œÙvyÂQO•E›j•%

Explanation:

œÙ                # Unique permutations of [implicit] input
  vy              # For each permutation...
    ÂQ            # Check if it is a palindrome
      O           # If so, increment the counter
       •E›j•%     # Modulo 666013 (no clue why this number, or even why this rule is in place)

Try it online!

Answer 3

Perl 6, 104 108 88 84 bytes

{my &f={[*] 1..$_ div 2}
.comb.Bag{*}.&{(2>.grep(*%2))*f(.sum)/[*]($_».&f)%666013}}

Try it online!

How it works

I can't easily generate all permutations and filter them, even if astronomical run-times are allowed, because Perl 6's built-in permutations routine straight-out refuses to permute lists of more than 20 elements and the task description requires inputs of up to 100 characters.

So instead I use a direct formula based on the letter frequencies of the input:

1. my &f={[*] 1..$_ div 2}

   A helper function that halves a number and rounds it down to the nearest integer, and then takes the factorial of that.

2. .comb.Bag{*}.&{    };

   Tally up the letter frequencies in the input string, and make them the topic for the rest of the code. E.g. for input abcdabcdddddd this would be the list (2, 2, 2, 7).

3. (2>.grep(*%2))*

   If there is more than one odd letter frequency, multiply the result by zero, because no palindromes are possible in that case.

4. f(.sum)/[*]($_».&f)

   Calculate the number of possible permutations of the characters that will be on "one side" of each palindrome (which corresponds to a multiset with the multiplicities obtained by halving and flooring the input letter frequencies). The formula used is from this PDF:
   (n₁+...+ n_k)! / (n₁!⋅...⋅n_k1)
   E.g. for input letter frequencies (2,2,2,7), the letters on one side of the palindrome form a multiset with multiplicities (1,1,1,3), and the number of permutations is thus (1+1+1+3)! / (1!⋅1!⋅1!⋅3!) = 120.

5. %666013

   Take the result modulo 666013.

Answer 4

Python3, 81 80 bytes

from itertools import*
lambda s:sum(a==a[::-1]for a in{*permutations(s)})%666013

This is the shortest I could come up with. Not sure if the permutations can be generated more easily...

Explanation

lambda s:                       # Anonymous function taking a parameter <s>. 
    sum(                        # Sum the following terms.
        a==a[::-1]              # Check whether the permutation <a> is a palindrome,
        for a in                # for each element <a>,
        {                       # inside a set that can only contain distinct elements.
            *                   # Splat the elements of the following object:
            permutations(s)     # the permutations of the input parameter <s>.
        }                       #
    )%666013                    # Modulo the sum by 666013.

Notes

1. The check a==a[::-1] returns a boolean value, but the sum(...) function implicitly casts it to an integer (0 or 1) and sums accordingly.
2. I have to use the 'splat operator' (not the real name), to extract the elements from the object permutations(...). Otherwise the set ({...}) would contain only one element, the object itself.
3. I use a set ({...}) to keep only distinct permutations inside.

In Floroid, this is (almost) z(T(a==aDKaIW(cb(L)))%666013), but prints the result instead, and takes input through the command line.

Thanks to @Jonathan Allan for saving a byte! --> Changed the import style

Try it online!

Answer 5

Jelly, 13 bytes

Œ!QŒḂ€S%“µɲ€’

Try it online!

How?

A brute forcer.

Œ!QŒḂ€S%“µɲ€’ - Main link: string
Œ!            - all permutations
  Q           - unique
     €        - for each
   ŒḂ         - isPalindromic? (yep a built-in!)
      S       - sum
       %      - mod
        “µɲ€’ - base 250 compressed number 666013

---

I believe that this will do it more efficiently, but it's 30 bytes (edit: this pdf seems to confirm it, courtesy of smls's answer):

ÑHḞµS!÷!P$ - Link 1, palindrome count: string a    e.g. 'abcabcd'
Ñ          - call the next link (2) as a monad(a)  e.g. [2, 2, 2, 1]
 H         - halve                                 e.g. [1, 1, 1, 0.5]
  Ḟ        - floor (get pair counts)               e.g. [1, 1, 1, 0]
   µ       - start a new monadic chain - call that p
    S      - sum(p)                                e.g. 3
     !     - factorial                             e.g. 6
         $ - last 2 links as a monad:
       !   -     factorial(p) (vectorises)         e.g. [1, 1, 1, 1]
        P  -     product                           e.g. 1
      :    - integer division                      e.g. 6

ĠL€ - Link 2, count characters: string a           e.g. 'abcabcd'
Ġ   - group indexes                                e.g. [[1, 4], [2, 5], [3, 6], 7]
 L€ - length of €ach                               e.g. [2, 2, 2, 1]

ÇḂS⁼LḂ$aÑ%“µɲ€’ - Main link: string a              e.g. 'abcabcd'
                - first check to see if any palindromes will be possible:
Ç               - last link (2) as a monad         e.g. [2, 2, 2, 1]
 Ḃ              - mod 2                            e.g. [0, 0, 0, 1]
  S             - sum                              e.g. 1
      $         - last two links as a monad:
    L           -     length(a string)             e.g. 7
     Ḃ          -     mod 2                        e.g. 1
   ⁼            - equal?                           e.g. 1 (1 when palindromes are possible)
       a        - and
        Ñ       - next link as a monad             e.g. 6
         %“µɲ€’ - mod 666013, as in the brute force version.

Answer 6

Mathematica, 46 bytes

Permutations@#~Count~_?PalindromeQ~Mod~666013&

Takes a list of characters as input.

Terribly inefficient, because it actually generates all permutations of the input and then counts the palindromic ones.

Answer 7

Mathematica, 68 bytes

If[i=Floor[t=Last/@Tally@#/2];Tr[t-i]<1,Multinomial@@i,0]~Mod~666013

Pure function taking a list of characters as input and returning an integer. Not as short as Martin Ender's Mathematica answer, but it's a cute approach nonetheless, which seems to be the same approach as in smls's Perl 6 answer.

First, t=Last/@Tally@#/2 computes the counts of all the distinct characters in the input, divided by 2; then i=Floor rounds down any fractions occurring in t. Note that palindromic permutations of the input exist exactly when there is at most one odd number among the original counts, that is, when there is at most one fraction in t. We can test for that by simply adding up all the elements of t-i (using Tr): if the answer is less than 1, there are palindromic permutations, otherwise not.

If there are, then i represents the counts of distinct characters in the left half of the permutations, which can be arranged arbitrarily. The number of ways to do that is exactly the Multinomial coefficient (a quotient of certain factorials), which Mathematica has built-in.

Answer 8

k, 23 bytes

{666013!+/{x~|x}'cmb x}

If using oK, or cmb doesn't exist, use prm instead of cmb.

Answer 9

Pyth - 15 bytes

%l{_I#.pQ666013

Try it online here.

Answer 10

Ruby, 67 57 52 59 chars

->s{s.chars.permutation.uniq.count{|t|t.reverse==t}%666013}

Answer 11

Japt, 20 18 bytes

á f_¥Zw} l %666013

Saved 2 bytes thanks to ETHproductions.

Try it online!

Answer 12

C++14, 161 bytes

As unnamed lambda assuming input is like std::string and returning via reference parameter.

#import<algorithm>
[](auto s,int&n){auto a=s.begin(),b=s.end();std::sort(a,b);n=0;do n=(n+std::equal(a,b,s.rbegin()))%666013;while(std::next_permutation(a,b));}

Ungolfed and usage:

#include<iostream>
#include<string>

#import<algorithm>
auto f=
[](auto s,int&n){
 auto a=s.begin(),b=s.end();
 std::sort(a,b);
 n=0;
 do
  n=(n+std::equal(a,b,s.rbegin()))%666013;
 while(std::next_permutation(a,b));
}
;

using namespace std;


int main(){
 string s;
 s = "cababaa";
 s = "abcdabcddddd";
 int n;
 f(s,n);
 cout << n << endl;
}

Answer 13

MATL, 13 bytes

Y@Xu!"@tP=Avs

Try it at MATL Online

Explanation

        % Implicitly grab input as a string
Y@      % Compute all permutations of the inputs (one per row)
Xu      % Determine the unique rows
!       % Take the transpose so each permutation is a column
"       % For each unique permutation
  @     % Take this permutation
  tP=A  % Duplicate it, reverse it, and compare (yields 1 for palindrome and 0 otherwise)
  v     % Vertically concatenate the entire stack
  s     % Compute the sum of all elements
        % Implicitly end for loop and display the result

Answer 14

CJam, 19 bytes

qe!{_W%=}%:+666013%

Try it online!

Explanation:

qe!{_W%=}%:+666013% e# Full program.
q                   e# Get all input.
 e!                 e# Get all unique permutations.
   {_W%=}           e# Function to check if a list is a palindrome.
    _               e# Duplicate ToS.
     W%             e# Reverse ToS (Push -1, Modular index of ToS).
       =            e# Check if ToS is equal to SToS.
         %          e# Map.
          :+        e# Sum (Reduce by addition).
            666013  e# Push 666013.
                  % e# Modulo.

Answer 15

Ohm, 17 bytes

I⌐:_₧?¡;;¼,

Explanation:

I⌐:_₧?¡;;¼,  ■Main wire
I⌐:     ;    ■for _ in permutations(input()){
   _₧? ;     ■  if(palindrome(_)){
      ¡      ■    counter++;
       ;     ■  }
        ;    ■}
         ¼,  ■print(counter)

Answer 16

PHP, 182 Bytes

function f($a,$b=1){return$a?f($a-1,bcmul($a,$b)):$b;}$a=count_chars($argv[1],$r=1);foreach($a as$v){$c+=$v%2?:0;$c>1?die("0"):$z+=$f=$v/2^0;$r=bcmul(f($f),$r);}echo bcdiv(f($z),$r);

Online Version

Breakdown

function f($a,$b=1){  #Factorial
    return$a?f($a-1,bcmul($a,$b)):$b;
}
$a=count_chars($argv[1],$r=1); # Array count for every char
foreach($a as$v){
    $c+=$v%2?:0; # counter mod 2 ==1
    $c>1?die("0"):$z+=$f=$v/2^0; # end program if there are 2 chars which cannot divide by 2
    $r=bcmul(f($f),$r);
}
echo bcdiv(f($z),$r);