Ein Zahlenproblem

[iBot]

Danke für die vielen Antworten so früh

@justin:
Ich kann leider kein Java, aber hab ich das richtig verstanden? Du meinst es gäbe einen Befehl mit dem man das direkt machen kann?

@Manf:
ich versteh den Gedanken jetzt nicht 100%ig, kannst du das vlt in eine kleine Basic-Schleife verpacken?

@radbruch:
Ah ja, stimmt, das würde die erforderlichen Möglichkeiten noch einmal halbieren…
Sprich: Es wären nur noch 181440 möglichkeiten

[Manf]

Man kann auch von der anderen Seite kommen und das System in der Anzahl der Stellen aufstocken. Für nur eine Ziffer heißt die Liste der Zahlen :1.

Eine weitere Ziffer ergänzt man indem man sie für jede bisherige Kombination dahinter, in jeden Zwischenraum und davor stellt, also 12; 21.

Dann ergänzt man die 12 mit 3 zu 123; 132; 312; und man ergänzt die 21 mit 3 zu 213; 231; 321.

Damit ergibt sich für die n-te Ergänzung einer Ziffer eine Vervielfachung der Kombinationen um n. Damit sind es n! Kombinationen.

Ich bin mal gespannt, welche Lösung der vorgesehenen Auflösung in diesem Quiz entspricht.

[radbruch]

Ein Ansatz in Bascom mit 4 Ziffern aus "0" -"9" ergeben 5040 Kombinationen:

' Zahlenproblem                                                                 29.7.2011 mic

' https://www.roboternetz.de/community/showthread.php?54210-Ein-Zahlenproblem

$regfile = "m8def.dat"                                      ' asuro mit Mega8
$crystal = 8000000                                          ' taktet mit 8MHz
$baud = 2400                                                ' IR-Baudrate


Dim Muster(10) As Byte
Dim N(10) As Byte , M As Byte
Dim Gefunden As Byte,
Dim Nr As Long

Print "{027}[1;1H";                                         ' Home
Print "{027}[2J";                                           ' clear terminal screen
Print "{027}[1m";                                           ' bold on
Print "Zahlenproblem                                  29.7.2011 mic"
Print "{027}[0m";                                           ' Attribute off
Print

Nr = 1
For N(1) = 0 To 9                                           ' erste Ziffer festlegen
    Muster(1) = N(1)

    'If N(1) = 1 Then N(1) = 8                               ' Abkürzung!

    For N(2) = 0 To 9

      If Muster(1) <> N(2) Then                             ' wenn zweite Ziffer ungleich
         Muster(2) = N(2)                                   ' zweite Ziffer festlegen

         For N(3) = 0 To 9                                  ' dritte Ziffer mit den anderen Ziffern vergleichen
             Gefunden = 0                                   ' ab hier könnte man das auch rekrusiv lösen
             For M = 1 To 2                                 ' aber so scheint es mir übersichtlicher
                 If Muster(m) = N(3) Then Gefunden = 1
             Next M
             If Gefunden = 0 Then
                Muster(3) = N(3)

                For N(4) = 0 To 9                           ' n. Ziffer
                  Gefunden = 0
                  For M = 1 To 3                            ' Stellen 1 bis n-1 überprüfen
                      If Muster(m) = N(4) Then Gefunden = 1
                  Next M
                  If Gefunden = 0 Then                      ' wenn schon vorhanden, Ziffer überspringen
                     Muster(4) = N(4)                       ' letzte Ziffer komplett

                     Print Nr ; " - " ; Muster(1) ; Muster(2) ; Muster(3) ; Muster(4)
                     Incr Nr

                  End If
                Next N(4)
             End If
         Next N(3)
      End If
    Next N(2)
Next N(1)

Decr Nr
Print
Print "Erzeugte Kombinationen: " ;
Print Nr

Do
Loop
End                                                         'end program

[Edit]
Weil ich ja schon fast am Ziel war habe ich mein Programm auf 10 Ziffern aufgebohrt:

' Zahlenproblem                                                                 29.7.2011 mic

' https://www.roboternetz.de/community/showthread.php?54210-Ein-Zahlenproblem

$regfile = "m8def.dat"                                      ' asuro mit Mega8
$crystal = 8000000                                          ' taktet mit 8MHz
$baud = 2400                                                ' IR-Baudrate


Config Pind.5 = Output                                      'speaker

Dim Muster(10) As Byte
Dim N(10) As Byte , M As Byte
Dim Gefunden As Byte,
Dim Nr As Long

