On Wednesday, 25 March 2015 at 20:09:53 UTC, bearophile wrote:
Dennis Ritchie:
A more effective solution for C ++:
#include <iostream>
#include <vector>
#include <range/v3/all.hpp>
int main() {
using namespace ranges;
auto rng = istream<int>( std::cin )
| to_vector
| action::sort
| view::group_by( std::equal_to<int>() )
| copy
| action::stable_sort( []( const auto& e1, const
auto& e2 ) { return distance( e1 ) < distance( e2 ); } );
std::cout << ( rng );
}
This is still not very efficient (perhaps the last sorting has
to be stable):
void main() {
import std.stdio, std.algorithm, std.typecons, std.array;
[7, 5, 7, 3, 3, 5, 3, 3, 0, 3, 1, 1, 5, 1, 1, 1, 2, 2, 8,
5, 8, 8]
.sort()
.groupBy!((a, b) => a == b)
.map!array
.array
.sort!q{a.length > b.length}
.joiner
.writeln;
}
Bye,
bearophile
5. An efficient version would be to count the integers by using
an associative array (or a redBlackTree for guaranteed upper
bound) and then use these. It is O (n) time and memory spent in
precalculation phase and O (n log n) time for sorting. Looks
like there is no way to write that as a chain of transforms, but
many optimizations do require manual labor.
-----
import std.algorithm, std.conv, std.range, std.stdio;
void main () {
auto arr = [7, 5, 7, 3, 3, 5, 3, 3, 0, 3, 1, 1, 5, 1,
1, 1, 2, 2, 8, 5, 8, 8];
int [int] counts;
foreach (e; arr) {
counts[e]++;
}
arr.multiSort !((a, b) => counts[a] > counts[b], (a, b) => a
< b);
arr.map !(to !(string))
.join (" ")
.writeln;
// prints 1 1 1 1 1 3 3 3 3 3 5 5 5 5 8 8 8 2 2 7 7 0
}
-----
Also, some of my previously posted codes do not compile under
2.066 or earlier unless you replace .join (' ') with .join (" ")
there.
