Permutation of Array



  • Hallo,

    printPermuation of Array. Mal Hand aufs Herz ist der Algorithmus einfach oder schwer. Auf ner Skala von 1 bis 5 würde ich sagen sau schwer = 5 .

    z.B. int* arr [3] = {1,2,3};

    Ausgabe 1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 1 2
    3 2 1


  • Mod

    Was hat das mit C++ zu tun? Was ist deine Frage? Willst du Mitleid? Eine Lösung deiner Hausaufgaben? Ich weiß nicht, welchen Algorithmus du meinst, aber es gibt einen, der wäre eine 1 auf deiner Skala. Eher schon eine 0.


  • Mod

    Ich weiß nicht, welchen Algorithmus du meinst, aber es gibt einen, der wäre eine 1 auf deiner Skala. Eher schon eine 0.

    Ich würde ihm eine zwei geben.

    template<class BidirIt>
    bool next_permutation(BidirIt first, BidirIt last)
    {
        if (first == last) return false;
        BidirIt i = last;
        if (first == --i) return false;
    
        while (1) {
            BidirIt i1, i2;
    
            i1 = i;
            if (*--i < *i1) {
                i2 = last;
                while (!(*i < *--i2))
                    ;
                std::iter_swap(i, i2);
                std::reverse(i1, last);
                return true;
            }
            if (i == first) {
                std::reverse(first, last);
                return false;
            }
        }
    }
    

  • Mod

    Arcoth schrieb:

    Ich würde ihm eine zwei geben.

    Deiner ist ja auch wesentlich komplizierter, als das, was ich machen würde.



  • @SeppJ
    Weiss nicht ob das "seiner" ist...
    http://en.cppreference.com/w/cpp/algorithm/next_permutation
    😉

    ----

    Funktioniert dein "einser" Algorithmus auch wenn es Duplikate in dem Array gibt?


  • Mod

    hustbaer schrieb:

    Funktioniert dein "einser" Algorithmus auch wenn es Duplikate in dem Array gibt?

    Kommt drauf an, welches Ergebnis du in dem Fall wünscht. Mein Algorithmus glaubt nicht an die Ununterscheidbarkeit gleicher Werte 😃



  • Gut, ich wollte nur wissen was du meinst.
    Denn ein "Einser" der doch an die Ununterscheidbarkeit gleicher Werte glaubt fällt mir nicht ein.
    Und falls du einen kennst, hätte mich der schon interessiert.


  • Mod

    @SeppJ: Listet deiner denn alle in Reihenfolge auf? Und funktioniert für beliebige Mengen?


  • Mod

    Mir fällt

    void list_permutations( int* arr, std::size_t len, std::size_t previous_len=0 ) {
    	if (len==1) {
    		while (previous_len--)
    			std::cout << *arr--;
    		std::cout << *arr << std::endl;
    		return;
    	}
    
    	for (std::size_t p = 0; p != len; ++p) {
    		std::iter_swap(arr, arr+p);
    		list_permutations(arr+1, len-1, previous_len+1);
    		std::iter_swap(arr, arr+p);
    	}
    }
    

    ein - ist aber IMO keine 1.



  • "Für beliebige Mengen" finde ich eine komische Forderung, da der next_permutation der STL (den du ja gezeigt hast) gerade nicht für beliebige Mengen funktioniert. Schliesslich wird vorausgesetzt dass die Elemente sortierbar sind.


  • Mod

    hustbaer schrieb:

    Schliesslich wird vorausgesetzt dass die Elemente sortierbar sind.

    Ich dachte eher daran dass es nicht um Ganzzahlmengen mit lediglich konsekutiven Elementen geht, die auch noch mit 1 beginnen.

    "Für beliebige Mengen" finde ich eine komische Forderung, da der next_permutation der STL (den du ja gezeigt hast) gerade nicht für beliebige Mengen funktioniert.

    Ich stelle eine Forderung an seine Implementierung. Was hat mein gepasteter Code damit überhaupt zu tun? Den nahm ich lediglich zum vorzeigen der Komplexität.
    Edit: Gut, ich hätte erwähnen sollen dass ich next_permutation nicht als tatsächlichen Kandidat vorschlug. Mea culpa.


  • Mod

    Ja, geht für beliebige Arten von Daten. 😕
    Verstehe ich da gerade richtig? Das ist irgendwie eine komische Anforderung.

    Welches ist die Reihenfolge?


  • Mod

    SeppJ schrieb:

    Welches ist die Reihenfolge?

    Offensichtlich wäre es nicht schlecht wenn die Permutationen in lexikographischer Reihenfolge durchlaufen werden.

    Verstehe ich da gerade richtig? Das ist irgendwie eine komische Anforderung.

    Mir geht es darum dass dein Algo kein Spezialisierter ist, der lediglich die Permutationen der ersten N natürlichen Zahlen ausgibt. Es soll ein allgemeiner Algo sein. Wenn deiner tatsächlich allgemeine ist, wie soll er dann den in meinem obigen Post in Einfachheit übertreffen?



  • Angenommen ihr bekommt in einem Test die Aufgabe diesen Algorithmus zu implementieren. Wie schwer findet ihr das ? Um das gings mir eigentlich 🙂
    Leicht, Schwer, Sauschwer



  • @StudiProf
    Kommt auf den Kenntnisstand der Schüler drauf an, und natürlich darauf wie lange sie dafür Zeit haben.
    Im ersten Semester von so ziemlich egal was würde ich die Frage schwer nennen. Für Informatiker im 2 Studienabschnitt ist sie eher mittel bis leicht.


  • Mod

    @SeppJ: Bekommen wir deinen Algo auch zu sehen? Oder muss das Meisterwerk erst patentiert werden? 😃
    Edit: Verdammt, das Internet hat mich ungeduldig gemacht.



  • Also ich vermute dass genau der
    https://www.c-plusplus.net/forum/p2447678#2447678
    gemeint war.

    Mir zumindest fällt nix einfacheres ein.
    Und wenn std::next_permutation für dich ne 2 ist, dann wundert es mich dass du das nicht als 1 durchgehen lässt.


  • Mod

    1 heißt "trivial". Das ist aber IMO kein trivialer Algo.



  • Das ist trivial. next_permutation ist vielleicht eine 2, aber einfach nur alle Permutationen ist eine 1.

    Hier ein Code im Anfängerstil:

    #include <iostream>
    #include <iterator>
    #include <algorithm>
    using namespace std;
    
    void permprint(int *arr, int size, int curr=0) {
    	if (curr+1 >= size) {
    		for (int i=0; i<size; ++i)
    			cout << arr[i] << ' ';
    		cout << '\n';
    	} else {
    		for (int i=curr; i<size; ++i) {
    			swap(arr[curr], arr[i]);
    			permprint(arr, size, curr+1);
    			swap(arr[curr], arr[i]);
    		}
    	}
    }
    
    int main() {
    	int arr[] = {1, 2, 3, 4};
    	permprint(arr, 4);
    }
    

  • Mod

    Ich möchte noch einmal unterstreichen:

    SeppJ schrieb:

    hustbaer schrieb:

    Funktioniert dein "einser" Algorithmus auch wenn es Duplikate in dem Array gibt?

    Kommt drauf an, welches Ergebnis du in dem Fall wünscht. Mein Algorithmus glaubt nicht an die Ununterscheidbarkeit gleicher Werte 😃

    Aufgrund der undeutlichen Fragestellung dachte ich, es würde etwas erwartet, das aus der Menge {1, 1, 2} die Ausgabe
    1 1 2
    1 2 1
    1 1 2
    1 2 1
    2 1 1
    2 1 1
    generiert. Fällt euch jetzt eine triviale Umsetzung ein, die wirklich ein 0 verdient?


Log in to reply