Liczba permutacji ciągów, które są palindromami

13

Twój tekst będzie ciągiem składającym się z małych angielskich liter.

Twoim zadaniem jest określenie liczby różnych kombinacji pierwotnego ciągu znaków, które są palindromem.

Ciąg wejściowy ma do 100 liter. W przypadku dłuższego ciągu wynik może być bardzo duży, więc wynikiem powinna być liczba permutacji modulo 666013.

Na przykład,

cababaa -> 3

Możliwe kombinacje to:

aabcbaa
abacaba
baacaab

To jest , więc wygrywa najkrótsza odpowiedź!

Andrei Mihailescu
źródło
2
„Biorąc pod uwagę, że ciąg ma do 100 cyfr, wynik musi wynosić% 666013.” Jeśli tak, dobrym pomysłem byłoby dołączenie odpowiedniego przypadku testowego.
Martin Ender
4
Nie rozumiem linii% 666013. Jest to jednak obiecujące wyzwanie i chętnie zagłosuję za ponownym otwarciem, gdy zostanie to wyjaśnione.
12
Och, teraz to zostało zredagowane. Widzę, do czego zmierzasz. Nie sądzę, aby ta linia stanowiła wyzwanie; przeważnie po prostu karze języki bez liczb całkowitych o dowolnej precyzji. Zwykle robimy coś takiego: „odpowiedź powinna być poprawna, jeśli działa w hipotetycznej wersji twojego języka z nieograniczonymi liczbami całkowitymi”.
7
To mogłoby naprawdę wykorzystać więcej przypadków testowych.
smls
3
Sugestie dotyczące przypadków testowych (proszę je jednak zweryfikować): abcdabcddddd -> 120 (brak liczby nieparzystych znaków) , abcdabcdddddd -> 120 (liczba nieparzystych znaków) , abcdabcddddddeee -> 0 (liczba dwóch nieparzystych znaków) , aabbccddeeffgghhiijj -> 298735 (wpływ modulo) .
smls

Odpowiedzi:

5

Brachylog (2), 15 bajtów

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

Wypróbuj online!

Wyjaśnienie

{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

źródło
2
Zdecydowanie muszę wdrożyć to „znajdowanie wyjątkowego” ...
Fatalize
2
@ Fatalizacja: Tak! Myślę, że nawet „liczenie unikatowe” zdarza się wystarczająco często w wyzwaniach, aby być może wart 1-bajtowej reprezentacji. Z drugiej strony „modulo 666013” prawie na pewno nie ;-)
5

05AB1E , 17 16 13 bajtów

-1 bajt od Jonathona Allana

-3 bajty od Emigny i Adnana

œÙvyÂQO•E›j•%

Wyjaśnienie:

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

Wypróbuj online!

Okx
źródło
1
Zawartość E›jreprezentuje cyfry [14, 116, 45]przekonwertowane z bazy 214i staje się 14*214^2 + 116*214 + 45 = 666013. Nie jestem do końca pewien, gdzie znajdują się odniesienia do cyfr, ale wydaje się, że są one zgodne (ich?) Z ich kolejnością na stronie informacyjnej . @Adnan może nas oświecić.
Jonathan Allan
1
@Emigna Łatwo, gdy znasz język: D
Jonathan Allan
1
Możesz zaoszczędzić 2 bajty usuwając instrukcję if, ponieważ i tak masz tylko potrzebne wartości na stosie:œÙvyÂQ}O•E›j•%
Emigna
2
@JonathanAllan Pełny zakres cyfr (i znaków) można znaleźć tutaj :).
Adnan
1
Opierając się na @ komentarzu Emigna, można zapisać kolejny bajt usuwając wspornik zamykający: œÙvyÂQO•E›j•%.
Adnan
4

Perl 6 , 104 108 88 84 bajtów

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

Wypróbuj online!

Jak to działa

Nie mogę z łatwością generować wszystkich permutacji i filtrować ich, nawet jeśli dozwolone są astronomiczne czasy działania, ponieważ wbudowana permutationsrutynowa procedura Perla 6 odmawia permutacji list zawierających więcej niż 20 elementów, a opis zadania wymaga danych wejściowych do 100 postacie.

