← Static tasks

E136. Генерация сочетаний из N элементов

emaxx algorithm

#algorithm#combinatorics#emaxx#math

Task

Источник: e-maxx.ru/algo, страница PDF 439.

Сочетания из N элементов по K в

лексикографическом порядке

Постановка задачи. Даны натуральные числа N и K. Рассмотрим множество чисел от 1 до N. Требуется вывести все различные его подмножества мощности K, причём в лексикографическом порядке. Алгоритм весьма прост. Первым сочетанием, очевидно, будет сочетание (1,2,...,K). Научимся для текущего сочетания находить лексикографически следующее. Для этого в текущем сочетании найдём самый правый элемент, не достигший ещё своего наибольшего значения; тогда увеличим его на единицу, а всем последующим элементам присвоим наименьшие значения.

bool next_combination (vector<int> & a, int n) {

int k = (int)a.size();
for (int i=k-1; i>=0; --i)
if (a[i] < n-k+i+1) {

++a[i];

for (int j=i+1; j<k; ++j)

a[j] = a[j-1]+1;

return true;

}

return false;

} С точки зрения производительности, этот алгоритм линеен (в среднем), если K не близко к N (т.е. если не выполняется, что K = N - o(N)). Для этого достаточно доказать, что сравнения "a[i] < n-k+i+1" выполняются в сумме Cn+1k раз, т.е. в (N +1) / (N-K+1) раз больше, чем всего есть сочетаний из N элементов по K.

Сочетания из N элементов по K с изменениями

ровно одного элемента

Требуется выписать все сочетания из N элементов по K, но в таком порядке, что любые два соседних сочетания будут отличаться ровно одним элементом. Интуитивно можно сразу заметить, что эта задача похожа на задачу генерации всех подмножеств данного множества в таком порядке, когда два соседних подмножества отличаются ровно одним элементом. Эта задача непосредственно решается с помощью Кода Грея: если мы каждому подмножеству поставим в соответствие битовую маску, то, генерируя с помощью кодов Грея эти битовые маски, мы и получим ответ. Может показаться удивительным, но задача генерации сочетаний также непосредственно решается с помощью кода Грея. А именно, сгенерируем коды Грея для чисел от 0 до 2N-1, и оставим только те коды, которые содержат ровно K единиц. Удивительный факт заключается в том, что в полученной последовательности любые две соседние маски (а также первая и последняя маски) будут отличаться ровно двумя битами, что нам как раз и требуется. Докажем это. Для доказательства вспомним факт, что последовательность G(N) кодов Грея можно получить следующим образом:

G(N) = 0G(N-1) ∪ 1G(N-1)R

т.е. берём последовательность кодов Грея для N-1, дописываем в начало каждой маски 0, добавляем к ответу; затем снова берём последовательность кодов Грея для N-1, инвертируем её, дописываем в начало каждой маски 1 и добавляем к ответу. Теперь мы можем произвести доказательство. Сначала докажем, что первая и последняя маски будут отличаться ровно в двух битах. Для этого достаточно заметить, что первая маска будет иметь вид N-K нулей и K единиц, а последняя маска будет иметь вид: единица, потом N-K-1 нулей, потом K-1 единица. Доказать это легко по индукции по N, пользуясь приведённой выше формулой для последовательности кодов Грея. Теперь докажем, что любые два соседних кода будут отличаться ровно в двух битах. Для этого снова обратимся к формуле для последовательности кодов Грея. Пусть внутри каждой из половинок (образованных из G(N-1)) утверждение верно, докажем, что оно верно для всей последовательности. Для этого достаточно доказать, что оно верно в месте "склеивания" двух половинок G(N-1), а это легко показать, основываясь на том, что мы знаем первый и последний элементы этих половинок. Приведём теперь наивную реализацию, работающую за 2N:

int gray_code (int n) {
return n ^ (n >> 1);

}

int count_bits (int n) {
int res = 0;
for (; n; n>>=1)

res += n & 1;

return res;

}

void all_combinations (int n, int k) {

for (int i=0; i<(1<<n); ++i) {
int cur = gray_code (i);
if (count_bits (cur) == k) {
for (int j=0; j<n; ++j)
if (cur & (1<<j))

printf ("%d ", j+1);

puts ("");

} } } Стоит заметить, что возможна и в некотором смысле более эффективная реализация, которая будет строить всевозможные сочетания на ходу, и тем самым работать за O (Cnk n). С другой стороны, эта реализация представляет собой рекурсивную функцию, и поэтому для небольших n, вероятно, она имеет большую скрытую константу, чем предыдущее решение. Собственно сама реализация - это непосредственное следование формуле:

G(N,K) = 0G(N-1,K) ∪ 1G(N-1,K-1)R

Эта формула легко получается из приведённой выше формулы для последовательности Грея - мы просто выбираем подпоследовательность из подходящих нам элементов.

bool ans[MAXN];

void gen (int n, int k, int l, int r, bool rev) {

if (k > n || k < 0)  return;
if (!n) {
for (int i=0; i<n; ++i)

printf ("%d", (int)ans[i]);

puts ("");

return;

}

ans[rev?r:l] = false;

gen (n-1, k, !rev?l+1:l, !rev?r:r-1, rev);

ans[rev?r:l] = true;

gen (n-1, k-1, !rev?l+1:l, !rev?r:r-1, !rev);

}

