Generating permutations of a set (most efficiently)

by

This might be what you’re looking for.

    private static bool NextPermutation(int[] numList)
    {
        /*
         Knuths
         1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, the permutation is the last permutation.
         2. Find the largest index l such that a[j] < a[l]. Since j + 1 is such an index, l is well defined and satisfies j < l.
         3. Swap a[j] with a[l].
         4. Reverse the sequence from a[j + 1] up to and including the final element a[n].

         */
        var largestIndex = -1;
        for (var i = numList.Length - 2; i >= 0; i--)
        {
            if (numList[i] < numList[i + 1]) {
                largestIndex = i;
                break;
            }
        }

        if (largestIndex < 0) return false;

        var largestIndex2 = -1;
        for (var i = numList.Length - 1 ; i >= 0; i--) {
            if (numList[largestIndex] < numList[i]) {
                largestIndex2 = i;
                break;
            }
        }

        var tmp = numList[largestIndex];
        numList[largestIndex] = numList[largestIndex2];
        numList[largestIndex2] = tmp;

        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;
    }

More Related Contents:

  1. Where is likely the performance bug here? [closed]
  2. Best way to reverse a string
  3. Listing all permutations of a string/integer
  4. Does C# optimize the concatenation of string literals?
  5. What is the real overhead of try/catch in C#?
  6. When is optimization premature? [closed]
  7. Efficient Cartesian Product algorithm
  8. A better way to replace many strings – obfuscation in C#
  9. How to make an algorithm to get all column names from across tables that relations with their primary key in SQL Server and C#?
  10. Is there any alternate way of avoiding the Foreach loop? [closed]
  11. Most efficient way to concatenate strings?
  12. How to write a large buffer into a binary file in C++, fast?
  13. Virtual functions and performance – C++
  14. Swap two variables without using a temporary variable
  15. How to pass values across the pages in ASP.net without using Session
  16. For vs. Linq – Performance vs. Future
  17. Rounding DateTime objects
  18. What is quicker, switch on string or elseif on type?
  19. Most efficient way to insert Rows into MySQL Database
  20. File.Copy vs. Manual FileStream.Write For Copying File
  21. Performance of nested yield in a tree
  22. How to sort depended objects by dependency
  23. Do string literals get optimised by the compiler?
  24. True Unsafe Code Performance
  25. async await performance?
  26. What is the fastest way to compute sin and cos together?
  27. Why is this faster on 64 bit than 32 bit?
  28. When to use pointers in C#/.NET?
  29. When to change the Generate Serialization Assembly value?
  30. Setting properties via object initialization or not : Any difference ?

Leave a Comment