4

std:next_permutation の実装方法に興味があったので、gnu libstdc++ 4.7 バージョンを抽出し、識別子とフォーマットをサニタイズして、次のデモを作成しました...

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

template<typename It>
bool next_permutation(It begin, It end)
{
    if (begin == end)
            return false;

    It i = begin;
    ++i;
    if (i == end)
            return false;

    i = end;
    --i;

    while (true)
    {
            It j = i;
            --i;

            if (*i < *j)
            {
                    It k = end;

                    while (!(*i < *--k))
                            /* pass */;

                    iter_swap(i, k);
                    reverse(j, end);
                    return true;
            }

            if (i == begin)
            {
                    reverse(begin, end);
                    return false;
            }
    }

}

  int main()
 {
             vector<int> v = { 1, 2, 3, 4 };

    do
    {
            for (int i = 0; i < 4; i++)
            {
                    cout << v[i] << " ";
            }
            cout << endl;
    }
    while (::next_permutation(v.begin(), v.end()));

}

私の質問は:

while (!(*i < *--k))
  /* Iterating linearly */;

[i+1 , end) からのシーケンスが降順であるため、単純な線形反復の代わりにバイナリ検索を実行できないのはなぜですか? そうすれば、検索の効率が上がります。「algorithm.h」の標準関数は、パフォーマンスと効率の向上につながるようなことをどのように無視できますか? 誰か説明してください...

4

1 に答える 1

6

15 個を処理する必要があるため、15 個を超える要素 (実際にはそれよりも少ない要素) で並べ替えたい配列はめったにありません。> 10^12 の異なる順列。また、このような小さなサイズのバイナリ検索を使用した配列の場合、単純な線形検索よりも効率が低下します。

于 2013-06-20T11:42:50.650 に答える