Два алгоритма генерации сочетаний без повторений

Оба алгоритма работают с вектором произвольных объектов длин n. На каждой итерации возвращается вектор из m элементов, содержащий очередное сочетание из n по m. Оба алгоритма реализованы на C#. Рассмотрим первый вариант:

    public class Combinations
    {
        int[] counter;
        uint m, n;
        object[] v;

        public Combinations(ref object[] v, uint m, uint n)
        {
            if (m > n)
                throw new Exception("m не может быть больше n");
            this.v = v;
            this.m = m;
            this.n = n;
            counter = new int[m];
            for (int i = 0; i < counter.Length; i++)
                counter[i] = i;
        }

       public bool FirstCombination(out object[] outv)
        {
            outv = new object[m];
            for (uint i = 0; i < m; i++)
                outv[i] = v[counter[i]];
            return (m == n) || (m == 0) ? false : true;
        }

        public bool NextCombination(out object[] outv)
        {
            if (counter[m - 1] < n – 1)
                counter[m – 1]++;
            else
            {
                for (uint i = m - 2; i >= 0; i--)
                {
                    if (counter[i] < n - m + I)
                    {
                        counter[i]++;
                        for (uint j = i + 1; j < m; j++)
                            counter[j] = counter[j - 1] + 1;
                        break;
                    }
                }
            }
            outv = new object[m];
            for (uint i = 0; i < m; i++)
                outv[i] = v[counter[i]];

            if (counter[0] == n – m)
                return false;
            else
                return true;
        }
    }

Суть работы данного алгоритма основана на том, что в наборе из n чисел существует С_n^m монотонно возрастающих (убывающих) последовательностей. Класс Combinations создает для каждого сочетания свой вектор outv длины m, который содержит ссылки на объекты из вектора V. Для получения первого сочетания нужно вызвать метод FirstCombination. Если при данных условиях выбора возможны еще сочетания, метод возвращает значение true, в противном случае – false. Для получения последующих сочетаний (если таковые имеются) вызывается метод NextCombination. Если при данных условиях выбора возможны еще сочетания, метод возвращает значение true, в противном случае – false. Таким образом метод NextCombination возвращает true С_n^m– 2 раз (всего, с учетом вызова FirstCombination получается С_n^m сочетаний). Типичная схема использования класса Combinations выглядит так:

// Генерируем сочетания из 7 по 4 из вектора V
Combinations combinations = new Combinations(ref V, 4, 7);
object[] outv;
if (combinations.FirstCombination(out outv))
do
{
... // Обработка. Вектор outv содержит очередное сочетаие
}
while (combinations.NextCombination(out outv));
... // Обработка последнего сочетания

Второй алгоритм несколько сложнее. Он не создает специального вектора для сохранения очередного сочетания. Вместо этого он последовательно переставляет элементы вектора V длины n таким образом, что при проходе всех итераций первые m элементов вектора V образуют сочетания из n по m, а последние n – m элементов – сочетания из n по n – m. Между этими сочетаниями, естественно, существует взаимнооднозначное соответствие.

    public class Combinations2
    {
        uint[] counter;
        uint m, n;
        object[] v;

        void Swap(uint i1, uint i2)
        {
            object tmp = v[i1];
            v[i1] = v[i2];
            v[i2] = tmp;
        }

        bool IncCounter()
        {
            bool result = false;
            for (uint i = 1; i < (uint) counter.Length; i++)
                if ((counter[i] == 0) && (counter[i - 1] != 0))
                {
                    result = true;
                    counter[i] = counter[i – 1];
                    for (uint j = 0; j < i; j++)
                        counter[j] = j < counter[i] - 1 ? j + 1 : 0;
                    break;
                }
            return result;
        }

        public Combinations2(ref object[] v, uint m, uint n)
        {
            if (m > n)
                throw new Exception("m не может быть больше n");
            if (m == 0)
                throw new Exception("m и n не могут быть равны 0");
            this.v = v;
            this.m = m;
            this.n = n;
            counter = new uint[n];
            for (uint i = 0; i < counter.Length; i++)
                counter[i] = i < m ? i + 1 : 0;
        }

        public bool NextCombination()
        {
            if (IncCounter())
            {
                for (uint i = 0; i < counter.Length; i++)
                    if (counter[i] > 0)
                        Swap(i, counter[i] – 1);
                return true;
            }
            return false;
        }

    }

Для получения очередного сочетания вызывается метод NextCombination, в результате чего выполняется перестановка элементов вектора V. Если при данных условиях выбора возможны еще сочетания, метод возвращает значение true, в противном случае – false. Исходное расположение элементов в V считается первым сочетанием. Таким образом метод NextCombination возвращает true С_n^m– 2 раз, так что общее число сочетаний, учитывая исходное расположение элементов вектора, оказывается С_n^m.

Типичная схема использования класса Combinations2 выглядит так:

// Генерируем сочетания из 7 по 4 из вектора V
Combinations2 combinations = new Combinations2(ref V, 4, 7);
// обработка исходного сочетания
while (combinations.NextCombination())
{
//Первые 4 элемента вектора V содержит очередное сочетание из 7 по 4 (последние три – из 7 по 3).
}

Другие алгоритмы На главную