Générer des permutations d'un ensemble (le plus efficacement possible)

Question

Je voudrais générer toutes les permutations d'un ensemble (une collection), comme ceci :

Collection: 1, 2, 3
Permutations: {1, 2, 3}
              {1, 3, 2}
              {2, 1, 3}
              {2, 3, 1}
              {3, 1, 2}
              {3, 2, 1}

Il ne s'agit pas d'une question de "comment", en général, mais plutôt de la manière la plus efficace. En outre, je ne voudrais pas générer TOUTES les permutations et les renvoyer, mais seulement générer une seule permutation à la fois, et ne continuer que si nécessaire (un peu comme les itérateurs - que j'ai également essayés, mais qui se sont avérés moins efficaces).

J'ai testé de nombreux algorithmes et approches et j'ai abouti à ce code, qui est le plus efficace de ceux que j'ai essayés :

public static bool NextPermutation<T>(T[] elements) where T : IComparable<T>
{
    // More efficient to have a variable instead of accessing a property
    var count = elements.Length;

    // Indicates whether this is the last lexicographic permutation
    var done = true;

    // Go through the array from last to first
    for (var i = count - 1; i > 0; i--)
    {
        var curr = elements[i];

        // Check if the current element is less than the one before it
        if (curr.CompareTo(elements[i - 1]) < 0)
        {
            continue;
        }

        // An element bigger than the one before it has been found,
        // so this isn't the last lexicographic permutation.
        done = false;

        // Save the previous (bigger) element in a variable for more efficiency.
        var prev = elements[i - 1];

        // Have a variable to hold the index of the element to swap
        // with the previous element (the to-swap element would be
        // the smallest element that comes after the previous element
        // and is bigger than the previous element), initializing it
        // as the current index of the current item (curr).
        var currIndex = i;

        // Go through the array from the element after the current one to last
        for (var j = i + 1; j < count; j++)
        {
            // Save into variable for more efficiency
            var tmp = elements[j];

            // Check if tmp suits the "next swap" conditions:
            // Smallest, but bigger than the "prev" element
            if (tmp.CompareTo(curr) < 0 && tmp.CompareTo(prev) > 0)
            {
                curr = tmp;
                currIndex = j;
            }
        }

        // Swap the "prev" with the new "curr" (the swap-with element)
        elements[currIndex] = prev;
        elements[i - 1] = curr;

        // Reverse the order of the tail, in order to reset it's lexicographic order
        for (var j = count - 1; j > i; j--, i++)
        {
            var tmp = elements[j];
            elements[j] = elements[i];
            elements[i] = tmp;
        }

        // Break since we have got the next permutation
        // The reason to have all the logic inside the loop is
        // to prevent the need of an extra variable indicating "i" when
        // the next needed swap is found (moving "i" outside the loop is a
        // bad practice, and isn't very readable, so I preferred not doing
        // that as well).
        break;
    }

    // Return whether this has been the last lexicographic permutation.
    return done;
}

Son utilisation consisterait à envoyer un tableau d'éléments, et à recevoir en retour un booléen indiquant s'il s'agit de la dernière permutation lexicographique ou non, ainsi qu'à faire passer le tableau à la permutation suivante.

Exemple d'utilisation :

var arr = new[] {1, 2, 3};

PrintArray(arr);

while (!NextPermutation(arr))
{
    PrintArray(arr);
}

Le problème est que je ne suis pas satisfait de la vitesse du code.

L'itération sur toutes les permutations d'un tableau de taille 11 prend environ 4 secondes. Bien que cela puisse être considéré comme impressionnant, puisque la quantité de permutations possibles d'un ensemble de taille 11 est 11! qui est de près de 40 millions.

Logiquement, avec un tableau de taille 12, cela prendra environ 12 fois plus de temps, puisque 12! est 11! * 12 Avec un tableau de taille 13, il faudra environ 13 fois plus de temps qu'avec un tableau de taille 12, et ainsi de suite.

Vous pouvez donc facilement comprendre comment, avec un tableau de taille 12 et plus, il faut vraiment beaucoup de temps pour passer en revue toutes les permutations.

Et j'ai la ferme conviction que je peux réduire considérablement ce temps (sans passer à un autre langage que C# - car l'optimisation du compilateur est vraiment très efficace, et je doute de pouvoir optimiser aussi bien, manuellement, en Assembly).

Quelqu'un connaît-il un autre moyen de le faire plus rapidement ? Avez-vous une idée sur la façon de rendre l'algorithme actuel plus rapide ?

Notez que je ne veux pas utiliser une bibliothèque ou un service externe pour faire cela - je veux avoir le code lui-même et je veux qu'il soit aussi efficace qu'il est humainement possible.

Answer 1

C'est peut-être ce que vous cherchez.

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

Answer 2

Si vous pouvez le traiter en C et le traduire dans la langue de votre choix, vous ne pouvez pas aller beaucoup plus vite, car le temps sera dominé par les éléments suivants print :