void all_combinations (int n, int k) {

gen (n, k, 0, n-1, false);

}

C# solution

auto-draft, review before submit
using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    bool next_combination (List<int> & a, int n) {
            int k = (int)a.size();
            for (int i=k-1; i>=0; --i)
                    if (a[i] < n-k+i+1) {
                            ++a[i];
                            for (int j=i+1; j<k; ++j)
                                    a[j] = a[j-1]+1;
                            return true;
                    }
            return false;
    }
    G(N) = 0G(N-1) ∪ 1G(N-1)R
    int gray_code (int n) {
            return n ^ (n >> 1);
    }
    int count_bits (int n) {
            int res = 0;
            for (; n; n>>=1)
                    res += n & 1;
            return res;
    }
    void all_combinations (int n, int k) {
            for (int i=0; i<(1<<n); ++i) {
                    int cur = gray_code (i);
                    if (count_bits (cur) == k) {
                            for (int j=0; j<n; ++j)
                                    if (cur & (1<<j))
                                            Console.Write ("%d ", j+1);
                            puts ("");
                    }
            }
    }
    G(N,K) = 0G(N-1,K) ∪ 1G(N-1,K-1)R
    bool[] ans = new bool[MAXN];
    void gen (int n, int k, int l, int r, bool rev) {
            if (k > n || k < 0)  return;
            if (!n) {
                    for (int i=0; i<n; ++i)
                            Console.Write ("%d", (int)ans[i]);
                    puts ("");
                    return;
            }
            ans[rev?r:l] = false;
            gen (n-1, k, !rev?l+1:l, !rev?r:r-1, rev);
            ans[rev?r:l] = true;
            gen (n-1, k-1, !rev?l+1:l, !rev?r:r-1, !rev);
    }
    void all_combinations (int n, int k) {
            gen (n, k, 0, n-1, false);
    }
}

C++ solution

matched/original
bool next_combination (vector<int> & a, int n) {
        int k = (int)a.size();
        for (int i=k-1; i>=0; --i)
                if (a[i] < n-k+i+1) {
                        ++a[i];
                        for (int j=i+1; j<k; ++j)
                                a[j] = a[j-1]+1;
                        return true;
                }
        return false;
}
G(N) = 0G(N-1) ∪ 1G(N-1)R
int gray_code (int n) {
        return n ^ (n >> 1);
}
int count_bits (int n) {
        int res = 0;
        for (; n; n>>=1)
                res += n & 1;
        return res;
}
void all_combinations (int n, int k) {
        for (int i=0; i<(1<<n); ++i) {
                int cur = gray_code (i);
                if (count_bits (cur) == k) {
                        for (int j=0; j<n; ++j)
                                if (cur & (1<<j))
                                        printf ("%d ", j+1);
                        puts ("");
                }
        }
}
G(N,K) = 0G(N-1,K) ∪ 1G(N-1,K-1)R
bool ans[MAXN];
void gen (int n, int k, int l, int r, bool rev) {
        if (k > n || k < 0)  return;
        if (!n) {
                for (int i=0; i<n; ++i)
                        printf ("%d", (int)ans[i]);
                puts ("");
                return;
        }
        ans[rev?r:l] = false;
        gen (n-1, k, !rev?l+1:l, !rev?r:r-1, rev);
        ans[rev?r:l] = true;
        gen (n-1, k-1, !rev?l+1:l, !rev?r:r-1, !rev);
}
void all_combinations (int n, int k) {
        gen (n, k, 0, n-1, false);
}

Java solution

auto-draft, review before submit
import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    boolean next_combination (ArrayList<Integer> & a, int n) {
            int k = (int)a.size();
            for (int i=k-1; i>=0; --i)
                    if (a[i] < n-k+i+1) {
                            ++a[i];
                            for (int j=i+1; j<k; ++j)
                                    a[j] = a[j-1]+1;
                            return true;
                    }
            return false;
    }
    G(N) = 0G(N-1) ∪ 1G(N-1)R
    int gray_code (int n) {
            return n ^ (n >> 1);
    }
    int count_bits (int n) {
            int res = 0;
            for (; n; n>>=1)
                    res += n & 1;
            return res;
    }
    void all_combinations (int n, int k) {
            for (int i=0; i<(1<<n); ++i) {
                    int cur = gray_code (i);
                    if (count_bits (cur) == k) {
                            for (int j=0; j<n; ++j)
                                    if (cur & (1<<j))
                                            System.out.print ("%d ", j+1);
                            puts ("");
                    }
            }
    }
    G(N,K) = 0G(N-1,K) ∪ 1G(N-1,K-1)R
    boolean ans[MAXN];
    void gen (int n, int k, int l, int r, boolean rev) {
            if (k > n || k < 0)  return;
            if (!n) {
                    for (int i=0; i<n; ++i)
                            System.out.print ("%d", (int)ans[i]);
                    puts ("");
                    return;
            }
            ans[rev?r:l] = false;
            gen (n-1, k, !rev?l+1:l, !rev?r:r-1, rev);
            ans[rev?r:l] = true;
            gen (n-1, k-1, !rev?l+1:l, !rev?r:r-1, !rev);
    }
    void all_combinations (int n, int k) {
            gen (n, k, 0, n-1, false);
    }
}

Explanation

Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.