Ein Zahlenproblem

[iBot]

Hallo Leute,
eigentlich hat das Problem rein gar nichts mit Robotik zu tun, außer vlt dass es um Automatisierung geht.
Aber jetzt ohne langes Reden gleich zum Problem ;) :

Ich habe 10 Zahlen (0-9) und ich möchte nun alle Kombinationsmöglichkeiten, wobei jede Zahl nur ein mal pro Kombination vorkommt (z. B. 1345267098 ) mittels eines Algorithmus ermitteln. (Später soll das dann mal in einem Programm für einen µC enden.)

Laut Rechnung wären das 3628800 Möglichkeiten (k=n! bzw. k=1*2*3*4*5*6*7*8*9*10).

Eine Idee wäre die Zahlen immer um einen Platz zu verschieben, also:


'ausgegangen von der Zahl abcdefghij

a=b
b=c
c=d
d=e
e=f
f=g
g=h
h=i
i=j
j=a

z=z+1 'bis z irgendwann 10 ist


Das würde schon mal die Möglichkeiten deutlich verringern (wenn ich mich nicht irre wäre es dann nur noch 1/10 )
Aber wie komm ich zu den restlichen 362880 Möglichkeiten ?

Falls ich irgendwo einen Denkfehler hineingebracht habe, bitte bescheid geben.

[justin]

Ohne jetzt länger drüber nachgedacht zu haben (ist ja schon spät) in irgendeiner Java-ähnlichen Fantasiesprache:


void schreibeAlleKombinationen(List<Ziffer> kombinationBisher, List<Ziffer> moeglicheZiffern){
Iterator<Ziffer> i = moeglicheZiffern.getIterator();
boolean foundSomething = false;
while(i.hasNext()){
Ziffer next = i.next();
if(! kombinationBisher.contains(next)){
schreibeAlleKombinationen(kombinationBisher.append (next),moeglicheZiffern);
foundSomething = true;
}
}
if(! foundSomething){
System.out.println(kombinationBisher.toString());
}
}

[Manf]

Die Positionen nacheinander betrachten:
An der ersten Position steht nacheinander jede der Ziffern a-j.
Für jeden der Fälle steht an der zweiten Position jede der Ziffern a-j mit Ausnahme der schon für die Position 1 ausgewählten Ziffer.
Für jeden der Fälle steht an der dritten Position jede der Ziffern a-j mit Ausnahme der schon für die Position 1 und 2 ausgewählten Ziffern.
...

[radbruch]

Hallo

Mein erster Gedanke:

1:
0123456789

3628800:
9876543210

Ich vermute, man muss nur die Hälfte der Kombinationen errechnen, denn das Ergebniss sollte nach der Mitte gespiegelt sein.

Gruß

mic

[PicNick]

Ich würde den Hinweis von Manf in eine Formel fassen, das geht sicher am schnellsten
(10)*(10-1)*(10-2).........

[iBot]

Danke für die vielen Antworten so früh :D

@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. :p