Zamiast tego używam bezpośredniej formuły opartej na częstotliwościach liter wejściowych:

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

    Funkcja pomocnicza, która zmniejsza liczbę o połowę i zaokrągla ją do najbliższej liczby całkowitej, a następnie przyjmuje silnię tego.

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

    Zsumuj częstotliwości liter w ciągu wejściowym i uczyń je tematem pozostałej części kodu. Np. Dla danych wejściowych abcdabcddddddbędzie to lista (2, 2, 2, 7).

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

    Jeśli występuje więcej niż jedna częstotliwość nieparzystej litery, pomnóż wynik przez zero, ponieważ w takim przypadku nie są możliwe palindromy.

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

    Oblicz liczbę możliwych kombinacji znaków, które będą po „jednej stronie” każdego palindromu (co odpowiada wielokrotności z wielokrotnościami uzyskanymi przez zmniejszenie o połowę i wyrównanie częstotliwości liter wejściowych) . Zastosowana formuła pochodzi z tego pliku PDF :
    (n 1 + ... + n k )! / (n 1 ! ⋅ ... ⋅n k 1)
    Np. dla częstotliwości liter wejściowych (2,2,2,7)litery po jednej stronie palindromu tworzą zbiór wielokrotny z mnożnikami (1,1,1,3), a zatem liczba permutacji jest taka (1+1+1+3)! / (1!⋅1!⋅1!⋅3!) = 120.

  5. % 666013

    Weź wynik modulo 666013.

smls
źródło
Dobrze, że moja alternatywna metoda jest poprawna!
Jonathan Allan
3

Python3, 81 80 bajtów

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

To najkrótszy, jaki mogłem wymyślić. Nie jestem pewien, czy permutacje można łatwiej wygenerować ...

Wyjaśnienie

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.

Notatki

  1. Kontrola a==a[::-1]zwraca wartość logiczną, ale sum(...)funkcja domyślnie rzuca ją na liczbę całkowitą (0 lub 1) i odpowiednio sumuje.
  2. Muszę użyć „ operatora ikony ” (nie prawdziwej nazwy), aby wyodrębnić elementy z obiektu permutations(...). W przeciwnym razie set ( {...}) zawierałby tylko jeden element, sam obiekt.
  3. Używam set ( {...}), aby zachować w środku tylko wyraźne kombinacje.

W Floroid jest to (prawie) z(T(a==aDKaIW(cb(L)))%666013), ale zamiast tego wypisuje wynik i pobiera dane z wiersza poleceń.

Dzięki @Jonathan Allan za uratowanie bajtu! -> Zmieniłem importstyl

Wypróbuj online!

Yytsi
źródło
3

Galaretka , 13 bajtów

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

Wypróbuj online!

W jaki sposób?

Brutalny 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 wierzę , że to zrobi to sprawniej, ale to 30 bajtów (edit: to pdf wydaje się to potwierdzać, dzięki uprzejmości odpowiedzi SML koszulka ):

Ñ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.
Jonathan Allan
źródło
Tak to robi, to %jest mod.
Jonathan Allan
Gah, właśnie miałem opublikować dokładnie tę odpowiedź, ale nie dotarłem na czas, ponieważ najpierw opublikowałem odpowiedź Brachylog. Myślę, że to kwestia sekundy. Oczywiście muszę pamiętać, że Jelly jest bardziej popularnym językiem niż Brachylog, więc najpierw powinienem popracować nad tym przesłaniem.
Wow, bajt po bajcie? Mam też kolejne 13, ale myślę, że to nieco mniej wydajne :)
Jonathan Allan
Czy liczba jest skompresowana w innej bazie czy co? : P
Yytsi
Z mojej karcie tio Œ!QŒḂ€S%“µɲ€’. To wygląda tak samo jak ja.
2

Mathematica, 46 bajtów

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

Pobiera na wejściu listę znaków.

Strasznie nieefektywny, ponieważ faktycznie generuje wszystkie permutacje danych wejściowych, a następnie liczy palindromiczne.

Martin Ender
źródło
Myślę, że to niepoprawnie daje pozytywną odpowiedź, a nie 0, jeśli ciąg ma wiele liter występujących z nieparzystą wielokrotnością (jak "abcdabcddddddeee").
Greg Martin
@GregMartin Dzięki, naprawiono. To i tak było niepotrzebnie skomplikowane.
Martin Ender
2

Mathematica, 68 bajtów

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

