第1053回比較関数が全順序則を満たさない時 一番面白い値を返すsort関数を作ったやつが最強選手権

比較関数が全順序則を満たさない時 一番面白い値を返すsort関数を作ったやつが最強選手権とは

与えられた比較関数が全順序則を満たさない時 一番面白い値を返すsort関数を作ったやつが最強になる選手権である

レギュレーション

• Listと比較関数を受け取りListを返すsort関数を実装する
• 比較関数が全順序則を満たす場合sortedなListを返すこと
• 比較関数が全順序則を満たさない場合、面白い値を返すとポイントが高い

sortされてない値が返る

それはそう。ところで「比較関数が全順序じゃない」って話においてsortedであるとはいったいどういう状態なのだろうか
https://wandbox.org/permlink/WHYlCpU7tyUmXWes

std::vector<int> sort(std::vector<int> const&in, std::function<bool(int,int)> const&comp){
    auto tmp = in;
    std::sort(tmp.begin(),tmp.end(),comp);
    return  tmp;
}

int main(){
    assert ((std::vector{0,1,2,3,4,10,5,6,7,8,9} == sort({9,8,7,6,5,10,4,3,2,1,0}, [](auto l,auto r){ return l<r || r < 7; })) );
    // 正しく全順序なルールを与えた場合はsortedな値が返る
    assert ((std::vector{0,1,2,3,4,5,6,7,8,9,10} == sort({9,8,7,6,5,10,4,3,2,1,0}, [](auto l,auto r){ return l<r;})) );
}

無限ループに突入し、値が返らない

sortアルゴリズムがボゴソートだった場合、無限ループに陥り関数から値が返らない可能性がある
https://wandbox.org/permlink/enTcBpJx9Nv312QC

std::vector<int> sort(std::vector<int> const&in, std::function<bool(int,int)> const&comp){
    // ボゴソート
    auto tmp = in;
    std::mt19937 engine(0);
    while(1){
        std::shuffle(tmp.begin(), tmp.end(), engine);
        if(std::is_sorted(tmp.begin(),tmp.end(),comp)){
            break;
        }
    }
    return  tmp;
}

int main(){
    // 無限ループに突入する。実行してはいけない
    //assert((std::vector{1,2,3,4,5} == sort({5,4,3,2,1},[](auto,auto){ return true; }) ));

    // ちゃんと停止する
    assert((std::vector{1,2,3,4,5} == sort({5,4,3,2,1},[](auto l,auto r){ return l<r; }) ));
}

入力に含まれていない値が返り値に含まれる

バイトニックソートなど、特定の要素数しか扱えないsortアルゴリズムも存在する
その場合、ダミー値を入れることでアルゴリズムを利用可能にすることができるのだが
このとき全順序則が正しくないとダミー値が戻り値に含まれうる

void merge(std::span<unsigned> v, bool reverse,std::function<bool(unsigned,unsigned)> const&comp){
    auto s = v.size();
    if(s <= 1){
        return;
    }
    for(std::size_t i = 0 ;i < s/2; ++i){
        if(comp(v[i], v[i+s/2]) == reverse){
            std::swap(v[i], v[i+s/2]);
        }
    }
    merge(v.subspan(0,s/2),reverse,comp);
    merge(v.subspan(s/2,s/2),reverse,comp);
}

void sort_impl(std::span<unsigned> v, bool reverse,std::function<bool(unsigned,unsigned)> const&comp){
    auto s = v.size();
    if(s <= 1){
        return;
    }
    sort_impl(v.subspan(0,s/2),false,comp); // リストの前半を昇順にsort
    sort_impl(v.subspan(s/2,s/2),true,comp);  // リストの後半を降順にsort
    merge(v,reverse,comp);
}

std::vector<unsigned> sort(std::vector<unsigned> const&in, std::function<bool(unsigned,unsigned)> const&comp){
    std::vector<unsigned> tmp = in;
    std::size_t pad_num = std::bit_ceil(in.size()) - in.size(); // バイトニックソートは2^n 個のListしかsortできないのでダミーデータを突っ込む
    tmp.insert(tmp.end(), pad_num, 0);
    sort_impl(tmp,false,comp);
    tmp.erase(tmp.begin(),tmp.begin()+pad_num); // 0 ダミーデータを取り除く。0を入れたのは最小値だからなんだけど全順序則が壊れた世界で最小値とは
    return tmp;   
}

int main(){
    // この0どっからきた？？？？？
    assert((std::vector<unsigned>{0, 1, 3, 3, 4, 4} == sort({1,2,3,4,4,3}, [](auto l,auto r){ return l<r || l==2 ; })));
    // 正しく全順序なルールを与えた場合はsortedな値が返る
    assert((std::vector<unsigned>{1,2, 3, 3, 4, 4} == sort({1,2,3,4,4,3}, [](auto l,auto r){ return l<r ; })));
}

まとめ

全順序則入れろって言ってる関数にはちゃんと全順序則入れよう