Permutation of Array


  • 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?



  • SeppJ schrieb:

    Fällt euch jetzt eine triviale Umsetzung ein, die wirklich ein 0 verdient?

    Mir nicht.
    Ich wüsste nicht wie man den von Arcoth bzw. auch trivialo implementierten Algorithmus noch weiter vereinfachen könnte.
    Will sehen! 🙂


  • Mod

    hustbaer schrieb:

    Ich wüsste nicht wie man den von Arcoth bzw. auch trivialo implementierten Algorithmus noch weiter vereinfachen könnte.
    Will sehen! 🙂

    Ich meine den von trivialo bzw. den zweiten von Arcoth. Das ist in meinen Augen wesentlich einfacher als die Nummer 1 von Arcoth und verdient eine 1 oder weniger.



  • Also ich hab nen Bachelor in Informatik und ich bin zu blöd den Algorithmus hinzukriegen. Also einfach ist das sicher nicht.



  • @SeppJ
    Ich dachte dass du was anderes meinst, da dieser Algorithmus ja bereits 2x gepostet wurde bevor du gefragt hast ob uns was einfaches einfällt.

    Dass Arcoth den für "schwerer als 1" hält hat er ja schon geschreiben.

    Ich würde ihm ne 1 geben. Ne 0 finde ich übertrieben.


  • Mod

    hustbaer schrieb:

    @SeppJ
    Ich dachte dass du was anderes meinst, da dieser Algorithmus ja bereits 2x gepostet wurde bevor du gefragt hast ob uns was einfaches einfällt.

    trivialo hat geantwortet, während ich meine Antwort formuliert habe und Arcoths iter_swap-Code habe ich nicht wirklich gelesen. Zu anstrengend.

    Wenn man will, kann man die gleiche Idee auch noch einfacher formulieren, wobei es aber für den Computer aufwändiger wird:

    template<typename Vector> void print_combinations(Vector data, Vector history)
    {
      if (data.empty())
        {
          for (const auto& e: history)
            std::cout << e << '\t';
          std::cout << '\n';
        }
      else
        {
          for (std::size_t i = 0; i < data.size(); ++i)
            {
              auto new_data = data;
              auto new_history = history;
              new_data.erase(new_data.begin() + i);
              new_history.push_back(data[i]);
              print_combinations(new_data, new_history);
            }
        }
    }
    


  • Hallo,

    ich hab jetzt mal den Algo gefunden . Ist der gut ? Leider versteh ich den überhaupt nicht. Allgemein hab ich große Probleme mit Rekursion. Sollte man sich das am besten mathematisch herleiten ?

    void permute(int k,int size){
        int i;
    
        if (k==0)
            printArray(size);
        else{
            for (i=k-1;i>=0;i--){
                swap(i,k-1);
                permute(k-1,size);
                swap(i,k-1);
            }
        }
    
        return;
    }
    

  • Mod

    NullPlanProf schrieb:

    ich hab jetzt mal den Algo gefunden .

    Also abgeschrieben? Und noch dazu exakt den gleichen, der jetzt schon 2.5 Mal in diesem Thread genannt wurde? Ich habe ja die Ausrede, nicht alle Antworten zu lesen, weil es nicht mein Thread ist. Du nicht. Schön zu wissen, dass hier anscheinend sämtliche Antworten für die Katz' sind.

    Ist der gut ?

    Kommt drauf an, was wirklich gefragt ist.

    Leider versteh ich den überhaupt nicht.

    Tja.

    Allgemein hab ich große Probleme mit Rekursion.

    Tja.

    Sollte man sich das am besten mathematisch herleiten ?

    Nein, nicht in dem Sinne, wie man Rekursion in der Mathematik behandelt.

    8/10 auf der Blurryskala.


Anmelden zum Antworten