Permutapalindromische Zahlen

18

Geben Sie bei einer Ganzzahl Nals Eingabe die Ndritte permutapalindromische Zahl aus.

Eine permutapalindromische Zahl ist eine streng positive ganze Zahl, sodass mindestens eine Permutation ihrer Ziffern ein Palindrom ergibt (dh eine Zahl, die ihre eigene Umkehrung darstellt).

Zum Beispiel 117ist es eine permutapalindromische Zahl, da ihre Ziffern permutiert werden können 171, was ein Palindrom ist.

Wir 10denken, dass Zahlen wie keine permutapalindromischen Zahlen sind, obwohl sie 01 = 1ein Palindrom sind. Wir setzen 0voraus , dass die palindromische Permutation keine führende Null haben darf (als solche ist sie selbst nicht permutapalindromisch).

Zahlen, die bereits Palindrome sind, sind auch permutapalindrom, da das Permutieren von nichts gültig ist.

Eingänge und Ausgänge

  • Nkann entweder 0-indiziert oder 1-indiziert sein. Bitte geben Sie an, welche der beiden Antworten Ihre Antwort verwendet.
  • Die Eingabe kann STDINals Funktionsargument oder in einer ähnlichen Sprache erfolgen. Die Ausgabe kann in STDOUTeine Funktion oder in eine ähnliche Sprache Ihrer Wahl geschrieben oder von dieser zurückgegeben werden.
  • Die Eingabe und Ausgabe muss in der Dezimalbasis erfolgen.

Testfälle

Die folgenden Testfälle sind 1-indiziert. Ihr Programm muss in der Lage sein, alle hier vorgestellten Testfälle in maximal 1 Minute zu bestehen.

N      Output

1      1
2      2
3      3
4      4
5      5
6      6
7      7
8      8
9      9
10     11
42     181
100    404
128    511
256    994
270    1166

Wertung

Das ist , also gewinnt die kürzeste Antwort in Bytes.

Tödlich
quelle
Es ist ganz unmöglich, nicht den letzten Testfall in einer Minute passieren ...
Leaky Nonne
OEIS A084050 (enthält zusätzliche Fälle wie 10)
Undichte Nonne
Was ist der größte Input?
Adám
@Adám Dein Programm sollte theoretisch für jede Zahl funktionieren, egal wie groß.
Fatalize
1
@ Adám Dies ist eine ziemlich willkürliche Grenze, die von der verwendeten Sprache abhängt. Angenommen, es sollte theoretisch für die größte Ganzzahl funktionieren, die Ihre Sprache standardmäßig darstellen kann (also für alle Ganzzahlen, wenn Bignums die Standardeinstellung in Ihrer Sprache ist).
Fatalize

Antworten:

8

05AB1E , 15 14 13 Bytes

Dank Emigna ein Byte gespart ! Code:

µNœvyJÂïÊP}_½

Erläuterung:

µ               # c = 0, when c is equal to the input, print N.
 N              # Push N, the iteration variable.
  œ             # Push all permutations of N.
   vyJ    }     # For each permutation...
      Â         #   Bifurcate, which is short for duplicate and reverse.
       ï        #   Convert the seconds one to int, removing leading zeros.
        Q       #   Check if they are not equal.
         P      #   Product of the stack.
           _    # Logical not.
            ½   # Pop a value, if 1 then increase c by 1.

Verwendet die CP-1252- Codierung. Probieren Sie es online! .

Adnan
quelle
1
µNœvyJÂïQ}O__½für 14.
Emigna
@Emigna Danke! Daran habe ich nicht gedacht.
Adnan
7

Brachylog, 19 Bytes

~l<:1at.
.=pPrPl~l?

Probieren Sie es online!

Dauert etwa 17 Sekunden N = 270.

Erläuterung

  • Hauptprädikat:

    ~l            Create a list whose length is Input.
      <           The list is strictly increasing.
       :1a        Apply predicate 1 to each element of the list.
          t.      Output is the last element of the list.
    
  • Prädikat 1:

    .=            Input = Output = an integer
      pPrP        A permutation P of the Output is its own reverse
          l~l?    The length of P is equal to the length of the Input
    
Tödlich
quelle
5

