Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Алгоритм перебора пар, троек, четверок и тд элемен

Автор: DASTAD 16.5.2013, 05:07

Прошу помощи.
Есть вектор N действительных значений. A = [a1, a2, ... an]
Как лучше реализовать универсальный перебор различных комбинаций элементов(пары, двойк, тройки, четверки, пятерки и тд.) на проверку условия? Например, сумма элементов комбинации равна 1.

Если, перебор комбинаций из одного элемента вектора - это 1 цикл вида: for i=1 to N if a[i]=1 then... )
Если перебор комбинаций пар элементов, то нужен двойной вложенный цикл (for i=1 to N for j=i to N if a[i]+a[j]=1 then...)
Если, перебор комбинаций троек элеметов, то 3й вложеный цикл: for i=1 to N for j=i to N for k=j to N if a[i]+a[j]+a[k]=1
и тд

А как это реализовать в одном алгоритме?

Автор: Lipetsk 16.5.2013, 07:49

используйте рекурсию

Автор: Earnest 16.5.2013, 07:52

Перебор сочетаний из N по M.
Есть простой и эффективный алгоритм перебора, погугли.

Автор: DASTAD 16.5.2013, 09:27

Цитата(Earnest @ 16.5.2013, 07:52)

Перебор сочетаний из N по M.
Есть простой и эффективный алгоритм перебора, погугли.

нашел хороший рекурсивный алгоритм
http://algolist.manual.ru/maths/combinat/seqnm.php

но мне нужны неповторяющиеся комбинации

нашел smile

Код


#include <iostream>
#include <vector>

using std::vector;
using std::cin;
using std::cout;
using std::endl;

int n, k;
vector<int> v;

void comb(int num)
{
    if(num > k)
    {
        for(int i=1; i<=k; i++)
            cout << v[i];
        cout << endl;
        return;
    }
    v[num] = v[num-1]+1;
    while(v[num] <= n)
    {
        comb(num+1);
        v[num]++;
    }
    return;
}


int main(void)
{
    cin >> n >> k;
    v.resize(k+1);
    v[0]=0;
    comb(1);
    return 0;
}