Permutation von 1,2,3,4.. n natürlichen Zahlen

binder0101

Grünschnabel
Schreiben Sie ein Programm, welches eine Folge p von n natürlichen Zahlen einliest und, falls es sich dabei um eine Permutation der natürlichen Zahlen 1, 2, ..., n handelt, prüft, ob die Permutation gerade oder ungerade ist.

Anmerkung: Steht in einer Permutation eine größere Zahl vor einer kleineren, so liegt eine "Inversion" dieser beiden Zahlen vor. Ist die Anzahl der Inversionen gerade, so heißt auch die Permutation gerade, entsprechend bei ungerader Anzahl von Inversionen.

Beispiel:

Eingabe: 1 2 6 3 4
Keine Permutation
Programm wiederholen(j/n)?

Einabe: 2 4 1 3
Ungerade Permutation
Programm wiederholen(j/n)?

Eingabe: 4 1 3 2
Gerade Permutation
Programm wiederholen(j/n)?

Eingabe: 3 5 2 1
Keine Permutation
Pogramm wiederholen (j/n)?

Hallo, Leute ich bin gerade am herumtüffteln dieser Aufgabenstellung, jedoch mach ich irgendetwas falsch und komme nicht weiter vielleicht könnte ja jemand einen Blick drüberwerfen und schauen was da falsch ist. PS: ich bekomm das mit den einlesen von n natürlichen Zahlen nicht hin deswegen Konstante mit ANZAHL 5 und ich hab so garkeinen Plan wie ich das schaffe überhaupt eine Permutation zubestimmen also:

Eingabe: 3 5 2 1
Keine Permutation
Pogramm wiederholen (j/n)?

Danke schon mal im vorraus
C++:
#define ANZAHL 5

void ausgabe(const int array[], int laenge, int stellen);
int inversion(int *werte, int len);



int main(void){
	//Variablendeklaration
	int feld[ANZAHL];
	int i; int n;
	int ergebnis = 2;

	for (i = 0; i<ANZAHL; i++) {
                 
                printf("Zahl: ");
		fgets(feld, sizeof(feld), stdin);
		zahl = strtol(feld, &eptr, 10);
	}


	n = sizeof(feld) / sizeof(feld[0]);
	printf("das feld lautet:");
	ausgabe(feld, n, 4);
	putchar('\n');
	inversion(feld, n);

	return EXIT_SUCCESS;
}


void ausgabe(const int array[], int n, int breite){
	int i;

	for (i = 0; i<n; i++)
		printf("%*d", breite, array[i]);
}

int inversion(int *werte, int len){ /* len ist die Länge des Arrays, wo man
									die Werte eingegeben hat */

	int j = 0, k = 0, count = 0;

	for (j = 0; j<len; j++)
	for (k = j+1; k<len; k++)
	if (werte[j]>werte[k])
		count++; /* count wird stets erhöht, wenn*/
	printf("es musste %d mal getauscht werden!!\n", count); //ein Element im Array > als einer der nachfolgenden ist

	if ((count % 2) == 0)
		printf("es liegt eine gerade permutation vor!\n\n");
	else
		printf("es liegt eine ungerade permutation vor!\n\n");

	return 0;
}
 

Technipion

Erfahrenes Mitglied
Hallo binder0101,
bei der Aufgabenstellung gibt es viele mögliche Algorithmen die dich mehr oder weniger schnell zum Ziel führen. Relativ leicht verständlich ist dieses Vorgehen:

1) Sortiere dein Eingabefeld p der Größe nach. (steigend)
2) Prüfe ob die n-te Zahl im sortierten Feld gerade n ist.
3) Falls ja:
i) Laufe über jede Zahl des Eingabefeldes bis zur vorletzten und prüfe, ob die folgende Zahl größer ist als die aktuelle (und erhöhe jeweils einen Zähler).
ii) Ist der Zähler gerade, gib "gerade Permutation" zurück, sonst gib "ungerade Permutation" zurück.
Falls nein:
Gib "keine Permutation" zurück.

Dieses Vorgehen ergibt sich daraus, dass alle Permutation das gleiche Ergebnis liefern wenn man sie nach einem bestimmten Kriterium sortiert. :D

Grüße Technipion
 

binder0101

Grünschnabel
Hallo Technipion,
Was verstehst du unter "Prüfe ob die n-te Zahl im sortierten Feld gerade n ist."? Könntest du das bitte ein wenig verständlicher formulieren und meinst du mit sortieren nach größe den bubblesort?
 