Print "{027}[1;1H";                                         ' Home
Print "{027}[2J";                                           ' clear terminal screen
Print "{027}[1m";                                           ' bold on
Print "Zahlenproblem                                  29.7.2011 mic"
Print "{027}[0m";                                           ' Attribute off
Print

For Nr = 0 To 4000
   Toggle Portd.5
   Waitus 250
Next Nr

Nr = 1
For N(1) = 0 To 9                                           ' erste Ziffer festlegen
    Print "1: " ; N(1)
    Muster(1) = N(1)

    'If N(1) = 1 Then N(1) = 8                               ' Abkürzung!

    For N(2) = 0 To 9
      Print "2: " ; N(2)

      If Muster(1) <> N(2) Then                             ' wenn zweite Ziffer ungleich
         Muster(2) = N(2)                                   ' zweite Ziffer festlegen

         For N(3) = 0 To 9                                  ' dritte Ziffer mit den anderen Ziffern vergleichen
            Print "3: " ; N(3)
            Gefunden = 0                                    ' ab hier könnte man das auch rekrusiv lösen
            For M = 1 To 2                                  ' aber so scheint es mir übersichtlicher
               If Muster(m) = N(3) Then Gefunden = 1
            Next M
            If Gefunden = 0 Then
                Muster(3) = N(3)

                For N(4) = 0 To 9                           ' n. Ziffer
                  Gefunden = 0
                  For M = 1 To 3                            ' Stellen 1 bis n-1 überprüfen
                      If Muster(m) = N(4) Then Gefunden = 1
                  Next M
                  If Gefunden = 0 Then                      ' wenn schon vorhanden, Ziffer überspringen
                     Muster(4) = N(4)                       ' letzte Ziffer komplett

                For N(5) = 0 To 9
                  Gefunden = 0
                  For M = 1 To 4
                      If Muster(m) = N(5) Then Gefunden = 1
                  Next M
                  If Gefunden = 0 Then
                     Muster(5) = N(5)

                For N(6) = 0 To 9
                  Gefunden = 0
                  For M = 1 To 5
                      If Muster(m) = N(6) Then Gefunden = 1
                  Next M
                  If Gefunden = 0 Then
                     Muster(6) = N(6)

                For N(7) = 0 To 9
                  Gefunden = 0
                  For M = 1 To 6
                      If Muster(m) = N(7) Then Gefunden = 1
                  Next M
                  If Gefunden = 0 Then
                     Muster(7) = N(7)

                For N(8) = 0 To 9
                  Gefunden = 0
                  For M = 1 To 7
                      If Muster(m) = N(8) Then Gefunden = 1
                  Next M
                  If Gefunden = 0 Then
                     Muster(8) = N(8)

                For N(9) = 0 To 9
                  Gefunden = 0
                  For M = 1 To 8
                      If Muster(m) = N(9) Then Gefunden = 1
                  Next M
                  If Gefunden = 0 Then
                     Muster(9) = N(9)

                For N(10) = 0 To 9
                  Gefunden = 0
                  For M = 1 To 9
                      If Muster(m) = N(10) Then Gefunden = 1
                  Next M
                  If Gefunden = 0 Then
                     Muster(10) = N(10)

                     'Print Nr ; " - " ; Muster(1) ; Muster(2) ; Muster(3) ; Muster(4) ; Muster(5) ;
                     'Print Muster(6) ; Muster(7) ; Muster(8) ; Muster(9) ; Muster(10)
                     Incr Nr

                  End If
                Next N(10)
                  End If
                Next N(9)
                  End If
                Next N(8)
                  End If
                Next N(7)
                  End If
                Next N(6)
                  End If
                Next N(5)
                  End If
                Next N(4)
             End If
         Next N(3)
      End If
    Next N(2)
    Print "Zwischenstand: " ; Nr ; " Kombinationen erzeugt"
Next N(1)

Decr Nr

Do
Print
Print "Erzeugte Kombinationen: " ;
Print Nr
Toggle Portd.5
Loop
End                                                         'end program

Zum Debuggen lasse ich die Schleifenwerte der ersten drei Stellen ausgeben, hier der Start:

1: 0 ' erste Ziffer ist "0"
2: 0 ' zweite Ziffer, "0" ist belegt,
2: 1 ' deshalb zweite Ziffer ist "1"
3: 0 ' dritte Ziffer, "0" ist belegt,
3: 1 ' "1" ebenfalls, 
3: 2 ' also ist "2" die dritte Ziffer 
2: 3 ' ab hier wirds dann unübersichtlich, 
3: 4 ' weil die inneren Schleifen keine Ausgabe
3: 5 ' machen und man deshalb die Sprünge
3: 6 ' nicht nachvollziehen kann
2: 7

... (4 Minuten später!)...

2: 9 ' zweite Stelle bei "9"
3: 0
3: 1
3: 2
3: 3
3: 4
3: 5
3: 6
3: 7
3: 8
3: 9 ' dritte Stelle bei "9"
Zwischenstand: 362881 Kombinationen erzeugt
1: 1 ' Übertrag zur ersten Stelle! Erste Ziffer ist jetzt "1" 
2: 0
3: 0
3: 1
3: 2
3: 3

Da der Zähler voreilt sind es in Wirklichkeit "nur" 362880 Kombinationen die mit "0" beginnen. Erfreulicherweise stimmt hier die Theorie mit der Praxis überein:
9*8*7*6*5*4*3*2=362880 :)

Wenn man die Zeit für die Ausgabe vernachlässigt ist mein 8MHz nach etwas mehr als 40 Minuten fertig mit allen Kombinationen...

[PICture]

Hallo!

Mir ist dazu nur eingefallen (falls ich mich nicht irre), dass zum Abspeichern von allen Kombinationen werden in BCD Kodierung 5 * 3628800 = 18 144 000 Bytes, also über 18 MB benötigt.

[radbruch]

Rekursiv in C (für den asuro):

// Zahlenproblem rekursiv in C :)                                       29.7.2011 mic

#include "asuro-probot.h"
#include "asuro-probot.c"

#define ziffern 4

uint8_t muster[ziffern];
uint8_t x[10], gefunden;
uint32_t nr=0;

void suchen(uint8_t z)
{
	uint8_t y;

	for(x[z]=0; x[z]<10; x[z]++)
	{
		gefunden=0;
		for(y=0; y<z; y++)
		   if(muster[y]==x[z]) gefunden=1;
		if(!gefunden)
		{
			muster[z]=x[z];
			if(z < (ziffern-1))
			{
				suchen(z+1); // Rekursion!
			}
			else
			{
				if(0) // 1 bedeutet: Ausgabe der Ziffernkombinationen
				{
					PrintInt(nr);
					SerWrite(": ", 2);
					for(y=0; y<ziffern; y++)
					{
						while(!(UCSRA & 0x20));
						UDR = muster[y]+'0';
					}
					SerWrite("\r\n", 2);
				}
				nr++;
			}
		}
	}
}

int main(void)
{
	Init();
	PORTC |= 3; // Odo-PullUps simulieren für PollSwitch()
	StatusLED(RED);

	for(x[0]=0; x[0]<10; x[0]++)
	{
   	muster[0]=x[0];
		suchen(1);
	}
	while(1)
	{
   	PrintInt(nr);
		SerWrite("\r\n", 2);
		Beep(50);
	}
return(0);
}

Probelauf mit 4 Ziffern ergibt wieder 5040. Speichern will ich das Ergebniss natürlich nicht. Fragt sich nun, wie man die Symmetrien der Ziffernfolgen einbauen könnte.

Gruß

mic

[Edit]
Nach der Optimierung:

// Zahlenproblem rekursiv in C :)                                       31.7.2011 mic

#include <avr/io.h>
#include <stdlib.h>

#define ziffern 3

uint8_t x[10], y, gefunden;
uint32_t nr=1;

void SerWrite(char *data, uint8_t length); // char???
void PrintInt32(uint32_t wert);
void ausgabe(void);

void suchen(uint8_t z)
{
	for(x[z]=0; x[z]<10; x[z]++)
	{
		gefunden=0;
		for(y=0; y<z; y++) if(x[y]==x[z]) gefunden=1;
		if(!gefunden)
		{
			if(z < (ziffern-1)) suchen(z+1); // Rekursion!
			else
			{
				ausgabe(); // Ausgabe der Ziffernkombinationen in x[0] bis x[ziffern-1]
				nr++;
			}
		}
	}
}

int main(void)
{
	SerWrite("\033[1;1H", 6); // home  VT100-Emulation
	SerWrite("\033[2J", 4); //clear terminal screen

	for(x[0]=0; x[0]<5; x[0]++) suchen(1);

	nr--;
	DDRD |= (1<<PD5); // Led
	while(1)
	{
   	PrintInt32(nr);
		SerWrite("\r\n", 2);
		if(PIND & (1<<PD5)) PORTD &= ~(1<<PD5); else PORTD |= (1<<PD5); // blinken
	}
return(0);
}

