Prüfen ob Ziffern einer Zahl pandigital sind?

[Großvater]

Hallo ihr,

ich würde gerne große Zahlen(BigIntegers) prüfen ob die ersten 9 Ziffern (ohne die 0) pandigital sind. Pandigitale Zahlen enthalten alle Ziffern von 1-9 (eigentlich 0-9), aber nicht unbedingt in der richtigen Reihenfolge. Bsp: 123456789, 987654321, 561234789

Angenommen ich habe jetzt eine große Zahl (BigInteger) wie z.B. die hier:

43466557686937456435642996440906533187938298969649928516003704476137795166849228875

Wie könnte ich möglichst effizient (schnell) prüfen, ob die ersten 9 Ziffern pandigital sind?

Hier meine Lösung (die aber viieeeel zu langsam ist):

public static boolean ispandigital(BigInteger x){
	String s = x.toString();
	if(s.length()<18){
		return false;
	}
	else{
		ArrayList<String> list = new ArrayList();
		for(int i=0;i<9;i++){
			String temp = s.substring(i,i+1);
			list.add(temp);
		}
		if(list.contains("1") && list.contains("2") && list.contains("3") && list.contains("4") && list.contains("5") && list.contains("6") && list.contains("7") && list.contains("8") && list.contains("9")){
			System.out.println("zahl gefunden: "+s);
			return true;
		}
		else{
			return false;
		}
	}
}

Das muss doch besser gehen!

 

[The_S]

Evtl. ist die Überprüfung der Quersumme schneller. Frag mich jetzt aber nicht, wie du am effektivsten von einem BigInteger auf die Quersumme der ersten neun Ziffern kommst

 

[SlaterB]

wenn du bei String bleibst, dann arbeite wenigstens mit charAt(i)-48, dann hast du 0-9
und dann in ein boolean[] nachschauen, wenn eine Zahl schon vorhanden ist false,
ansonsten (9x nicht false) muss es geklappt haben,

toString() sieht im Code aber recht aufwendig aus,
vielleicht hilft es, mit shiftRight(n) die Zahl auf die Länge eines int oder long zu kürzen,
oder die toByteArray()-Operation ausprobieren,

wäre beides aber mit aufwendigeren Berechnungen verbunden,
und ob das schneller oder langsamer ist, wäre auch noch zu testen

 

[Guest]

Wie könnte ich möglichst effizient (schnell) prüfen, ob die ersten 9 Ziffern pandigital sind?

Du kannst in einer int-Variable für jede Ziffer ein Bit reservieren und dann bei jeder eingelesenen Ziffer das entsprechende Bit setzen. Am Ende prüfst Du dann einfach, ob die 9 richtigen Bits gesetzt sind:

public static boolean ispandigital(BigInteger x)
{
	String string = x.abs().toString();
	int ziffern = 0;
	for (int i = 0, sup = Math.min(string.length(), 9); i < sup; ++i)
		ziffern |= 1 << (string.charAt(i) - '0');
	
	return ziffern == 1022;
}

Fred

 

[moormaster]

Kann man nicht einfach den String Zeichen für zeichen durchwandern?:

//Skizze
checksum = 0

für jedes Zeichen c aus dem String:
{
  n = Integer.parseInt(c);  // Ziffer bestimmen
  checksum |= (int)Math.pow(2, n) // n-tes Bit von checksum setzen
                                                  // das geht sicher noch effizienter, als wirklich mit Math.pow zu arbeiten
                                                  // z.B. könnte man sich statt dessen ein Array mit den entsprechenden
                                                  // 2er Potenzen zurechtlegen und dann nur die Elemente daraus abfragen
}

// Wenn nun alle Ziffern von 0-9 enthalten waren, dann gilt
// checksum & (2^10-1) == (2^10-1)

// Analog gilt:
// checksum & (2^10-1 - 1) == (2^10-1 - 1)
// wenn Ziffern 1-9 enthalten waren

//d.h. pandigital für 0-9
return checksum & (2^10-1) == (2^10-1);

//ODER pandigital für 1-9
return checksum & (2^10-1 - 1) == (2^10-1 - 1)

 

[SlaterB]

also charAt ist auf jeden Fall besser als Integer.parseInt, bzw. aus dem char musst du nicht mehr parsen, einfach -48,
für das Math.pow hat ja jemand zeitgleich das Shift vorgeschlagen

die (Quer-) Summe reicht aber wohl aus und ist dann noch besser als das Shiften?
letzlich egal, solange nur substring wegfällt (oder gar Integer.parseInt)

 

[Guest]

die (Quer-) Summe reicht aber wohl aus und ist dann noch besser als das Shiften?

Ich glaube nicht, dass die Quersumme ausreicht. Sonst würde 111159999 auch als pandigital anerkannt werden, oder?

Fred

 

[SlaterB]

Mist, stimmt

 

[moormaster]

also charAt ist auf jeden Fall besser als Integer.parseInt, bzw. aus dem char musst du nicht mehr parsen, einfach -48,
für das Math.pow hat ja jemand zeitgleich das Shift vorgeschlagen

die (Quer-) Summe reicht aber wohl aus und ist dann noch besser als das Shiften?
letzlich egal, solange nur substring wegfällt (oder gar Integer.parseInt)

Mit der Quersumme wäre ich aber vorsichtig... Wenn ich nur schaue, ob die ersten 9 Ziffern summiert == 9*10/2 (-> 45) sind, dann wäre auch
997654320... pandigital, weil 9+9+7+6+5+4+3+2+0 == 45

