W
SeppJ schrieb:
Das ist schlicht keine Sortierung, sondern eine Art Puzzlespiel. Mit einem Sortieralgorithmus kannst du das nicht lösen.
.. Sortierung hin oder her; es handelt sich in jedem Fall um eine topologische Sortierung. Das heißt aber auch, dass ein Graph besser geeignet wäre, das Ergebnis aufzunehmen als ein sequentieller Container.
Bogo-Sort liefert übrigens ganz ordentliche Ergebnisse. Probiert's mal selber aus:
#include <algorithm>
#include <list>
#include <iostream>
#include <random>
struct Node
{
int left_;
int right_;
};
std::ostream& operator<<( std::ostream& out, const Node& nd )
{
return out << "(" << nd.left_ << "," << nd.right_ << ")";
}
template< typename I, typename Pred >
void bogo_sort( I from, I to, Pred comp )
{
std::ptrdiff_t const size = std::distance( from, to );
if( size <= 1 )
return;
std::mt19937 rng;
std::uniform_int_distribution< std::ptrdiff_t > dist( 0, size-1 );
typedef typename std::iterator_traits< I >::value_type V;
while( std::adjacent_find( from, to, [comp]( const V& a, const V& b ) { return !comp( a, b ); } ) != to )
{
auto j = from;
std::advance( j, dist( rng ) ); // zufällig ...
auto k = j;
if( ++k == to )
k = from;
std::iter_swap( j, k ); // ... zwei benachbarte Elemente vertauschen
}
}
int main()
{
using namespace std;
list< Node > lst( { {1,2}, {2,5}, {3,2}, {2,3}, {3,1} } );
for( auto e: lst )
cout << e << " ";
cout << endl;
bogo_sort( begin(lst), end(lst), []( Node a, Node b ) { return a.right_ == b.left_; } );
for( auto e: lst )
cout << e << " ";
cout << endl;
return 0;
}
.. zu beachten ist hier der Unterschied in der Bedeutung des Predikats ' comp '. Beim klassischen std::sort ist die Sequenz sortiert, wenn für zwei aufeinander folgende Elemente A und B gilt, dass comp(B,A)==false ist. Bei der von mir gewählten Implementierung von Bogo-Sort ist die Sequenz sortiert, wenn comp(A,B)==true ist.
Gruß
Werner
