Генерация перестановок

Этот класс, написанный на С#, реализует алгоритм генерации перестановок в лексикографическом порядке. Класс Permutations генерирует все возможные перестановки элементов вектора V. Метод NextPermutation выполняет очередную перестановку элементов V. Если метод возвращает false, значит все возможные перестановки проделаны (общее число перестановок равно n!, где n — число элементов V). Исходное состояние V считается первой перестановкой.

public class Permutations

{

    int[] st;

    object[] v;

    public Permutations(object[] V)

    {

        v = V;

        st = new int[v.Length];

        for (int i = 0; i < st.Length; )

            st[i++] = 0;

    }

    void Swap(ref Object a, ref Object b)

    {

        Object t = a;

        a = b;

        b = t;

    }

    void Reverse(object[] v, int start)

    {

        for (int i = 0; i < (v.Length - start) / 2; i++)

            Swap(ref v[start + i], ref v[v.Length - 1 - i]);

    }

    public bool NextPermutation()

    {

        if (v.Length < 2) return false;

        int pos = pos = v.Length - 2;

        while (pos >= 0)

        {

            if (st[pos] < st.Length - 1 - pos)

            {

                Reverse(v, pos + 1);

                for (int i = pos + 1; i < v.Length; )

                    st[i++] = 0;

                st[pos]++;

                Swap(ref v[pos], ref v[pos + st[pos]]);

                return true;

            }

            pos--;

        }

        return false;

    }

}

(c) 2007 Андрей Боровский, контакты: anb@symmetrica.net