Permutapalindromic numbers

Question

Given an integer N as input, output the Nth permutapalindromic number.

A permutapalindromic number is a strictly positive integer such that there is at least one permutation of its digits that results in a palindrome (i.e. a number that is its own reverse).

For example, 117 is a permutapalindromic number since its digits can be permuted into 171, which is a palindrome.

We consider that numbers like 10 are not permutapalindromic numbers, even though 01 = 1 is a palindrome. We impose that the palindromic permutation must not have a leading zero (as such, 0 itself is not permutapalindromic).

Numbers that are already palindromes are also permutapalindromic, since permuting nothing is valid.

Inputs and outputs

• N may be either 0-indexed or 1-indexed. Please indicate which of the two your answer uses.
• The input can be taken through STDIN, as a function argument, or anything similar in your language of choice. The output can be written to STDOUT, returned from a function, or anything similar in your language of choice.
• The input and output must be in the decimal base.

Test cases

The following test cases are 1-indexed. Your program must be able to pass any of the test cases presented here in at most 1 minute.

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

Scoring

This is code-golf, so the shortest answer in bytes wins.

Answer 1

05AB1E, 15 14 13 bytes

Saved a byte thanks to Emigna! Code:

µNœvyJÂïÊP}_½

Explanation:

µ               # 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.

Uses the CP-1252 encoding. Try it online!.

Answer 2

Brachylog, 19 bytes

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

Try it online!

Takes about 17 seconds for N = 270.

Explanation

• Main predicate:

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

• Predicate 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
  

Answer 3

Brachylog, 21 20 bytes

1 byte thanks to Fatalize.

Did you design the challenge for Brachylog?

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

Try it online!

270 takes about half a minute here.

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

Exit code:     0

Predicate 0 (main predicate)

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

Predicate 1 (auxiliary predicate)

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.

Answer 4

JavaScript (ES6), 99 bytes

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

Explanation:

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!

Answer 5

Pyth, 14

e.ff&_ITshT.p`

Try it here or run a Test Suite

Expansion:

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

Answer 6

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
}

Essentially -- a function checking membership in permutapalindromic set, and a while loop incrementing until it finds the nth member.

Answer 7

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]

Simple enough. Basically uses a while loop to repeatedly create arrays containing permutapalindromic numbers the the range [1,Q) until Q is large enough such that the array contains Input number of items. It then outputs the last element in that array.

Try It Online! (Ideone)

Answer 8

Dyalog APL, 51 bytes

One-indexed.

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

{ a function where ⍵ represents the argument

⍵⊃{ use the argument to pick from the result of the function

⍵/⍨{ filter the argument with the result of the function

(⍵≤9)∨ the argument is less or equal to 9, OR

(1<≢c~'0')∧ there remains more than one digit when zeros are removed AND

1≥+/ 0 or 1 is the sum of

2| the oddnesses of

+⌿ of the column sums of

c∘.=∪c the comparison table of c and the unique elements of c, where c...

←⍕⍵ is the string representation of the argument

}¨⍵ applied to each of the arguments

}⍳5×⍵ applied to {1, 2, 3, ..., 5 times the argument}

} [end of function]

Finishes all the test cases instantly on TryAPL

Answer 9

Perl 6, 66 bytes

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

0 based

Explanation:

# 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
  )[$_]
}

Test:

#! /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";

Answer 10

JavaScript (ES6), 92

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

Less golfed

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

Test

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>

Answer 11

Javascript (using external library - 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 to lib:https://github.com/mvegh1/Enumerable/

Code explanation: _.Sequence creates an enumerable for a count of "n" elements, based on the predicate of signature ("i"teration,"a"ccumulated array). Cast the current iteration to a string, and create an enumerable of all permutations from it. Test if any of the permutations satisfy the test of not starting with "0" and that the reversal of the permutation equals the permutation. Return the last element in the sequence because that is the desired output as per OP

Answer 12

Haskell, 89 87 bytes

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

Answer 13

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-indexed. Depending on your system, the last test case may exceed the allowed recursion depth.

Does not compute permutations. Instead, uses the fact that two strings are permutations if they are equal when sorted. To test if a number is permutapalindromic, checks if its sorted digits equal the sorted digits of any palindrome up to a bound.

---

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-indexed. Depending on your system, the last test case may exceed the allowed recursion depth.

This doesn't look at permutations and instead uses the following characterization:

A number is permutapalindromic exactly when

• At most one of its digits appears an odd number of times, and
• It does not have the form d00...00 with one or more zeroes.

This is true because a palindrome must pair off digits from the start and end, except for a possible center digit. The exception comes from the requirement that the leading digit be nonzero, and so some nonzero digit must appear twice unless the number is single-digit.

Answer 14

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