Effiziente Codierungshilfe

Question

Ich schreibe gerade Code in C++, um alle möglichen Permutationen von 6 ganzen Zahlen zu finden und die beste Permutation zu speichern (d. H. Diejenige, deren Summe einem gegebenen Wert am nächsten kommt).

Ich versuche, diesen Code so effizient wie möglich zu schreiben und würde jeden Rat oder Beispiele schätzen.

Ich erwog, die Ganzzahlen in einem Array zu speichern und die Permutationen mit Zeigern innerhalb einer Schleife durchzuführen. Ist das ein guter Ansatz?

Answer 1

Sie schon gedacht dieses für Sie:

#include <algorithm> 

int ra[6] = { 1, 2, 3, 4, 5, 6 }; 

do { 
    // whatever 
} while (std::next_permutation(ra, ra+6)); 

Beachten Sie, dass die Elemente in aufsteigender Reihenfolge starten haben (im Vergleich über Operator <), sonst wird die Schleife beenden, bevor Sie alle gesehen haben Permutation. Einzelheiten finden Sie unter http://en.cppreference.com/w/cpp/algorithm/next_permutation.

Es ist wahrscheinlich nicht der schnellste Laufzeit möglich geben, denn bei jedem Schritt den Array hat, zu überprüfen, was zu arbeiten, zu ändern. Aber es ist sicherlich der effizienteste Aufwand für Programmierer, und ohne den Compiler und die Plattform zu kennen, ist es ohnehin nicht möglich, die Nested-Loop-Ansätze zu optimieren.

Answer 2

Werfen Sie einen Blick auf diese ausgezeichnete Post @Coding the Wheel: Exhaustively Enumerating Combinations and Permutations in Code. Es hat vollständigen Code und wurde von einem Kollegen SO'r geschrieben, es sollte genug sein, um Sie auf dem richtigen Weg zu bekommen.

Answer 3

Unter der Annahme, doppelte Zahlen sind kein Problem, gibt es n! Perationen von n ganzen Zahlen (jeweils n genommen). Also egal, was Sie tun, Ihr Algorithmus wird faktorielle Zeitverhalten haben (O (n^n)). Wenn also n groß wird, wird es langsam sein. Es tut uns leid.

Es gibt tatsächlich diese auf der permutation wikipedia Seite zu tun Algorithmen.

Answer 4

I wurde unter Berücksichtigung der ganzen Zahlen in einem Array zu speichern und Durchführen die Permutationen Zeiger innerhalb einer Schleife. Ist das ein guter Ansatz?

Nein, es ist nicht wirklich ein guter Ansatz. Anstatt Zeiger auf Elemente im Array zu vertauschen, tauschen Sie stattdessen einfach die Elemente im Array aus. Die Zeiger wären nur ein zusätzlicher Schritt der Umleitung ohne wirklichen Zweck.