void SerWrite(char *data, uint8_t length) // aus der asuro-Lib
{
	unsigned char i = 0;
	UCSRB = 0x08; // enable transmitter
	while (length > 0) {
		if (UCSRA & 0x20) { // wait for empty transmit buffer
			UDR = data[i++];
			length --;
		}
	}
	while (!(UCSRA & 0x40));
	//for (i = 0; i < 0xFE; i++)
		//for(length = 0; length < 0xFE; length++);
}

void PrintInt32(uint32_t wert) // aus der asuro-Lib
{  char text[7]="       ";
	itoa(wert,text,10);
	SerWrite(text,7);
}

void ausgabe(void)
{
	for(y=0; y<ziffern; y++)
	{
		while(!(UCSRA & 0x20));
		UDR = x[y]+'0';
	}
 	SerWrite("  ",2);
	for(y=0; y<ziffern; y++)
	{
		while(!(UCSRA & 0x20));
		UDR = 9-x[y]+'0';
	}
 	SerWrite("  ",2);
	PrintInt32(nr);
 	SerWrite("\r\n",2);
}

Ohne Ausgabe schafft mein asuro die 10-stelligen Kombinationen in knapp 22 Minuten :)

[iBot]

@radbruch:
Du bist echt ein Held. Hab das Programm für Bascom mal eben im Simulator laufen lassen und es funktioniert wirklich einwandfrei.
Sag mal wie hast du das so schnell hinbekommen? Ich hätte dafür sicher noch einige Wochen grübeln müssen…
Und jetz auch noch in C …
Allerdings hab ich mal noch eine Frage: Warum kommst du nur auf 362880 Möglichkeiten ? Es müssten doch 3628800 sein…
bzw. was meinst du mit "Da der Zähler voreilt…"?

@PICture:
Na zum Glück muss es nur Ausgegeben und nicht gespeichert werden .

[PICture]

Ich bin eher an Hexzahlen gewöhnt um alle mögliche Kombinationen zu erstellen, da es am einfachsten geht. Die grösste Zahl wäre 9876543210 d = 24CB016EA h was "nur" 34 Bits braucht und die grössere bis 2FFFFFFFF h könnte man weg lassen. Danach muss man natürlich jede Hexzahl in eine Dezimale wandeln.

Es müssten natürlich noch dezimale Zahlen, wo sich gleiche Ziffern wiederholen, entfernt werden.

[radbruch]

Sag mal wie hast du das so schnell hinbekommen?

Das ist reine Übungssache :) Allerdings war es zufällig auch mein erstes C-Programm mit Rekursion.

...Danach muss man natürlich jede Hexzahl in eine Dezimale wandeln.

Und dann muss mannur noch alle Zahlen mit doppelten Ziffern entfernen...

Allerdings hab ich mal noch eine Frage: Warum kommst du nur auf 362880 Möglichkeiten ? Es müssten doch 3628800 sein…
bzw. was meinst du mit "Da der Zähler voreilt…"?

Die Ausgabe des Zählerstandes erfolgt am Ende der For-Schleife für die erste Ziffer:

    Print "Zwischenstand: " ; Nr ; " Kombinationen erzeugt"
Next N(1)

Decr Nr

Zu diesem Zeitpunkt sind alle Kombinationen die mit "0" anfangen generiert. Allerdings wurde die Nr-Variable schon für die nächste Runde erhöht, deshalb eilt der Zähler an dieser Stelle immer um 1 vor.

Ich denke, auch das Symmetrieproblem ist gelöst:

				if(0) // 1 bedeutet: Ausgabe der Ziffernkombinationen
				{
					PrintInt(nr);
					SerWrite(": ", 2);
					for(y=0; y<ziffern; y++)
					{
						while(!(UCSRA & 0x20));
						UDR = muster[y]+'0';
					}
					SerWrite("  ", 2);
					for(y=0; y<ziffern; y++)
					{
						while(!(UCSRA & 0x20));
						UDR = 9-muster[y]+'0';
					}
					SerWrite("\r\n", 2);
				}

Damit kann man die äußerste Schleife im Hauptprogramm von 0 bis 4 laufen lassen und durch die Spiegelung der Werte wird der Bereich 5 bis 9 generiert.

Wozu kann man solche Kombinationen eigentlich nutzen?

[SprinterSB]

Falls das Problem noch aktuell ist, hier meine Lösung in C.

Eingegeben wird die Anzahl der zu permutierenden Zeichen (N)
und die Nummer der auszugebenden Permutation (n).

Beispiel mit N = 5, n = 1
#1: 12345

Beispiel mit N = 5, n = 120
#120: 54321

Beispiel mit N = 3, n = 0
#1: 123
#2: 132
...
#6: 321

