Steinhaus-Johnson-Trotter-Algorithmus
Der Steinhaus-Johnson-Trotter-Algorithmus oder der Johnson-Trotter-Algorithmus, auch einfache Änderungen genannt, ist ein Algorithmus, der nach Hugo Steinhaus, Selmer M. Johnson und Hale Trotter benannt ist und alle Permutationen von Elementen erzeugt. Jede Permutation in der von ihr erzeugten Sequenz unterscheidet sich von der vorherigen Permutation durch Vertauschen zweier benachbarter Elemente der Sequenz. Entsprechend findet dieser Algorithmus einen Hamiltonweg im Permutaeder.
Diese Methode war bereits den englischen Change-Ringern des 17. Jahrhunderts bekannt und Robert Sedgewick nennt sie 1977 „den vielleicht bekanntesten Permutations-Aufzählungsalgorithmus“. Er ist nicht nur einfach und rechnerisch effizient, sondern hat auch den Vorteil, dass nachfolgende Berechnungen der von ihm erzeugten Permutationen beschleunigt werden können, da diese Permutationen einander so ähnlich sind.