VPF::Быстрый перебор без повторений с ограничениями

tt0100

Дата 18.7.2012, 22:01 (ссылка)

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

Загрузка ...

Новичок

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

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

Нужен быстрый алгоритм поиска всех возможных вариантов значений нескольких переменных без повторений.
Есть m переменных. Каждая из которых может принимать некоторые значения из диапазона 1..n. Например:
v1 {4,5,6,7}
v2 {1,2,3,4,7}
v3 {1,2,3,4,5,6,7}
v4 {1}
v5 {1,2,3,4,5,6,7}
v6 {1,7}
нужен алгоритм который переберет все варианты так что варианты одинаковы если отличаются только порядком переменных.
стандартно если ограничений нет то можно через вложенные циклы
for(i1=1;i1<=(7-(колво переменных-1));i1++){
for(i2=i1+1;i2<=(7-(колво переменных-1)+1);i2++){
и тд.
но когда есть ограничения это не работает.
а делать полный перебор это n^m это слишком много лишних операций.
хотелось бы что-нибудь попроще
если есть
спс

Silent

Дата 19.7.2012, 13:33 (ссылка)

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

Загрузка ...

Опытный

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

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

Мне сейчас лень расписывать, что и как делать, проще код написать:
входной файл input.txt

Код


6
4 4 5 6 7
5 1 2 3 4 7
7 1 2 3 4 5 6 7
1 1
7 1 2 3 4 5 6 7
2 1 7

первое число - количество множеств _count, далее в _count строках первое число - количество чисел в i-ом множестве и сами числа

алгоритм

Код


#include <stdio.h>
#include <algorithm>
using namespace std;

const int N = 7,        //диапазон [1..N]
           mmax = 10;    //m переменных
struct elem
{
    int num;
    int value;
};

elem v[mmax*N];
elem ans[mmax];
bool ex_v[N+1], ex_l[N+1];

int _count;    //количество множеств
int n = 0;    //количество элементов во всех множествах

int cmp1(const elem & a, const elem & b) { return a.value < b.value; }
int cmp2(const elem & a, const elem & b) { return a.num < b.num; }

void init()
{
    for (int i = 1; i <= N; i++) 
    {
        ex_v[i] = true;
        ex_l[i] = true;
    }
    int k, c1 = 0;
    scanf("%d",&_count);
    for (int i = 0; i < _count; i++)
    {
        scanf("%d",&k);
        for (int j = 0; j < k; j++, c1++)
        {
            scanf("%d", &v[c1].value);
            v[c1].num = i;
        }        
    }
    n = c1;
}

void solve(int level, int last)
{
    if (level == _count)
    {
        elem tmp[mmax];
        for (int i = 0; i < _count; i++) tmp[i] = ans[i];
        sort(&tmp[0], &tmp[_count-1], &cmp2);
        //for (int i = 0; i < _count; i++) printf("%d:%d ", tmp[i].num, tmp[i].value);
        for (int i = 0; i < _count; i++) printf("%d ", tmp[i].value);
        printf("\n");
    }
    else
    {
        int i = 0;
        while (v[i].value <= last) i++;    //найдем первый подходящий элемент (можно заменить на бинарный поиск)
        while (i < n)
        {
            if (ex_v[v[i].value] && ex_l[v[i].num])
            {
                ans[level] = v[i];
                ex_v[v[i].value] = false;            
                ex_v[v[i].num]   = false;
                solve(level+1, v[i].value);
                ex_v[v[i].value] = true;            
                ex_v[v[i].num]   = true;
                int tmp = v[i].value;
                while ((i < n) && (v[i].value == tmp)) i++;    //пропускаем все элементы с таким значением
            }
            i++;
        }
    }
}

int main()
{
   freopen("input.txt", "rt", stdin);
//   freopen("output.txt", "wt", stdout);
    init();
    sort(&v[0], &v[n], &cmp1);
    solve(0, 0);
    return 0;
}

в итоге для данных множеств ответ

Код


1 2 3 4 5 6 
1 2 3 4 5 7 
1 2 3 4 6 7 
1 2 3 5 6 7 
1 2 4 5 6 7 
1 4 3 5 6 7 
3 4 2 5 6 7

tt0100

Дата 19.7.2012, 14:17 (ссылка)

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

Загрузка ...

Новичок

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

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

ну вроде как очевидно что неправильно. т.к. из v4 и v6 следует что в результате всегда должно быть 1 и 7. но спасибо за оперативность. неожидал

Silent

Дата 20.7.2012, 12:34 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата

ну вроде как очевидно что неправильно

не совсем понял, что вы имели ввиду... результат неправильный или отсечение мало?

tt0100

Дата 20.7.2012, 18:18 (ссылка)

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

Загрузка ...

Новичок

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

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

Цитата(Silent @ 20.7.2012, 12:34

)

не совсем понял, что вы имели ввиду...

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

tt0100

Дата 21.7.2012, 11:47 (ссылка)

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

Загрузка ...

Новичок

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

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

Silent
все вродебы понятно как решать.
там у тебя в v нужно хранить именно матрицу 0/1 есть значение в ограничении или нет. ( sort(&v[0], &v[n], &cmp1) исключает выпадающие значения но у меня их не будет).
и исходя из этой матрицы выбирать значение которое исключаем первым - то которое реже всего встречается из оставшихся. и проверять исключение значения приводит к исключению переменной или нет.
по идее это значит что на каждом шагу надо производить поиск минимального элемента. не знаю на сколько это быстро.
ну в смысле понятно что за линейное время но вопрос в накладных расходах на каждый шаг операции

Silent

Дата 23.7.2012, 09:37 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата

ну там первого и последнего результата не должно быть

а чем они плохи, почему их не должно быть? вполне себе обычные варианты
Количество операций меньше C(n,m), поскольку алгоритм пытается собрать возрастающую последовательность
v - это линейный список с элементами множеств, никаких "0/1 матриц значений ограничений" там нет.

Попробуйте еще раз разобраться с кодом.

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