void perm(char* s, int n, int i){
  if (i >= n-1) print(s);
  else {
    perm(s, n, i+1);
    for (int j = i+1; j<n; j++){
      swap(s[i], s[j]);
      perm(s, n, i+1);
      swap(s[i], s[j]);
    }
  }
}

perm("ABC", 3, 0);

Answer 3

L'algorithme de permutation le plus rapide que je connaisse est l'algorithme QuickPerm.
Voici l'implémentation, elle utilise le retour de rendement afin que vous puissiez itérer un à la fois comme requis.

Code :

public static IEnumerable<IEnumerable<T>> QuickPerm<T>(this IEnumerable<T> set)
    {
        int N = set.Count();
        int[] a = new int[N];
        int[] p = new int[N];

        var yieldRet = new T[N];

        List<T> list = new List<T>(set);

        int i, j, tmp; // Upper Index i; Lower Index j

        for (i = 0; i < N; i++)
        {
            // initialize arrays; a[N] can be any type
            a[i] = i + 1; // a[i] value is not revealed and can be arbitrary
            p[i] = 0; // p[i] == i controls iteration and index boundaries for i
        }
        yield return list;
        //display(a, 0, 0);   // remove comment to display array a[]
        i = 1; // setup first swap points to be 1 and 0 respectively (i & j)
        while (i < N)
        {
            if (p[i] < i)
            {
                j = i%2*p[i]; // IF i is odd then j = p[i] otherwise j = 0
                tmp = a[j]; // swap(a[j], a[i])
                a[j] = a[i];
                a[i] = tmp;

                //MAIN!

                for (int x = 0; x < N; x++)
                {
                    yieldRet[x] = list[a[x]-1];
                }
                yield return yieldRet;
                //display(a, j, i); // remove comment to display target array a[]

                // MAIN!

                p[i]++; // increase index "weight" for i by one
                i = 1; // reset index i to 1 (assumed)
            }
            else
            {
                // otherwise p[i] == i
                p[i] = 0; // reset p[i] to zero
                i++; // set new index value for i (increase by one)
            } // if (p[i] < i)
        } // while(i < N)
    }

Answer 4

Voici l'implémentation la plus rapide à laquelle j'ai abouti :

public class Permutations
{
    private readonly Mutex _mutex = new Mutex();

    private Action<int[]> _action;
    private Action<IntPtr> _actionUnsafe;
    private unsafe int* _arr;
    private IntPtr _arrIntPtr;
    private unsafe int* _last;
    private unsafe int* _lastPrev;
    private unsafe int* _lastPrevPrev;

    public int Size { get; private set; }

    public bool IsRunning()
    {
        return this._mutex.SafeWaitHandle.IsClosed;
    }

    public bool Permutate(int start, int count, Action<int[]> action, bool async = false)
    {
        return this.Permutate(start, count, action, null, async);
    }

    public bool Permutate(int start, int count, Action<IntPtr> actionUnsafe, bool async = false)
    {
        return this.Permutate(start, count, null, actionUnsafe, async);
    }

    private unsafe bool Permutate(int start, int count, Action<int[]> action, Action<IntPtr> actionUnsafe, bool async = false)
    {
        if (!this._mutex.WaitOne(0))
        {
            return false;
        }

        var x = (Action)(() =>
                             {
                                 this._actionUnsafe = actionUnsafe;
                                 this._action = action;

                                 this.Size = count;

                                 this._arr = (int*)Marshal.AllocHGlobal(count * sizeof(int));
                                 this._arrIntPtr = new IntPtr(this._arr);

                                 for (var i = 0; i < count - 3; i++)
                                 {
                                     this._arr[i] = start + i;
                                 }

                                 this._last = this._arr + count - 1;
                                 this._lastPrev = this._last - 1;
                                 this._lastPrevPrev = this._lastPrev - 1;

                                 *this._last = count - 1;
                                 *this._lastPrev = count - 2;
                                 *this._lastPrevPrev = count - 3;

                                 this.Permutate(count, this._arr);
                             });

        if (!async)
        {
            x();
        }
        else
        {
            new Thread(() => x()).Start();
        }

        return true;
    }

    private unsafe void Permutate(int size, int* start)
    {
        if (size == 3)
        {
            this.DoAction();
            Swap(this._last, this._lastPrev);
            this.DoAction();
            Swap(this._last, this._lastPrevPrev);
            this.DoAction();
            Swap(this._last, this._lastPrev);
            this.DoAction();
            Swap(this._last, this._lastPrevPrev);
            this.DoAction();
            Swap(this._last, this._lastPrev);
            this.DoAction();

            return;
        }

        var sizeDec = size - 1;
        var startNext = start + 1;
        var usedStarters = 0;

        for (var i = 0; i < sizeDec; i++)
        {
            this.Permutate(sizeDec, startNext);

            usedStarters |= 1 << *start;

            for (var j = startNext; j <= this._last; j++)
            {
                var mask = 1 << *j;

                if ((usedStarters & mask) != mask)
                {
                    Swap(start, j);
                    break;
                }
            }
        }

        this.Permutate(sizeDec, startNext);

        if (size == this.Size)
        {
            this._mutex.ReleaseMutex();
        }
    }

