Найти все различные сочетания из k элементов

Question

Задание: Дан целочисленный массив, состоящий из n элементов. Необходимо найти все различные сочетания элементов заданной длины k.

Входные данные: В первой строке входного файла дано значение n - количество элементов в массиве. Во второй строке входного файла через пробел даны n чисел – элементы массива, а затем дано число k - необходимая длина.

Моё решение: `

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    int *arr = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    int k;
    cin >> k;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (abs(arr[j] - arr[i]) == k) {
                cout << arr[i] << " " << arr[j];
            }
        }
    }
    return 0;
}`

Вопрос: К сожалению, вместо вывода каждого такого элемента, программа выводит только промежуточный ответ в виде 1 3. Когда должна выводить 1 2, 1 3, 2 3.

Answer 1

В с++ есть std:next_permutation. Заполните массив длиной n нулями в количестве n-k и k единицами. После каждой итерации позиции единиц покажут индексы, которые нужно использовать для получения очередного сочетания

P.S. Не подходит, если в массиве есть повторы.

P.P.S. Для массивов с повторами сделал:

void combine(vector<vector<int>> lst, int idx, int n, int k, vector<int> res) {
    if (res.size() == k) {
        for (auto &x:res)
            cout << x << " ";
        cout << "\n";
        return;
    }
    if (idx >= n)
        return;

    //используем текущий элемент
    res.push_back(lst[idx][0]);
    combine(lst, idx + 1, n, k, res);
    res.pop_back();

    //пропустим текущий элемент, перейдя к следующей серии
    combine(lst, lst[idx][1], n, k, res);
}

int main()
{
    vector<int> a = { 3,1,4,1,2,2,2 };
    std::sort(a.begin(), a.end());
    int n = a.size();
    int k = 3;

    //подготовим специальную структуру, где второй элемент указывает на индекс начала следующей серии
    vector<vector<int>> b = { {a.back(), n} };
    int next = n;
    for(int i = n-2; i>=0; i--){
        if (a[i] != a[i + 1]) 
            next = i + 1;
        b.insert(b.begin(), { a[i], next });
    }

    vector <int> res;
    combine(b, 0, n, k, res);
}

1 1 2
1 1 3
1 1 4
1 2 2
1 2 3
1 2 4
1 3 4
2 2 2
2 2 3
2 2 4
2 3 4

Answer 2

Вариант MBo для небольших количеств — до 64, например — можно сделать с помощью трюка над битами (см. "Алгоритмические трюки для программистов" Уоррена):

unsigned long long snoob(unsigned long long x)
{
    unsigned long long smallest = x & -x;
    unsigned long long ripple   = x + smallest;
    unsigned long long ones     = x ^ ripple;
    ones = (ones >> 2)/smallest;
    return ripple|ones;
}

template<typename T, size_t N>
void combines( T(&a)[N], size_t K)
{
    static_assert( N < 64 );
    if (K == 0 || K > N ) return;
    unsigned long long x = (1ull << K) - 1;
    for(;x < (1ull << N); x = snoob(x))
    {
        unsigned long long y = x;
        for(size_t i = 0; y; y >>= 1, i++)
            if (y&1) cout << a[i] << " ";
        cout << endl;
    }
}

int main(int argc, char * argv[])
{
    int a[] = {1,3,5,8, 0};
    combines(a,2);
}

См. https://ideone.com/g3Gg5Z

Но! Заметим минус данного подхода: если в массиве оказываются одинаковые элементы — будут выводиться одинаковые сочетания. Метод не смотрит на сами элементы...

Answer 3

Есть вот такой вариант, который работает прямо с контейнером:

template <typename Iterator>
inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
    if ((first == last) || (first == k) || (last == k))
        return false;
    Iterator itr1 = first;
    Iterator itr2 = last;
    ++itr1;
    if (last == itr1)
        return false;
    itr1 = last;
    --itr1;
    itr1 = k;
    --itr2;
    while (first != itr1)
    {
        if (*--itr1 < *itr2)
        {
            Iterator j = k;
            while (!(*itr1 < *j)) ++j;
            std::iter_swap(itr1,j);
            ++itr1;
            ++j;
            itr2 = k;
            std::rotate(itr1,j,last);
            while (last != j)
            {
                ++j;
                ++itr2;
            }
            std::rotate(k,itr2,last);
            return true;
        }
    }
    std::rotate(first,k,last);
    return false;
}

Он, правда, тоже не умеет работать с одинаковыми элементами, но это легко обойти, примерно как

vector<int> combo = {1, 2, 3, 3, 3, 4, 5};
sort(combo.begin(), combo.end());
auto end = unique(combo.begin(), combo.end());
auto begin = combo.begin();
auto mid = begin + 3;

do {
    for (auto iter = begin; iter != mid; ++iter)
        cout << *iter << " ";

    cout << endl;
    }
while (next_combination(begin, mid, end));

БЛОГ НА HUSL

Найти все различные сочетания из k элементов

Ответы (3 шт):