Cromon

Erfahrenes Mitglied
Hallo binder0101

Einfach gesagt:
C++:
if(array[n] == n)

Bzgl. Sortierung:
bubblesort, quicksort, mergesort, was auch immer dir beliebt :)

Grüsse
Cromon
 

Technipion

Erfahrenes Mitglied
Hi binder0101,
mit Sortieren meine ich einen beliebigen Sortieralgorithmus, der die Zahlen in aufsteigender Reihenfolge anordnet. Im Prinzip wie Bubblesort, nur bietet die Standard-Library viel schnellere Methoden (siehe hier: http://en.cppreference.com/w/cpp/algorithm/sort).

Der Algorithmus den ich dir genannt habe wird ziemlich anschaulich, wenn man mal ein paar Beispiele betrachtet. Lass uns mal von der umgekehrten Reihenfolge aus starten:
Wir nehmen eine Liste aller Zahlen 1 ... n und würfeln sie durcheinander (wir permutieren sie).
Also nehmen wir doch z.B. (1, 2, 3, 4, 5). Wenn wir das wild durcheinanderwerfen kommt z.B. das hier raus: (2, 3, 1, 5, 4). Damit haben wir eine Permutation erzeugt. Es gibt insgesamt n! (Fakultät) mögliche Permutationen für eine Liste mit n Elementen (in diesem Fall natürliche Zahlen). Aber alle Permutationen haben etwas gemeinsam, wenn man sie sortiert, liefern alle das gleiche Ergebnis.
Hier sind 3 mögliche Permutationen von (1, 2, 3, 4, 5):
(2, 3, 1, 5, 4), (1, 2, 3, 5, 4), (5, 1, 3, 4, 2)

Wenn wir die jetzt der Größe nach sortieren erhalten wir:
(1, 2, 3, 4, 5), (1, 2, 3, 4, 5), (1, 2, 3, 4, 5)

Tatsächlich wird jede Permutation von (1, 2, 3, 4, 5) nach dem Sortieren immer (1, 2, 3, 4, 5) zurückgeben.

Haben wir keine Permutation von (1, 2, 3, 4, 5), also z.B. (2, 1, 3, 1, 4), dann erhalten wir ein anderes Ergebnis, in diesem Fall z.B. (1, 1, 2, 3, 4).

Hier liegt sogar ein Spezialfall vor, denn jede Permutation enthält ja laut Vorgabe die Zahlen von 1 bis n.
Wenn wir also eine Liste mit allen Zahlen von 1 bis n sortieren, dann steht in dieser Liste an der n-ten Stelle die Zahl n:
(5, 1, 3, 4, 2) --- sortieren ---> (1, 2, 3, 4, 5) --- entspricht ---> (1.Stelle: 1, 2.Stelle: 2, 3.Stelle: 3, 4.Stelle: 4, 5.Stelle:5)

Ich hoffe ich konnte deine Fragen klären ;)

Gruß Technipion

EDIT:
Cromon war mal wieder schneller :D

@Cromon: kleine Abweichung noch im Code, in C++ fangen Listen mit Index 0 an, deshalb müsste es dann heißen:
C++:
if(array[n] == n+1)

Grüße Technipion
 
Zuletzt bearbeitet:

binder0101

Grünschnabel
Hallo Technipion,

Danke du hast mir schon sehr weitergeholfen, dennoch bleib ich immer noch am
"if(array[n] == n+1)" stecken da ich nicht weiß, welche Variable ich dafür einsetzen soll. Vielleicht könntest du mal über meine Fehlerquelle schauen und ich komm einfach nicht drauf wie mann überprüfen soll ob es KEINE Permutation denn man kann nicht überprüfen ob eine Folge von Zahl in sortierender Reihenfolge stattfindet oder irr ich mich da gerade gewaltig? Danke Schon mal im vorhinein.
Fehlerquelle:
C++:
if (folge[x] == x + 1){
			for (i = 0; i <= size - 1; i++){
				if (x + 1 > x){
					count++;
				}

			}
		}


C++:
//Includes
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <ctype.h>


