VPF::Алгоритм перебора пар, троек, четверок и тд элемен

DASTAD

Дата 16.5.2013, 05:07 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 21
Регистрация: 14.10.2009

Репутация: нет
Всего: 1

Прошу помощи.
Есть вектор 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 (ссылка)

(нет голосов)

Загрузка ...

в форме ;)

Профиль
Группа: Участник
Сообщений: 180
Регистрация: 28.1.2009
Где: Липецк

Репутация: 2
Всего: 5

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

Earnest

Дата 16.5.2013, 07:52 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 7
Всего: 183

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

--------------------

...

DASTAD

Дата 16.5.2013, 09:27 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 21
Регистрация: 14.10.2009

Репутация: нет
Всего: 1

Цитата(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;
}

Это сообщение отредактировал(а) DASTAD - 16.5.2013, 09:51

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »