How to generate a list of palindromes without checking

Question

I am working on a problem when I need to manipulate large lists of palindromes up to a certain number of digits. This should work with numbers up to 15 digits. The most common method I've seen for this is to repeat each number and check if each is a palindrome and then add it to the list. This is my java implementation and it works great.

public class Palindrome { public ArrayList<Long> List = new ArrayList<Long>(); public double d; public Palindrome(double digits) { this.d = digits; long dig = (int)(Math.pow(10,digits)); for (long i = 1; i <= dig; i++) { long a = i; long b = inverse(a); if (a == b) { List.add(a); } } public long inverse(long x){ long inv = 0; while (x > 0) { inv = inv * 10 + x % 10; x = x / 10; } return inv; } } 

Only the problem is pretty slow when I get 10 digit palindromes. I am considering alternative ways of creating this list, and one consideration I had was to generate a list of palindromes, rather than repeating each number and checking its palindrome.

I am still working on paper, but the picture is not as obvious as I thought I would find to turn it into a pseudo-code. I'm working on the fact that for n the number of digits going from i to n, if the number of digits is even, generate numbers from 1 to [10 ^ (i / 2 + 1) - 1]. Then add the reverse of each number to yourself. A bit stuck on how to do this for odd numbers. That's where I am now.

I will come back with my own answer if I consider this and implement the code, but in the meantime I would just like to know if anyone has done this before or has an alternative method that I have missed, which will be more efficient.

UPDATE

So I managed to come up with something, thanks to all your suggestions. I decided to work with numbers as strings, but contrary to what I intended, it actually increased the execution time: /

