Permutation of Array
-
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.
-
@SeppJ: Listet deiner denn alle in Reihenfolge auf? Und funktioniert für beliebige Mengen?
-
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.
-
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 ichnext_permutation
nicht als tatsächlichen Kandidat vorschlug. Mea culpa.
-
Ja, geht für beliebige Arten von Daten.
Verstehe ich da gerade richtig? Das ist irgendwie eine komische Anforderung.Welches ist die Reihenfolge?
-
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.
-
@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 wennstd::next_permutation
für dich ne 2 ist, dann wundert es mich dass du das nicht als 1 durchgehen lässt.
-
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); }
-
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!
-
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.
-
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; }