Man muss also sicherstellen können, dass eine Ziffer nicht doppelt gezählt werden, was bei einer ODER-Verknüpfung der Fall wäre

*Mist schonwieder zu langsam... das kommt davon, wenn man abgelenkt wird beim Schreiben... *

 

[Guest]

toString() sieht im Code aber recht aufwendig aus,

Das könnte tatsächlich der eigentliche Flaschenhals sein.

Was machst Du denn so mit den Zahlen, bevor Du sie auf Pandigitalität überprüfst? Wird da viel gerechnet, oder werden die vielleicht einfach nur aus einer Textdatei gelesen? Dann würde es Sinn machen, sie gleich ausschließlich als Strings zu behandeln.

Schreib doch mal den Code auf, der ispandigital benutzt.

Fred

 

[Guest]

Die toString()-Methode IST der Flaschenhals:

public static boolean ispandigital(BigInteger x)
{
	Benchmark bm = new Benchmark();
	bm.start();
	String string = x.abs().toString();
	bm.stop("toString");

	bm.start();
	int ziffern = 0;
	for (int i = 0, sup = Math.min(string.length(), 9); i < sup; ++i)
		ziffern |= 1 << (string.charAt(i) - '0');
	bm.stop("Ziffern");

	bm.start();
	ArrayList<String> list = new ArrayList();
	for (int i = 0; i < 9; i++)
	{
		String temp = string.substring(i, i + 1);
		list.add(temp);
	}
	boolean ergebnis = list.contains("1") && list.contains("2") && list.contains("3")
			&& list.contains("4") && list.contains("5") && list.contains("6")
			&& list.contains("7") && list.contains("8") && list.contains("9");
	bm.stop("Liste");

	return ziffern == 1022;
}

Die letzten Messung lautet:
*** toString: 4740 ns
*** Ziffern: 450 ns
*** Liste: 2585 ns

toString() braucht ganz grob 10x so lange wie der optimierte Algorithmus. Obwohl die Ziffern-Version also 6x so schnell ist wie Listen-Version, ist die komplette Methode aufgrund der Laufzeit von toString() insgesamt nur 40% schneller geworden.

Fred

 

[moormaster]

Du musst es ja auch nicht als String behandeln... man kann doch Ganzzahlen auch per Modulo in ihre Ziffern zerlegen:

1432%10 = 2 -> 1432/10=143
143%10 = 3 -> 143/10 = 14
14%10 = 4 -> 14/10 = 1
1%10 = 1 -> 1 /10 = 0 -> halt

=> 1,4,3,2

Bezüglich BigInteger gibt es entsprechende Methoden, welche statt der "primitven" Operatoren verwendet werden können. Möglicherweise ist es bei besonders langen Ganzzahlen günstiger, den BigInteger stückweise in primitive int's zu verwandeln und diese dann nach obigem Schema zu zerlegen, wobei die Ergebnisse zum Schluss zusammengefügt werden.

 

[SlaterB]

tja, es ist aber gerade die Frage, wie man aus einem BigInteger die Ziffern rauskriegt,
eine 'Ganzzahl' hat man da nicht so leicht, toString() schon eher

edit:
> Bezüglich BigInteger gibt es entsprechende Methoden

oh, welche? außer du meinst, die ganze Zahl modulo zu rechnen

 

[moormaster]

tja, es ist aber gerade die Frage, wie man aus einem BigInteger die Ziffern rauskriegt,
eine 'Ganzzahl' hat man da nicht so leicht, toString() schon eher

BigInteger ist doch die Repräsentation einer Ganzzahl... nur eben leider nicht als primitiver Datentyp

edit:
> Bezüglich BigInteger gibt es entsprechende Methoden

oh, welche? außer du meinst, die ganze Zahl modulo zu rechnen

Genau das meinte ich... Die BigInteger-Klasse stellt Methoden zum Dividieren und zur Modulorechnung von Biginteger'n bereit, weil ja % und / nicht direkt darauf angewendet werden können. Da das wahrscheinlich auch eine längere Rechenzeit in Anspruch nimmt, als wenn man es mit primitiven Datentypen zu tun hätte, hab ich ja auch vorgeschlagen, den BigInteger nicht ziffernweise zu zerlegen, sondern erstmal Gruppenweise...

BigInt mod 10^gruppenlaenge = letzte Gruppe -> BigInt div 10^gruppenlaenge (letzte Gruppe entfernen)
usw.

die Gruppen könnte man dann per intValue zu int wandeln und dann diese Gruppen mit % und / in Ziffern zerlegen.

 

[NTB]

Wenn man gegen richtig viele Zahlen prüft, kann es durchaus Sinn machen, die Quersumme erstmal zu berechnen. Wenn die Quersumme 45 ist, dann eben weiter untersuchen.
Das wäre zwar an sich bischen länger, aber man schließt Zahlen viel schneller aus.

 

[moormaster]

Wenn man gegen richtig viele Zahlen prüft, kann es durchaus Sinn machen, die Quersumme erstmal zu berechnen. Wenn die Quersumme 45 ist, dann eben weiter untersuchen.
Das wäre zwar an sich bischen länger, aber man schließt Zahlen viel schneller aus.

Ich bezweifle, dass eine Addition so viel schneller ist, als eine simple Bitoperation... auch für die Quersumme muss man schliesslich erstmal an die einzelnen Ziffern kommen (was, wie ich denke, der aufwendigste Teil der Sache ist).