//Hauptprogramm
int main(void){
	//Variablendeklaration
	char *eptr = NULL, nochmal = 'A';
	char folge[61]="",folge2[61]="";
	int zahl = 0,size=0,i=0,hilf=0,j=0,x=0,ausgabe=0,count=0;

	do{
		
		do{
			printf("%d.Eingabe: ",x+1);
			x++;
			fgets(folge2, sizeof(folge2), stdin);
			zahl = strtol(folge2, &eptr, 10);
			strncat(folge, folge2, 15);
		} while (zahl != 0);
		size = strlen(folge);
		
		printf("Folge:%s", folge);
		printf("\n");
		//Bubblesort
		for (i = 0; i < size - 1; i++){

			for (j = 0; j<size - 1 - i; j++){

				if (folge[j]>folge[j + 1]){

					hilf = folge[j];
					folge[j] = folge[j + 1];
					folge[j + 1] = hilf;
				}

			}

		}
		printf("Folge sortiert: %s\n", folge);
		
		size = strlen(folge);
		if (folge[x] == x + 1){
			for (i = 0; i <= size - 1; i++){
				if (x + 1 > x){
					count++;
				}

			}
		}

		if ((count % 2) == 0)
			printf("es liegt eine gerade Permutation vor!\n\n");
		else
			printf("es liegt eine ungerade Permutation vor!\n\n");




		printf("Wollen Sie das Programm neu starten? (J/N)\n");
		nochmal = getch();
	} while (nochmal == 'j' || nochmal == 'J');
	return EXIT_SUCCESS;
}
 

Technipion

Erfahrenes Mitglied
Hallo binder0101,
das hier:
C++:
if (folge[x] == x + 1){
            for (i = 0; i <= size - 1; i++){
                if (x + 1 > x){
                    count++;
                }
 
            }
        }
kann so nicht funktionieren.
Ich vermute, du hast da etwas mit der Permutation und mit der sortierten Permutation durcheinander gebracht.
Die sortierte Permutation benutzt du um festzustellen, ob es sich überhaupt um eine Permutation der Zahlen 1 bis n handelt. Um herauszufinden ob die Permutation gerade ist, brauchst du dann wieder die Permutation selbst.
Eine Implementierung könnte z.B. so aussehen:
C++:
#include <iostream>     // für std::cout
#include <algorithm>    // für std::sort
#include <vector>       // für std::vector

int main()
{
    int Eingabezahlen[] = {5, 1, 3, 4, 2}; //mögliche Eingabe
    /// Algorithmus
    std::vector<int> Permutation (Eingabezahlen, //übernehme die Eingabe
                                  Eingabezahlen + sizeof(Eingabezahlen) / sizeof(int)); //länge der Eingabe
    std::vector<int> SortierteEingabe (Permutation); //den werden wir gleich sortieren
    std::sort(SortierteEingabe.begin(), SortierteEingabe.end()); //sortieren...
    for (int i = 0; i < SortierteEingabe.size(); i++) {
        if (SortierteEingabe[i] != i+1) { //wenn das i-te Element nicht i ist
            std::cout << "keine Permutation!" << std::endl;
            return 0;
        }
    }
    //wenn wir hier ankommen, liegt eine Permutation vor
    int AnzahlInversionen = 0;
    for (int i = 0; i < Permutation.size()-1; i++) { //prüfe ob gerade oder ungerade
        if (Permutation[i] > Permutation[i+1])
            AnzahlInversionen += 1;
    }
    if (AnzahlInversionen % 2 == 0) {
        std::cout << "gerade Permutation." << std::endl;
        //hier könnte return 0 stehen
    } else {
        std::cout << "ungerade Permutation." << std::endl;
        //hier könnte return 0 stehen
    }
    /// fertig
    //aufräumen, etc.
    return 0;
}

Ich denke der Code sollte eigentlich selbsterklärend sein ;)
Ich hätte hier noch ein paar Tipps, die dich (höchst wahrscheinlich) zu einem besseren Programmierstil führen:
1) Es ist schick, zwischen printf/scanf und cout/cin zu unterscheiden.
2) Niemand ist dir böse wenn du die Standardbibliothek verwendest :) , durch die Verwendung von std::vector zum Beispiel wird Code in der Regel anschaulicher. (ebenso ist std::sort mit Sicherheit schneller implementiert als eine eigene Bubblesort-Funktion)
3) Immer wenn du mit Benutzereingaben zu tun hast, solltest du an Exceptions denken.

Das sind nur Tipps und keine Kritik, dein Stil ist schon deutlich besser als so manch andere Codes die man hier findet :D

In diesem Sinne
Gruß Technipion