    private unsafe void DoAction()
    {
        if (this._action == null)
        {
            if (this._actionUnsafe != null)
            {
                this._actionUnsafe(this._arrIntPtr);
            }

            return;
        }

        var result = new int[this.Size];

        fixed (int* pt = result)
        {
            var limit = pt + this.Size;
            var resultPtr = pt;
            var arrayPtr = this._arr;

            while (resultPtr < limit)
            {
                *resultPtr = *arrayPtr;
                resultPtr++;
                arrayPtr++;
            }
        }

        this._action(result);
    }

    private static unsafe void Swap(int* a, int* b)
    {
        var tmp = *a;
        *a = *b;
        *b = tmp;
    }
}

Utilisation et performance des tests :

var perms = new Permutations();

var sw1 = Stopwatch.StartNew();

perms.Permutate(0,
                11,
                (Action<int[]>)null); // Comment this line and...
                //PrintArr); // Uncomment this line, to print permutations

sw1.Stop();
Console.WriteLine(sw1.Elapsed);

Méthode d'impression :

private static void PrintArr(int[] arr)
{
    Console.WriteLine(string.Join(",", arr));
}

Aller plus loin :

Je n'ai pas pensé à cela pendant très longtemps, donc je ne peux expliquer mon code qu'à moitié, mais voici l'idée générale :

1. Les permutations ne sont pas lexicographiques - cela me permet d'effectuer pratiquement moins d'opérations entre les permutations.
2. L'implémentation est récursive, et lorsque la taille de la "vue" est de 3, elle saute la logique complexe et se contente d'effectuer 6 échanges pour obtenir les 6 permutations (ou sous-permutations, si vous voulez).
3. Comme les permutations ne sont pas dans un ordre lexicographique, comment puis-je décider de l'élément à amener au début de la "vue" actuelle (sous permutation) ? Je garde une trace des éléments qui ont déjà été utilisés comme "starters" dans l'appel récursif de la sous-permutation actuelle et je recherche simplement de manière linéaire un élément qui n'a pas été utilisé dans la queue de mon tableau.
4. L'implémentation ne concerne que les entiers, donc pour permuter sur une collection générique d'éléments, il suffit d'utiliser la classe Permutations pour permuter les indices au lieu de votre collection réelle.
5. Le Mutex n'est là que pour éviter que les choses ne se gâtent lorsque l'exécution est asynchrone (remarquez que vous pouvez passer un paramètre UnsafeAction qui obtiendra à son tour un pointeur vers le tableau permuté. Vous ne devez pas changer l'ordre des éléments dans ce tableau (pointeur) ! Si vous voulez le faire, vous devez copier le tableau dans un tableau tmp ou simplement utiliser le paramètre d'action sûre qui s'en occupe pour vous - le tableau passé est déjà une copie).

Note :

Je n'ai aucune idée de la qualité réelle de cette mise en œuvre - je n'y ai pas touché depuis si longtemps. Testez-la et comparez-la à d'autres implémentations par vous-même, et faites-moi part de vos commentaires !

Profitez-en.

Answer 5

Voici un chercheur de permutation générique qui va parcourir chaque permutation d'une collection et appeler une fonction d'évaluation. Si la fonction d'évaluation renvoie vrai (elle a trouvé la réponse qu'elle cherchait), le chercheur de permutations arrête le traitement.

public class PermutationFinder<T>
{
    private T[] items;
    private Predicate<T[]> SuccessFunc;
    private bool success = false;
    private int itemsCount;

    public void Evaluate(T[] items, Predicate<T[]> SuccessFunc)
    {
        this.items = items;
        this.SuccessFunc = SuccessFunc;
        this.itemsCount = items.Count();

        Recurse(0);
    }

    private void Recurse(int index)
    {
        T tmp;

        if (index == itemsCount)
            success = SuccessFunc(items);
        else
        {
            for (int i = index; i < itemsCount; i++)
            {
                tmp = items[index];
                items[index] = items[i];
                items[i] = tmp;

                Recurse(index + 1);

                if (success)
                    break;

                tmp = items[index];
                items[index] = items[i];
                items[i] = tmp;
            }
        }
    }
}

Voici une mise en œuvre simple :

class Program
{
    static void Main(string[] args)
    {
        new Program().Start();
    }

    void Start()
    {
        string[] items = new string[5];
        items[0] = "A";
        items[1] = "B";
        items[2] = "C";
        items[3] = "D";
        items[4] = "E";
        new PermutationFinder<string>().Evaluate(items, Evaluate);
        Console.ReadLine();
    }

    public bool Evaluate(string[] items)
    {
        Console.WriteLine(string.Format("{0},{1},{2},{3},{4}", items[0], items[1], items[2], items[3], items[4]));
        bool someCondition = false;

        if (someCondition)
            return true;  // Tell the permutation finder to stop.

        return false;
    }
}