 public class Palindrome2 { public ArrayList<Long> List = new ArrayList<Long>(); public double d; public Palindrome2(double digits) { this.d = digits; for (long n = 1; n <= d; n++) { if (n == 1) { for (long i = 1; i < 10; i++) { List.add(i); } } if (n % 2 != 0 && n != 1) { long max = (long) Math.pow(10, (n + 1) / 2); long min = (long) Math.pow(10, Math.floor(n / 2)); for (long i = min; i < max; i++) { String str = Long.toString(i); str = str + removeFirst(reverse(str)); Long x = Long.parseLong(str); List.add(x); } } else if (n % 2 == 0) { long max = (long) (Math.pow(10, Math.floor((n + 1) / 2)) - 1); long min = (long) Math.pow(10, (n / 2) - 1); for (long i = min; i <= max; i++) { String str = Long.toString(i); str = str + reverse(str); Long x = Long.parseLong(str); List.add(x); } } } } public String reverse(String x) { String rev = new StringBuffer(x).reverse().toString(); return rev; } public String removeFirst(String x) { return x.substring(1); } 

}

Once again, accurate, but still slow :(

Answer 1

Introduction

You need to analyze the regular template for the algorithm until approximately the transition to development, which will save a lot of time, for example:

 each 1 digit is 1 palindrome, eg: 1 each 2 digits has 1 palindrome, eg: 11. each 3 digits has 10 palindromes, eg: 101,111,...,191. each 4 digits has 10 palindromes, eg: 1001, 1111, ..., 1991. each 5 digits has 100 palindromes, eg: 10001, 11011, ..., 19091, ..., 19991. each 6 digits has 100 palindromes, eg: 100001, 110011, ..., 190091, ..., 199991. each 7 digits has 1000 palindromes, eg: 1000001, ...,1900091,...,1090901, ..., 1999991. each 8 digits has 1000 palindromes, eg: 10000001, ...,19000091,...,10900901, ..., 19999991. .... 

then you can write a layout algorithm to implement this.

Implementation

But I can tell you that this implementation can be optimized in the same way as if you used the cache to save palindromes created using palindromes(2) digits, then any high palindromes(n>2) digits palindromes(n>2) can reuse it.

It may not be reliable, but it passes all my tests to github . I left the rest of the work and optimization for you, and I would like you to do it yourself.

 private static List<Integer> palindromes(int digits) { return palindromes(digits, 0); } private static List<Integer> palindromes(int digits, int shifts) { List<Integer> result = new ArrayList<>(); int radix = (int) Math.pow(10, digits - 1); int renaming = digits - 2; boolean hasRenaming = renaming > 0; for (int i = start(digits, shifts); i <= 9; i++) { int high = i * radix; int low = low(digits, i); if (hasRenaming) { for (Integer m : palindromes(renaming, shifts + 1)) { int ret = high + m * 10 + low; if (ret < 0) { return result; } result.add(ret); } } else { result.add(high + low); } } return result; } private static int low(int digits, int high) { return digits > 1 ? high : 0; } private static int start(int digits, int shifts) { return digits > 1 && shifts == 0 ? 1 : 0; } 

Using

then you can collect all the palindrome numbers as shown below:

  // v--- min:0, max: 2147447412, count: 121474 List<Integer> all = IntStream.rangeClosed(1, 10) .mapToObj(PalindromeTest::palindromes) .flatMap(List::stream) .collect(Collectors.toList()); 

Cost of time:

191ms

Enable Caching

 public class Palindromes { private static final int[] startingNonZerosTable = { 0,// 0 0, 1,// 1 2 10, 10,//3 4 100, 100, //5 6 1000, 1000,//7 8 10000, 10000,// 9 10 100000, 100000,//11 12 1000000, 1000000,//13 14 10000000, 10000000,//15 16 100000000, 100000000,//17 18 1000000000, 1000000000//19 20 }; private static final int MAX_DIGIT = 9; private static final int MIN_DIGIT = 0; private static final int RADIX = MAX_DIGIT - MIN_DIGIT + 1; private static final int LONG_MAX_DIGITS = 19; private static volatile long[][] cache = new long[LONG_MAX_DIGITS + 1][]; // includes palindromes(0) ---^ static { cache[0] = new long[0]; cache[1] = new long[]{0L, 1L, 2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L}; cache[2] = new long[]{0L, 11L, 22L, 33L, 44L, 55L, 66L, 77L, 88L, 99L}; } public static LongStream since1(int end) { return between(1, end); } public static LongStream between(int start, int end) { return IntStream.rangeClosed(start, end) .mapToObj(Palindromes::of) .flatMapToLong(identity()); } public static LongStream of(int digits) { return Arrays.stream(palindromes0(digits)) .skip(startingNonZerosTable[digits]); } private final static long[] palindromes0(int digits) { if (cache[digits] != null) { return cache[digits]; } long[] result = new long[sizeOf(digits)]; int size = 0; long high = (long) Math.pow(RADIX, digits - 1); for (int i = MIN_DIGIT; i <= MAX_DIGIT; i++) { for (long mid : palindromes0(digits - 2)) { long value = i * high + mid * RADIX + i; if (value < 0) {//overflow return cache[digits] = Arrays.copyOf(result, size); } result[size++] = value; } } return cache[digits] = result; } private static int sizeOf(int digits) { return MAX_DIGIT * (int) Math.pow(RADIX, (digits - 1) >>> 1) + startingNonZerosTable[digits]; } // v--- java -Xms1024m -Xmx2048m test.algorithm.Palindromes public static void main(String[] args) { Duration duration = timing(() -> { // palindromes[1..15] ---v LongSummaryStatistics result = since1(15).summaryStatistics(); long max = result.getMax(); long count = result.getCount(); System.out.printf("Max: %d, Count: %d%n", max, count); }); System.out.printf("Time Elapsed:%s%n", duration); // ^--- time elapsed: 4s } private static Duration timing(Runnable task) { long starts = System.currentTimeMillis(); task.run(); return Duration.ofMillis(System.currentTimeMillis() - starts); } } 

Cost of time:

palindromes [1..15] elapsed time: 4 s

Answer 2

Have you tried working with symbols, not numbers? You can generate the palindrome as a string of numbers, and then convert to a number at the end. Something like this pseudo code:

 generatePalindrome(size) half <- size DIV 2 // Integer division result <- "" result.append(randomDigitIn(1..9)) // No leading zeros. while (result.length <= half) result.append(randomDigitIn(0..9)) endwhile if (size is odd) result <- result + randomDigitIn(0..9) + result.reverse() else result <- result + result.reverse() endif return number.parse(result) end generatePalindrome() 

In principle, you randomly generate a half of the palindrome, avoiding leading zeros, insert an additional digit in the middle for odd lengths, add the inverse first half, and then parse the digital string into the desired format.

Answer 3

For an odd number, you can simply reuse the palindromes generated in the previous even step, divide them in half and insert in the middle all possible number from 0 to 9.

Let's say you need to generate a 3-digit palindrome, just get all 2-digit palindromes and add the whole number from 0 to 9.

We have 22, than we can generate:

• 202
• 212
• 222
• 232
• etc.

I hope my idea is clear :)

Answer 4

Try something like this:

 public class Palindrome { public static ArrayList<Long> calculatePalindromes(int maxLength) { ArrayList<Long> result = new ArrayList<>(); if (maxLength <= 0) { return result; } long maxPart = (long)Math.pow(10, maxLength / 2); for (long i = 0; i < 10; ++i) { result.add(i); } for (long i = 1; i < maxPart; ++i) { long curHalf = i; long curNum = i; int curLen = 0; while (curHalf != 0) { curNum *= 10; curNum += curHalf % 10; curHalf /= 10; ++curLen; } result.add(curNum); // insert numbers from 0 to 9 if (curLen * 2 + 1 > maxLength) { continue; } for (int j = 0; j < 10; ++j) { curHalf = i; curNum = i; curNum *= 10; curNum += j; while (curHalf != 0) { curNum *= 10; curNum += curHalf % 10; curHalf /= 10; } result.add(curNum); } } return result; } } 

The idea is to insert numbers from 0 to 9 after each X and add reversed(X) after it so that we get X (1..9) reversed(X) .

Answer 5

You can generate all the palindromes in the desired range without checking, but you are likely to run out of memory, as keeping all these numbesr for the top number 15 in the length of the list is a bad idea.

More specifically, your code will look like this:

  long dig = (long) Math.pow(10, digits / 2); int pow = 10; int npow = 100; for (long i = 1; i <= dig; i++) { System.out.println(i * pow + inverse(i)); System.out.println(i * pow / 10 + inverse(i / 10)); // list.add(i * pow + inverse(i)); // list.add(i * pow/10 + inverse(i / 10)); if (i % pow == 0) { pow = npow; npow *= 10; } } 

I intentionally commented on the list adding lines.

The idea is to insert into the list / output all numbers composed with a given half, like:

 XXXY+YXXX 

and

 XXX+Y+XXX 

i.e. generating both cases: odd and even palindromes.