より大きなデータセットの順列生成アルゴリズムを最適化するにはどうすればよいでしょうか?

順列生成アルゴリズムの最適化

セットの順列を効率的に生成することは、コンピューター サイエンスにおける古典的な問題です。提供されたコードは効率的ですが、セットが大きい場合には依然としてかなりの時間がかかる可能性があります。

Knuth のアルゴリズムを使用すると、時間計算量が O(n) の 1 つの改善が可能です。ここで、n は次のサイズです。セット。 Knuth のアルゴリズムに基づいた改訂版は次のとおりです。

public static bool NextPermutation(int[] numList)
{
    // Find the largest index j such that a[j] < a[j + 1]
    var largestIndex = -1;
    for (var i = numList.Length - 2; i >= 0; i--)
    {
        if (numList[i] < numList[i + 1])
        {
            largestIndex = i;
            break;
        }
    }

    // If there's no such index, we have reached the last permutation
    if (largestIndex < 0) return false;

    // Find the largest index l such that a[j] < a[l]
    var largestIndex2 = -1;
    for (var i = numList.Length - 1; i >= 0; i--)
    {
        if (numList[largestIndex] < numList[i])
        {
            largestIndex2 = i;
            break;
        }
    }

    // Swap a[j] with a[l]
    var tmp = numList[largestIndex];
    numList[largestIndex] = numList[largestIndex2];
    numList[largestIndex2] = tmp;

    // Reverse the sequence from a[j + 1] up to and including the final element a[n]
    for (int i = largestIndex + 1, j = numList.Length - 1; i < j; i++, j--)
    {
        tmp = numList[i];
        numList[i] = numList[j];
        numList[j] = tmp;
    }

    return true;
}

この最適化されたアルゴリズムは、昇順で次の順列を見つけるためのより効率的な方法を使用します。一般に、特に大規模なセットの場合は高速です。ただし、さらに効率を高めるには、効率的な順列生成用に特別に設計された言語またはライブラリの使用を検討してください。

以上がより大きなデータセットの順列生成アルゴリズムを最適化するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。