Liste mit Palindromen erzeugen?

[Guest]

Ich würde gerne eine Liste aller Zahlen bis 1000000,die Palindrome sind, erzeugen.(Also Zahlen die von vorne oder hinten gelesen den gleichen Wert darstellen).

Mein naiver Ansatz:

	public void createList(){
		ArrayList<Integer> list = new ArrayList<Integer>();
		for(int i=0;i<1000000;i++){
			if(isPalindrome(i)){
				list.add(i);
			}
		}
	}
	
	public boolean isPalindrome(int num) {
		String digits = String.valueOf(num);
		int numDigits = digits.length();

		for (int i=0; i<numDigits/2; i++) {
			if (digits.charAt(i) != digits.charAt(numDigits - i - 1))
				return false;
		}
		return true;
	}

Das schlechte an dieser Methode ist das Umwandeln in einen String, das enorm Performance kostet. Bei kleinen Zahlen kein Problem aber ab einer bestimmten Menge und Größe der Zahlen dauert das.

Kann man einer Zahl nicht irgendwie anders "ansehen" ob sie ein Palindrom ist? Oder lässt sich das berechnen ob eine Zahl ein Palindrom ist?

Freue mich auf euere Anregungen!

 

[0x7F800000]

nein, den test auf palindrom-eigenschaft kannst du nicht wesentlich beschleunigen, es wird am ende auf ziemlich dasselbe rauskommen.

Du kannst dir allerdings sehr viel zeit sparen, wenn du direkt nur die zahlen erzeugst, die palindrome sind.
_1_
_2_
.
.
.
_9_
11
101
111
121
131
...
181
191
22
202
212
222
232
...
292
...
...
...
1001
10001
10101
10201
10301
10401
...

d.h. Du zählst einfach los: 1,2,3,4,5,6,7,8,9,10,11,12,13,14...
drehst die zifferndarstellung jeweils um: 1,2,3,4,5,6,7,8,9,01,11,21,31,41...
und für jedes solches paar hängst du alle zeichen ' ','1','2','3','4',...,'9' dazwischen: 11,111,121,131,141,151...191,22,212,222... usw.

dann kriegst du wirklich nur genau das was du brauchst, und musst nicht zigtausend überflüssige zahlen testen.

 

[SlaterB]

gib Palindrom in die Forum-Suche ein, dann findest du manch ähnlichen Thread,

allgemeiner Tipp um die String-Erzeugung zu umgehen:
verwende ein int[] der Länge 7, fülle dies mathematisch korrekt mit
0 0 0 0 0 0 1
0 0 0 0 0 0 2
0 0 0 0 0 0 3
...
0 0 0 0 0 0 8
0 0 0 0 0 0 9
0 0 0 0 0 1 0
0 0 0 0 0 1 1
...

und prüfe jeweils nur noch Länge + Elemente des Arrays

 

[0x7F800000]

http://www.java-forum.org/de/viewtopic.php?t=76180
da variieren die lösungen von total abgefahren bis extrem trivial.

 

[Guest]

nein, den test auf palindrom-eigenschaft kannst du nicht wesentlich beschleunigen, es wird am ende auf ziemlich dasselbe rauskommen.

Du kannst dir allerdings sehr viel zeit sparen, wenn du direkt nur die zahlen erzeugst, die palindrome sind.
_1_
_2_
.
.
.
_9_
11
101
111
121
131
...
181
191
22
202
212
222
232
...
292
...
...
...
1001
10001
10101
10201
10301
10401
...


dann kriegst du wirklich nur genau das was du brauchst, und musst nicht zigtausend überflüssige zahlen testen.

Genau sowas suche ich! Schon beim Erzeugen nur Palindrome erzeugen.
Nur wie erzeugt man so ein Muster in Java?
Gehts das mit Patterns?

Wäre für einen Tip sehr dankbar!

 

[0x7F800000]

Nur wie erzeugt man so ein Muster in Java?

was für "patterns"? Ne, mir fällt spontan nichts ein, wie man das problem auf irgendetwas bereits gelöstes zurückführen sollte, das musst du so wie ich in prosa in meinem beitrag beschrieben hab "per hand erledigen", d.h. mit ganz primitiven mitteln: ein paar verschachtelten for-schleifen.

 

[Gast]

Ich dachte vielleicht hiermit:
http://java.sun.com/j2se/1.4.2/docs/api/java/util/regex/Pattern.html

 

[Schandro]

schnell hingehackt:

import java.util.*;
import java.io.*;

public class Palindrome{

	public static void main(String[] args){

		ArrayList <String> palindrome = new ArrayList <String> ();
		int maxZiffern = 5;

		for(int ziffern=1;ziffern<=halbierenUndRunden(maxZiffern);++ziffern){

			for(int i=(int)Math.pow(10,ziffern-1);i<Math.pow(10,ziffern);++i){
				palindrome.add(i+""+umdrehen(i+"",true));
			}
			if(ziffern != halbierenUndRunden(maxZiffern) || maxZiffern%2==0){
				for(int i=(int)Math.pow(10,ziffern-1);i<Math.pow(10,ziffern);++i){
					palindrome.add(i+""+umdrehen(i+"",false));
				}
			}
		}

		for(int i=0;i<palindrome.size();++i){
			System.out.println(palindrome.get(i));
		}
	}

	public static String umdrehen(String s, boolean letzteZifferAbschneiden){
		if(letzteZifferAbschneiden){
			s = s.substring(0,s.length()-1);
		}

		StringBuilder result = new StringBuilder();
		char[] c = s.toCharArray();
		for(int i=c.length-1;i>=0;--i){
			result.append(c[i]);
		}
		return result.toString();
	}

	public static int halbierenUndRunden(int i){
		if(i%2 == 0){return i/2;}
		else{return (i/2)+1;}
	}

}

 

[Landei]

Ich hätte ja gerne geholfen, aber ich leide unter Eibohphobie :-D

 

[0x7F800000]

Ich hätte ja gerne geholfen, aber ich leide unter Eibohphobie :-D

Das ist alles ein Scherz, oder soll es wirklich mal in der Geschichte der Menschheit jemanden gegeben haben, der da rumgesessen hat, und überprüft hat, ob er angst vor einer Zeichenkette haben soll?

 

[Landei]

Der Begriff war tatsächlich als Scherz gedacht, aber es scheint in seltenen Fällen wirklich Leute zu geben, die sich von Palindromen fürchten, weil sie diese irgendwie als "schlechtes Omen sehen" - also so in etwa wie Menschen, die vor der Zahl 13 Angst haben.