[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 :D …
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 :D .

[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

[iBot]

Ok also ich hänge immer noch bei der ersten guten Idee von radbruch fest. :D
Aber ich glaube das Problem ist jetzt im Großen und Ganzen gelöst.


Wozu kann man solche Kombinationen eigentlich nutzen?
ich sag nur Brute Force-Angriffe :D
Nein natürlich nicht.
In der Zeitschrift "Gong" gibt es jede Woche ein neues sogenanntes "Rechenproblem" , dabei hat man 6 in einander verschachtelte Gleichungen die aus Symbolen bestehen welche je für eine Zahl von 0-9 Stehen. Das Ganze ist oft ziemlich kniffelig zu lösen und weil ich oft nicht bis zur nächsten Ausgabe warten kann und weil es mich irgendwie interessierte, wie das ein Computer lösen könnte, musste ich als erstes erst einmal einen Weg finden, alle erdenklichen Kombinationen für die Variablen bzw. Symbole des Rechenproblems zu finden. Das Einsetzen lassen und auf Richtigkeit überprüfen dürfte da deutlich leichter gehen.

[SprinterSB]

Ja, das sieht echt clever aus, vor allem die imponierende for-Schleife. Allerdings funktioniert es irgendwie nicht richtig. [...] Liegts an mir oder am Programm?
Die Folge "123" wird ja ausgegeben; irgendwas hast du da geändert oder veränderst Optionen, die das ABI verändern (unsigned-char?).

Ich hab's eben genau so auf einem ATmega88 getestet: Funktioniert ebenso wie das PC-Original. Ich verwende Zusatzmodule, so daß ich ganz normal mit printf etc arbeiten kann ohne immer die Quelle für AVR/PC umändern zu müssen. Für solche kleinen Tests ist das super praktisch.

Wenn du alle Permutationen nacheinander willst, ist es wie gesagt günstiger, immer 1 auf die faktorielle Darstellen zu addieren anstatt für jedes n die Darstellung neu zu berechnen. Bei der faktoriellen Darstellung wächst die Wertigkeit der Stellen: 1, 2, 3, 4, ... während sie z.B. beim Dualsystem 2, 2, 2, ... oder beim Zezimalsystem 10, 10, 10, ... ist. Einfach bei der kleinsten Ziffer Eins aufaddieren und stellenweise Überträge berücksichtigen.

Anstsatt "Brutaler Gewalt" würd ich eher bissl Hirnschmalz auf die Lösung inverstieren; so schwer sind die Rätsel ja nicht. Bisher hab ich von denen noch keins gesehen, das nicht durch Überlegen zu knacken gewesen wäre.

[justin]

Nur so als Hinweis:

http://de.wikipedia.org/wiki/Prolog_%28Programmiersprache%29#L.C3.B6sen_eines_m athematischen_R.C3.A4tsels

[Searcher]

Hallo,
da ich durch C nicht durchblicke, hier noch ein Versuch durch Tauschen der Stellen in der Richtung wie Manf vorgeschlagen hat ?


$regfile = "attiny45.dat"
$framesize = 32
$swstack = 32
$hwstack = 36
$crystal = 8000000

Const Max_positionen = 4 'Anzahl Stellen
Const Max_pos_decr = Max_positionen - 1 'Hilfskonstante

Dim Zahl(max_positionen) As Byte 'enthält jeweilige Kombination
Dim Roll_pos(max_positionen) As Byte 'Hilfsvariable für Rollpositionen
Dim Zahl_str As String * Max_positionen 'variable für Ausgabe der Kombination

Dim Ab_stelle As Byte 'Übergabevariable in Sub "rollen"
Dim I As Byte , Zw1 As Byte , Zw2 As Byte
Dim Moeglichkeit_nr As Long 'zählt gefundene Möglichkeiten durch

Defbyte S 'Noch nicht decl. Variablen beg. mit S as byte

Declare Sub Rollen(ab_stelle As Byte)
Declare Sub Ausgabe

'####################
'Beginn Hauptprogramm

Moeglichkeit_nr = 0

For I = 1 To Max_positionen
Zahl(i) = I - 1
Roll_pos(i) = Max_positionen - I
Next I

'Zahlarray mit maximal 10 Stellen mit Ziffern 0..9
'links ist Stelle 10 - ST10 , rechts ist Stelle 1 - ST1
'läuft mit 4 Stellen
'zum Erweitern Kommentare entfernen UND Konstante Max_positionen anpassen

'For St10 = 1 To 10
' For St9 = 1 To 9
' For St8 = 1 To 8
' For St7 = 1 To 7
' For St6 = 1 To 6
' For St5 = 1 To 5
For St4 = 1 To 4
For St3 = 1 To 3
For St2 = 1 To 2
For St1 = 1 To 1
Ausgabe
Next St1
Rollen Roll_pos(1)
Next St2
Rollen Roll_pos(2)
Next St3
Rollen Roll_pos(3)
Next St4
' Rollen Roll_pos(4)
' Next St5
' Rollen Roll_pos(5)
' Next St6
' Rollen Roll_pos(6)
' Next St7
' Rollen Roll_pos(7)
' Next St8
' Rollen Roll_pos(8)
' Next St9
' Rollen Roll_pos(9)
'Next St10

End 'end program

'##########
'Beginn Unterprogrammdefinitionen

Sub Rollen(ab_stelle As Byte) 'links rollen um 1 der rechten Stellen in "Zahl" ab "ab_stelle"
Zw1 = Zahl(ab_stelle)
For I = Ab_stelle To Max_pos_decr
Zw2 = I + 1
Zahl(i) = Zahl(zw2)
Next
Zahl(max_positionen) = Zw1
End Sub

Sub Ausgabe

Incr Moeglichkeit_nr 'Wieder eine Möglichkeit mehr zur Ausgabe
'Hier eigene Ausgabeanweisungen rein
'zb Print
Zahl_str = ""
For I = 1 To Max_positionen
Zahl_str = Zahl_str + Str(zahl(i)) 'Kombination im Zahl array in String geben
Next I
End Sub

Algorithmus ist mit Turbo Pascal ausprobiert, BASCOM Prg aber nur bis 4 Stellen im Simulator getestet.


EDIT: Etwas spät, aber ich möchte die Arbeitsweise vom Programm noch etwas erklären:

Das Array "Zahl" enthält soviele Elemente, wie verschiedene Elemente vorhanden sind, von denen Permutationen gebildet werden sollen. In diesem Fall 10 für die Zahlen 0 bis 9.

Das Array wird dann mit den Zahlen 0..9 gefüllt. Möglich sind auch Buchstaben oder sonstwas, wenn es dem Arraytyp entspricht bzw der Arraytyp angepaßt wird.

Danach läuft das Programm in die For-To Schleifen und landet bei "Ausgabe" -> es wird die Initialisierung von "Zahl" als erste Möglichkeit ausgegeben.

Nach der Ausgabe wird der Inhalt nur der beiden letzten Arrayelemente nach links gerollt (was für die beiden ein Austausch bedeutet.)

Das wird dann als nächste Möglichkeit wieder zur Ausgabe gebracht und die letzten beiden Arrayelementinhalte wieder getauscht, was zum Initialisierungszustand zurückführt.

Nun ist ST2 aber erfüllt und ein Rollen von 3 Elementen ab dem drittletzten Element findet statt und danach ausgegeben.
Die letzten beiden Elemente werden wieder gerollt und ausgegeben, weiter wie oben.

Das findet für ST3 drei Mal statt - Initialisierungszustand wieder erreicht, der nicht ausgegeben wird - ab viertletztem Element gerollt - Ausgabe
...und so weiter.


Gruß
Searcher

[iBot]

@Searcher:
Wenn ich mich nicht irre macht doch das Programm von radbruch das Selbe oder?

Ich glaube das Rätsel wurde (in mehreren Sprachen gleich :D ) gelüftet und der Thread kann geschlossen werden.
Danke für eure Beteiligung.

[Searcher]

@Searcher:
Wenn ich mich nicht irre macht doch das Programm von radbruch das Selbe oder?

Hi,
ich kann radbruchs C Programme nicht verstehen. Seine BASCOM Programme, wenn ich das richtig verstehe, nehmen Ziffern und vergleichen, ob diese schon in der Kombination vorhanden sind.???

Mein Programm verzichtet darauf und tauscht stur die Stellen durch.

Bitte um Berichtigung, wenn ich da was falsch interpretiert habe.

Gruß
Searcher

[radbruch]

Hallo Searcher

Deine Lösung funktioniert leider auch nicht richtig, weil sie nicht alle Ziffern von '0' bis 9' berücksichtigt. Ausgabe deiner Variante:


0123
0132
0231
0213
0312
0321
1230
1203
1302
1320
1023
1032
2301
2310
2013
2031
2130
2103
3012
3021
3120
3102
3201
3210

24
Kombinationen und Anzahl der Kombinationen. Richtig wäre 10*9*8*7=5040 Kombinationen. Hier die Kombinationen mit drei Stellen:
https://www.roboternetz.de/community/attachment.php?attachmentid=19482&d=1312105805

Gruß

mic

[Edit]

Das C-programm macht genau desselbe wie die Bascom-Variante. Es wird ein Array mit der Anzahl der gewünschten Stellen erzeugt und jede Stelle nacheinander mit allen Werten ausprobiert. Wenn der Wert für die aktuelle Stelle schon im Array vorhanden ist, wird dieser Wert übersprungen. Wenn man mit dem Wert für die erste Stelle startet, kann man alle weiteren Stellen mit dem selben Algorithmus errechnen:

void suchen(uint8_t z) // z ist der Index im Array, es wird also die z-Stelle erzeugt
{
for(x[z]=0; x[z]<10; x[z]++) // Werte von 0 bis 9 erzeugen
{
gefunden=0; // flag wird gestezt, wenn Wert schon im Array erhalten ist
for(y=0; y<z; y++) if(x[y]==x[z]) gefunden=1; // Alle Elemente im Array vor aktuellem Index prüfen
if(!gefunden) // Wenn der Wert erstmalig im Array auftritt wird er im Array unter dem aktuellen Index espeichert
{
if(z < (ziffern-1)) suchen(z+1); // Rekursion! // Wenn noch nicht alle Stellen berechnet sind wird die nächste Stelle berechnet
else
{
ausgabe(); // Ausgabe der Ziffernkombinationen in x[0] bis x[ziffern-1]
nr++;
}
}
}
}

[Searcher]

Hallo radbruch,
das war ja schnell getestet! Die Ausgabe ist Absicht.

Wenn die Anzahl der Stellen auf 4 begrenzt ist, werden alle Permutationen der Ziffern 0, 1, 2, 3 ausgegeben. Zu Testzwecken durch die REMs auf 4 begrenzt.

Wenn die Anzahl der Stellen auf 10 ist, werden alle Permutationen der Ziffern 0, 1, 2, 3 ... 9 ausgegeben.

Gruß
Searcher

[radbruch]

Wenn die Anzahl der Stellen auf 10 ist, werden alle Permutationen der Ziffern 0, 1, 2, 3 ... 9 ausgegeben.Achso, das habe ich natürlich nicht versucht. Sorry. Dann bin ich mit meiner Lösung eigentlich übers Ziel hinausgeschossen.

[Searcher]

Achso, das habe ich natürlich nicht versucht.
Das mit den 10 Stellen hab ich, ehrlich gesagt, auch nicht ausprobiert. :-) :-)

Bis 5 Stellen mit 0, 1..4 hat es geklappt und das hat mich schon einige Kästchen auf kariertem Papier und Radiergummi gekostet. :-)

Gruß
Searcher