Brachylog , 21 20 Bytes

1 Byte dank Fatalize.

Haben Sie die Herausforderung für Brachylog entworfen?

:1yt.
0<.={@epcPrP!}

Probieren Sie es online!

270 dauert hier etwa eine halbe Minute.

Z = 1166
real    0m27.066s
user    0m26.983s
sys     0m0.030s

Exit code:     0

Prädikat 0 (Hauptprädikat)

:1yt.
:1y    find the first Input solutions to predicate 1
   t.  unify the output with the last element

Prädikat 1 (Hilfsprädikat)

0<.={@epcPrP!}
0<.              0 < Output
  .=             Assign a value to Output (choice point)
    {        }   Inline predicate:
     @e              Digits of the Output
       p             A permutation (choice point)
        c            Concatenate (fails if leading zero present)
         P           store as P
          rP         assert that P reversed is still P
            !        remove the choice point in this predicate, so
                     that it will not return twice for the same number.
Undichte Nonne
quelle
5

Pyth, 14

e.ff&_ITshT.p`

Probieren Sie es hier aus oder führen Sie eine Test Suite aus

Erweiterung:

e.ff&_ITshT.p`ZQ   # Auto-fill variables
 .f            Q   # Find the first input number of numbers that give truthy on ...
           .p`Z    # Take all the permutations of the current number
   f&              # Keep those that give a truthy value for both:
     _IT           # Invariance on reversing (is a palindrome)
        shT        # The integer value of the first digit (doesn't start with zero)
                   # A list with any values in it it truthy, so if any permutation matches
                   # these conditions, the number was a permutapalindrome
e                  # Take only the last number
FryAmTheEggman
quelle
5

JavaScript (ES6), 99 Byte

f=(n,i=1)=>(n-=/^.0+$/.test(i)</^((.),\2,)*(.)(,\3)?(,(.),\6)*$/.test([...i+''].sort()))?f(n,i+1):i

Erläuterung:

f=(n,i=1)=>             look for n numbers starting at 1
 (n-=                   test whether current guess is
  /^.0+$/.test(i)<      not a round number and
  /^((.),\2,)*          pairs of comma-separated digits
   (.)(,\3)?            possible single digit
   (,(.),\6)*$/         pairs of comma-separated digits
   .test(               matches the comma-joined
    [...i+''].sort()))  digits in ascending order
 ?f(n,i+1)              if not n numbers found try next number
 :i                     found it!
Neil
quelle
1100 ist eine runde permutapalindromische Zahl.
Adám
@ Adám Es ist nicht rund, es enthält mindestens zwei Ziffern ungleich Null.
Neil
@Neil: +2 Bytes - das sollten Sie wirklich zählen, f=wenn Sie später darauf verweisen
Charlie
@charlie Sorry, das vergesse ich immer.
Neil
4

R, 145 Bytes

g=function(n){d=b=0 
while(d<n){b=b+1
if(sum(a<-table(strsplit(n<-as.character(b),""))%%2)==nchar(n)%%2&(!names(a)[1]==0|a[1]|sum(!a)>1))d=d+1}
b}

ungolfed

f=function(b){
    a<-table(strsplit(n<-as.character(b),""))%%2
    sum(a)==nchar(n)%%2&(!names(a)[1]==0|a[1]|sum(!a)>1)
}
g=function(n){
    d=b=0
    while(d<n){
         b=b+a
         if(f(b)) d=d+1
    }
    b
}

Im Wesentlichen - eine Funktion, die die Zugehörigkeit zu einer permutapalindromischen Menge überprüft und eine while-Schleife, die inkrementiert, bis das n-te Mitglied gefunden wird.

user5957401
quelle
3

Python 2.7, 163 154 Bytes:

from itertools import*;I,F,Q=input(),[],2
while len(F)<I:F=[g for g in range(1,Q)if any(i==i[::-1]*(i[0]>'0')for i in permutations(`g`))];Q+=1
print F[-1]

Einfach genug. Grundsätzlich wird eine whileSchleife verwendet, um wiederholt Arrays zu erstellen, die permutapalindromische Zahlen enthalten. Der Bereich [1,Q)bis Qist so groß, dass das Array die InputAnzahl der Elemente enthält . Anschließend wird das letzte Element in diesem Array ausgegeben.

Probieren Sie es online! (Ideone)

R. Kap
quelle
2

Perl 6 , 66 Bytes

{(1..*).grep(*.comb.permutations.grep({+.join.flip eq.join}))[$_]}

0 basierend

Erläuterung:

# bare block lambda which takes an implicit parameter 「$_」
{
  # all numbers greater than 0
  (1..*)\

  # remove any which aren't permutapalindromic
  .grep(

    # 「*」 here starts a Whatever lambda
    *\
    # split into list of digits
    .comb\
    # get all of the permutations of the digits
    .permutations\
    # find out if there are any palindromes
    .grep(

      # another bare block lambda taking 「$_」 as implicit parameter
      {
        # compare the current permutation with its reverse stringwise
        # numify only one side to get rid of leading 「0」
        +$_.join.flip eq $_.join
      }
    )

  # get the value at the index
  )[$_]
}

Prüfung:

#! /usr/bin/env perl6
use v6.c;
use Test;

my &permutapalindromic = {(1..*).grep(*.comb.permutations.grep({+.join.flip eq.join}))[$_]}

my @tests = (
  1   => 1,
  2   => 2,
  3   => 3,
  4   => 4,
  5   => 5,
  6   => 6,
  7   => 7,
  8   => 8,
  9   => 9,
  10  => 11,
  42  => 181,
  100 => 404,
  128 => 511,
  256 => 994,
  270 => 1166,
);

plan +@tests + 1;

my $start-time = now;
for @tests -> $_ ( :key($input), :value($expected) ) {
  # zero based instead of one based, so subtract 1
  is-deeply permutapalindromic( $input - 1 ), $expected, .gist;
}
my $finish-time = now;

my $total-time = $finish-time - $start-time;

cmp-ok $total-time, &[<], 60, 'Less than 60 seconds for the tests';
diag "$total-time seconds";
Brad Gilbert b2gills
quelle
2

Dyalog APL , 51 Bytes

Einseitig indiziert.

{⍵⊃{⍵/⍨{(⍵≤9)∨(1<≢c~'0')∧1≥+/2|+⌿c∘.=∪c←⍕⍵}¨⍵}⍳5×⍵}

{ eine Funktion, bei der ⍵ das Argument darstellt

⍵⊃{ Verwenden Sie das Argument, um aus dem Ergebnis der Funktion auszuwählen

⍵/⍨{ Filtern Sie das Argument mit dem Ergebnis der Funktion

(⍵≤9)∨ Das Argument ist kleiner oder gleich 9, ODER

(1<≢c~'0')∧ Es bleibt mehr als eine Ziffer, wenn Nullen entfernt werden UND

1≥+/ 0 oder 1 ist die Summe von

2| die seltsamkeiten von

+⌿ der Spaltensummen von

c∘.=∪cdie Vergleichstabelle von c und die eindeutigen Elemente von c , wo c ...

←⍕⍵ ist die Zeichenfolgendarstellung des Arguments

}¨⍵ auf jedes der Argumente angewendet

}⍳5×⍵ angewendet auf {1, 2, 3, ..., 5 mal das Argument}

} [Ende der Funktion]

Beendet alle Testfälle sofort in TryAPL

Adam
quelle
Können Sie das beweisen a(n) <= 5n?
Undichte Nonne
Die zweite Lösung erzeugt falsche Ergebnisse.
Undichte Nonne
Die erste Lösung erzeugt auch falsche Ergebnisse.
Undichte Nonne
@LeakyNun Welche sind falsch? Und wenn 5 × nicht genug ist, gibt es Platz für 9 × ...
Adám
@LeakyNun Richtig, ich schließe 100 etc. ein, die nicht erlaubt sind.
Adám
2

JavaScript (ES6), 92

n=>eval("for(a=0;n-=(a++<9||(b=[...a+``].sort().join``)>9&!b.replace(/(.)\\1/g,``)[1]););a")

Weniger golfen

n=>{
  for( a = 0;
       n -= // decrement n (and exit when 0) if the check below is true == a is permutapalindromic
            (a ++ < 9 // single digit (meanwhile, increment a)
             || // or...
             ( b=[...a+``].sort().join`` )// build a string with the digits sorted
               > 9 // required at least 2 non zero digits
             & ! b.replace(/(.)\1/g,``)[1] // removed all digits pair, there must be just 1 or no single digits remaining
            );
     );
   return a;
}

Prüfung

f=n=>eval("for(a=0;n-=(a++<9||(b=[...a+``].sort().join``)>9&!b.replace(/(.)\\1/g,``)[1]););a")

function update() {
  O.textContent=f(+I.value)
}

update()
<input id=I oninput=update() type=number value=100>
<pre id=O></pre>

edc65
quelle
1

Javascript (mit externer Bibliothek - Enumerable) (142 Bytes)

   n=>_.Sequence(n,i=>{l=i+"";p=_.Permutations(_.From(l),l.length).Any(y=>y.First()!="0"&&y.SequenceEqual(y.Reverse()));if(p){return i;}}).Last()

Link zu lib: https://github.com/mvegh1/Enumerable/

Codeerklärung: _.Sequence erstellt eine Aufzählung für eine Anzahl von "n" Elementen, basierend auf dem Prädikat der Signatur ("i" -Teration , "ein" kumuliertes Array ). Wandeln Sie die aktuelle Iteration in eine Zeichenfolge um und erstellen Sie daraus eine Aufzählung aller Permutationen. Prüfen Sie, ob eine der Permutationen den Test erfüllt, nicht mit "0" zu beginnen, und ob die Umkehrung der Permutation der Permutation entspricht. Gibt das letzte Element in der Sequenz zurück, da dies der gewünschte Ausgang gemäß OP ist

Bildbeschreibung hier eingeben

applejacks01
quelle
1

Python 2, 93 Bytes

S=sorted
f=lambda n,i=1:n and-~f(n-(S(`i`)in[S(`k`)for k in range(9*i)if`k`==`k`[::-1]]),i+1)

1-indiziert. Abhängig von Ihrem System kann der letzte Testfall die zulässige Rekursionstiefe überschreiten.

Berechnet keine Permutationen. Verwendet stattdessen die Tatsache, dass zwei Zeichenfolgen Permutationen sind, wenn sie beim Sortieren gleich sind. Um zu testen, ob eine Zahl permutapalindrom ist, prüfen Sie, ob ihre sortierten Ziffern den sortierten Ziffern eines Palindroms bis zu einer Grenze entsprechen.


96 Bytes:

f=lambda n,i=1:n and-~f(n-(sum(`i`.count(`d`)%2for d in range(10))<2*(set(`i`[1:])!={'0'})),i+1)

1-indiziert. Abhängig von Ihrem System kann der letzte Testfall die zulässige Rekursionstiefe überschreiten.

Dies betrachtet keine Permutationen und verwendet stattdessen die folgende Charakterisierung:

Eine Zahl ist genau dann permutapalindromisch

  • Höchstens eine der Ziffern erscheint ungerade oft, und
  • Es hat nicht die Form d00 ... 00 mit einer oder mehreren Nullen.

Dies ist der Fall, weil ein Palindrom Ziffern vom Anfang bis zum Ende mit Ausnahme einer möglichen mittleren Ziffer koppeln muss. Die Ausnahme ergibt sich aus der Anforderung, dass die führende Ziffer ungleich Null ist. Daher muss eine Ziffer ungleich Null zweimal angezeigt werden, es sei denn, die Zahl ist einstellig.

xnor
quelle
1

Haskell, 89 87 Bytes

import Data.List
(filter(any(show.floor.read.reverse>>=(==)).permutations.show)[0..]!!)
Damien
quelle
0

C 254 Bytes

#define W while
#define R return
f(j){int c=0,a[16]={0};do++a[j%10],++c;W(j/=10);if(c>1&&a[0]>=c-1)R 0;c%=2;W(j<10)if(a[j++]%2&&(!c||++c>2))R 0;R 1;}g(n){int k=0,i=1;W(k<n)if(f(i++))++k;R i-1;}main(a){printf("N>");scanf("%d",&a);printf("%d\n",g(a));}
RosLuP
quelle