Beispiel mit n = 12, n = 100000
#100000: 12368AB59704

#include <stdio.h>
#include <string.h>

#define DIGITS "1234567890ABCDEF"

int print_perm (unsigned int N, unsigned int n0)
{
    char *l, letters[] = DIGITS;
    int j, digit[N];
    unsigned int n = n0;
    
    // n0 in faktorielle Darstellung umwandeln
    
    for (unsigned int i = 1; i <= N; i++)
    {
        digit[i-1] = n % i;
        n /= i;
    }
    
    if (n)
        return 0;
        
    // n0-te Permutation ausdrucken
    
    printf ("#%d: ", n0 + 1);
    
    for (int i = N-1; i >= 0; i--)
    {
        for (j = -1, l = letters - 1; j < digit[i]; j += *++l != ' ');
        printf ("%c", *l);

        // Gedruckte Zeichen aus Liste entfernen
        *l = ' ';
    }
    
    printf ("\n");
    
    return 1;
}

int main ()
{
    unsigned int n, N;
    
    printf ("\nAnzahl Zeichen: ");
    scanf ("%u", &N);

    printf ("\nPermutation Nr. (0 fuer alle): ");
    scanf ("%u", &n);
    
    if (N == 0 || N > strlen (DIGITS))
    {
        printf ("Ungueltige Eingabe: Anzahl Zeichen in 1..%d\n",
                strlen (DIGITS));
        return 1;
    }
    
    if (n)
        print_perm (N, n-1);
    else
        while (print_perm (N, n++));
    
    return 0;
}

Der Code ist einfach gehalten und berechnet die faktorielle Darstellung für jede Permutation neu.
Für eine effiziente Implementierung falls alle Permutationen gebraucht werden oder nur eine Teilmenge aus einer Obermenge auszuwählen ist, kann man eine Arithmetik auf der faktoriellen Darstellung implementieren.

[radbruch]

Ja, das sieht echt clever aus, vor allem die imponierende for-Schleife. Allerdings funktioniert es irgendwie nicht richtig. Da mein asuro die stdio.h nicht richtig anwendet habe ich versucht, das Programm anzupassen:

#include "asuro-probot.h"
#include "asuro-probot.c"
//#include <stdio.h>
//#include <string.h>

#define DIGITS "1234567890ABCDEF"

int print_perm (unsigned int N, unsigned int n0)
{
    char *l, letters[] = DIGITS;
    int j, digit[N];
    unsigned int n = n0;
    unsigned int i;
    
    // n0 in faktorielle Darstellung umwandeln

    for (i = 1; i <= N; i++)
    {
        digit[i-1] = n % i;
        n /= i;

			//while(!(UCSRA & 0x20));
			//UDR = digit[i-1]+'0';
    }
		//SerWrite("\r\n\n",3);

    if (n)
        return 0;

    // n0-te Permutation ausdrucken

    //printf ("#%d: ", n0 + 1);
      PrintInt(n0+1);
      SerWrite(": ",2);

    for (i = N-1; i >= 0; i--)
    {
        for (j = -1, l = letters - 1; j < digit[i]; j += *++l != ' ');
        //printf ("%c", *l);

			while(!(UCSRA & 0x20)); // Warten bis USART fertig ist
			//UDR = *l; // Wert an Adresse l senden
			UDR = *l+'0'; // Wert an Adresse l als Ascii-Zeichen senden
			//UDR = i+'0'; // i als Ascii-Zeichen senden

        // Gedruckte Zeichen aus Liste entfernen
        *l = ' ';
    }

    //printf ("\n");
 		SerWrite("\r\n",2); // neue Zeile

    return 1;
}

int main (void)
{
    unsigned int n=0, N=3;

/*    printf ("\nAnzahl Zeichen: ");
    scanf ("%u", &N);

    printf ("\nPermutation Nr. (0 fuer alle): ");
    scanf ("%u", &n);

    if (N == 0 || N > strlen (DIGITS))
    {
        printf ("Ungueltige Eingabe: Anzahl Zeichen in 1..%d\n",
                strlen (DIGITS));
        return 1;
    }
*/
 		SerWrite("\r\n\n",3); // neue Zeile

    if (n)
        print_perm (N, n-1);
    else
        while (print_perm (N, n++));
        
	 while(1);
    return 0;
}

Die Ausgabe:

1    : 123R 6Eƈ "¤    "×"  ˆ Cø (usw....)

Liegts an mir oder am Programm?

Gruß

mic

[Edit]
Die Lösung sollte doch so aussehen:

Beispiel mit N = 3, n = 0
#1: 123
#2: 132
...
#720: 098