Ihre Eingabe wird eine Zeichenfolge sein, die aus kleinen englischen Buchstaben besteht.

Ihre Aufgabe ist es, die Anzahl der unterschiedlichen Permutationen der ursprünglichen Zeichenfolge zu bestimmen, die ein Palindrom sind.

Die Eingabezeichenfolge enthält bis zu 100 Buchstaben. Bei einer längeren Zeichenfolge kann das Ergebnis sehr groß sein, daher sollte die Ausgabe die Anzahl der Permutationen modulo 666013 sein.

Beispielsweise,

cababaa -> 3

Die möglichen Permutationen sind:

aabcbaa
abacaba
baacaab

Das ist Code-Golf , also gewinnt die kürzeste Antwort!

Brachylog (2), 15 Bytes

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

Probieren Sie es online!

Erläuterung

{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

05AB1E , 17 16 13 Bytes

-1 Byte von Jonathon Allan

-3 Bytes von Emigna und Adnan

œÙvyÂQO•E›j•%

Erläuterung:

œÙ                # 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)

Probieren Sie es online!

Perl 6 , 104 108 88 84 Bytes

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

Probieren Sie es online!

Wie es funktioniert

Ich kann nicht einfach alle Permutationen generieren und filtern, auch wenn astronomische Laufzeiten zulässig sind, da die integrierte permutationsRoutine von Perl 6 es ablehnt, Listen mit mehr als 20 Elementen zu permutieren, und die Aufgabenbeschreibung Eingaben von bis zu 100 erfordert Zeichen.

Deshalb verwende ich stattdessen eine direkte Formel, die auf den Buchstabenhäufigkeiten der Eingabe basiert:

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

   Eine Hilfsfunktion, die eine Zahl halbiert und auf die nächste Ganzzahl abrundet und dann die Fakultät davon aufnimmt.

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

   Zählen Sie die Buchstabenhäufigkeiten in der Eingabezeichenfolge auf und machen Sie sie zum Thema für den Rest des Codes. ZB zur Eingabe abcdabcddddddwäre dies die Liste (2, 2, 2, 7).

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

   Wenn es mehr als eine ungerade Buchstabenfrequenz gibt, multiplizieren Sie das Ergebnis mit Null, da in diesem Fall keine Palindrome möglich sind.

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

   Berechnen Sie die Anzahl der möglichen Permutationen der Zeichen, die sich auf "einer Seite" jedes Palindroms befinden (was einem Multiset mit den Multiplizitäten entspricht, die durch Halbieren und Untermalen der Eingangsbuchstabenfrequenzen erhalten werden) . Die verwendete Formel stammt aus diesem PDF :
   (n ₁ + ... + n _k )! / (n ₁ ! ⋅ ... ⋅n _k 1)
   ZB für die Eingabe von Buchstabenfrequenzen (2,2,2,7)bilden die Buchstaben auf einer Seite des Palindroms ein Multiset mit Multiplizitäten (1,1,1,3), und die Anzahl der Permutationen ist somit (1+1+1+3)! / (1!⋅1!⋅1!⋅3!) = 120.

5. % 666013

   Nehmen Sie das Ergebnis modulo 666013.

Python3, 81 80 Bytes

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

Dies ist das kürzeste, was ich mir vorstellen konnte. Ich bin mir nicht sicher, ob die Permutationen einfacher generiert werden können ...

Erläuterung

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.

Anmerkungen

1. Die Prüfung a==a[::-1]gibt einen booleschen Wert zurück, der von der sum(...)Funktion jedoch implizit in eine Ganzzahl (0 oder 1) umgewandelt und entsprechend summiert wird.
2. Ich muss den ' splat-Operator ' (nicht den richtigen Namen) verwenden, um die Elemente aus dem Objekt zu extrahieren permutations(...). Andernfalls {...}würde set ( ) nur ein Element enthalten, das Objekt selbst.
3. Ich verwende ein set ( {...}), um nur bestimmte Permutationen in mir zu behalten.

In Floroid ist dies (fast) z(T(a==aDKaIW(cb(L)))%666013), gibt jedoch stattdessen das Ergebnis aus und nimmt Eingaben über die Befehlszeile entgegen.

Vielen Dank an Jonathan Allan für das Speichern eines Bytes! -> importStil geändert

Probieren Sie es online!

Gelee , 13 Bytes

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

Probieren Sie es online!

Wie?

Ein roher 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

Ich glaube, dass dies effizienter sein wird, aber es sind 30 Bytes (Bearbeiten: Dieses PDF scheint es zu bestätigen, dank der Antwort von smls ):

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

Mathematica, 46 Bytes

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

Nimmt eine Liste von Zeichen als Eingabe.

Schrecklich ineffizient, weil es tatsächlich alle Permutationen der Eingabe generiert und dann die palindromischen zählt.

Mathematica, 68 Bytes

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

Reine Funktion, die eine Liste von Zeichen als Eingabe verwendet und eine Ganzzahl zurückgibt. Nicht so kurz wie die Mathematica-Antwort von Martin Ender , aber es ist trotzdem eine nette Herangehensweise, die dieselbe Herangehensweise zu sein scheint wie in der Perl 6-Antwort von smls .

Zuerst t=Last/@Tally@#/2berechnet die Zählungen aller unterschiedlichen Zeichen in der Eingabe, dividiert durch 2; dann i=Floorabrundet irgendwelche Brüche in auftreten t. Beachten Sie, dass palindromische Permutationen der Eingabe genau dann vorliegen, wenn höchstens eine ungerade Zahl unter den ursprünglichen Zählwerten vorhanden ist, dh wenn höchstens ein Bruch in vorhanden ist t. Wir können das testen, indem wir einfach alle Elemente von t-i(using Tr) addieren : Wenn die Antwort kleiner als ist 1, gibt es palindromische Permutationen, andernfalls nicht.

Wenn ija , dann repräsentiert das die Anzahl der verschiedenen Zeichen in der linken Hälfte der Permutationen, die beliebig angeordnet werden können. Die Anzahl der Möglichkeiten, dies zu tun, ist genau der MultinomialKoeffizient (ein Quotient bestimmter Fakultäten), den Mathematica eingebaut hat.

k, 23 Bytes

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

Wenn Sie OK verwenden oder cmbnicht vorhanden sind, verwenden Sie prmanstelle von cmb.

Pyth - 15 Bytes

%l{_I#.pQ666013

Probieren Sie es hier online aus .

C ++ 14, 161 Bytes

Als unbenanntes Lambda wird angenommen, dass die Eingabe wie folgt ist std::stringund über den Referenzparameter zurückgegeben wird.

#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 und Nutzung:

#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;
}

Ruby, 67 57 52 59 Zeichen

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

Japt , 20 bis 18 Bytes

á f_¥Zw} l %666013

2 Bytes gespart dank ETHproductions.

Probieren Sie es online!

MATL, 13 Bytes

Y@Xu!"@tP=Avs

Probieren Sie es bei MATL Online aus

Erläuterung

        % 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

CJam , 19 Bytes

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

Probieren Sie es online!

Erläuterung:

qe! {_ W% =}%: + 666013% e # Volles Programm.
qe # Alle Eingaben abrufen.
 e! e # Holen Sie sich alle eindeutigen Permutationen.
   {_W% =} e # Funktion zum Überprüfen, ob eine Liste ein Palindrom ist.
    _ e # ToS duplizieren.
     W% e # ToS umkehren (Push -1, Modularer Index von ToS).
       = e # Überprüfe, ob ToS gleich SToS ist.
         % e # Map.
          : + e # Summe (durch Addition reduzieren).
            666013 e # Drücken Sie 666013.
                  % e # Modulo.

Ohm, 17 Bytes

I⌐:_₧?¡;;¼,

Erläuterung:

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

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

Nervenzusammenbruch

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);