Czysta funkcja pobierająca listę znaków jako dane wejściowe i zwracająca liczbę całkowitą. Nie tak krótki, jak odpowiedź Mathematica Martina Endera , ale mimo to jest to urocze podejście, które wydaje się takie samo, jak w odpowiedzi na perl 6 smls .

Najpierw t=Last/@Tally@#/2oblicza liczbę wszystkich różnych znaków na wejściu, podzieloną przez 2; następnie i=Floorzaokrągla wszystkie ułamki występujące w t. Zauważ, że palindromiczne permutacje danych wejściowych istnieją dokładnie wtedy, gdy wśród pierwotnych zliczeń występuje co najwyżej jedna liczba nieparzysta, to znaczy, gdy występuje co najwyżej jedna część t. Możemy to sprawdzić, po prostu dodając wszystkie elementy t-i(używając Tr): jeśli odpowiedź jest mniejsza niż 1, istnieją kombinacje palindromiczne, w przeciwnym razie nie.

Jeśli tak, ioznacza liczbę różnych znaków w lewej połowie permutacji, które można dowolnie ustawić. Liczba sposobów, aby to zrobić, to dokładnie Multinomialwspółczynnik (iloraz niektórych silni), który ma wbudowana Mathematica.

Greg Martin
źródło
1

k, 23 bajty

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

Jeśli używasz OK lub cmbnie istnieje, użyj prmzamiast cmb.

zgrep
źródło
1

C ++ 14, 161 bajtów

Ponieważ nienazwana lambda zakłada, że ​​dane wejściowe są podobne std::stringi zwracane przez parametr referencyjny.

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

Niegolfowane i użytkowanie:

#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;
}
Karl Napf
źródło
1

Ruby, 67 57 52 59 znaków

->s{s.chars.permutation.uniq.count{|t|t.reverse==t}%666013}
dorycki
źródło
Zgłoszenia do Codegolfa powinny być odpowiednimi programami / funkcjami / lambdami, a nie fragmentami . Nie jestem programistą Ruby, ale myślę, że możesz to zmienić w lambda, pakując go ->s{ }, prawda?
smls
Ponadto, czy na podstawie dokumentacji(s.size) argument nie jest zbędny?
smls
1
Przetestowałem go na Ruby 2.4 i działa bez niego .to_a.
smls
@smls Nie działa na Ruby 2.3.3 ( undefined method uniq 'dla # <Enumerator`), ale dobrze działa na Ruby 2.4, dzięki :)
Dorian
Czy trzeba wziąć wynik mod 666013?
NielinioweOwoc
1

Japt , 20 18 bajtów

á f_¥Zw} l %666013

Zaoszczędzono 2 bajty dzięki produktom ETH.

Wypróbuj online!

Tomek
źródło
Fajnie, tak bym zrobił. Możesz zapisać dwa bajty f_¥Zw}, jak _to jestZ{Z
ETHproductions
á fêS â l %666013zaoszczędzi ci bajt.
powelles
0

MATL, 13 bajtów

Y@Xu!"@tP=Avs

Wypróbuj w MATL Online

Wyjaśnienie

        % 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
Suever
źródło
0

CJam , 19 bajtów

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

Wypróbuj online!

Wyjaśnienie:

qe! {_ W% =}%: + 666013% e # Pełny program.
qe # Zbierz wszystkie dane wejściowe.
 mi! e # Uzyskaj wszystkie unikalne permutacje.
   {_W% =} e # Funkcja sprawdzająca, czy lista jest palindromem.
    _ e # Duplikat ToS.
     W% e # Odwróć ToS (Push -1, Modułowy indeks ToS).
       = e # Sprawdź, czy ToS jest równe SToS.
         Mapa% e #.
          : + e # Sum (Zmniejsz przez dodanie).
            666013 e # Push 666013.
                  % e # Modulo.

Erik the Outgolfer
źródło
0

Ohm, 17 bajtów

I⌐:_₧?¡;;¼,

Wyjaśnienie:

I⌐:_₧?¡;;¼,  ■Main wire
I⌐:     ;    ■for _ in permutations(input()){
   _₧? ;     ■  if(palindrome(_)){
      ¡      ■    counter++;
       ;     ■  }
        ;    ■}
         ¼,  ■print(counter)
Roman Gräf
źródło
0

PHP, 182 bajtów

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

Wersja online

Awaria

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);
Jörg Hülsermann
źródło