[pva]

пока не понятно, что именно собираешься реализовывать, попробую показать как я это вижу
1. рассмотрим все перестановки (алгоритм)
1.1. выбрали один элемент
1.2. из оставшихся следующий
1.3. из оставшихся следующий и т.д...
2. рассмотрим перестановки с учётом групп. Чтобы внутри групп не получилось таких, которые из группы получаются перестановкой, будем всегда выбирать так, чтобы следующий элемент был больше предыдущего, то есть группа должна быть всегда отсортирована по возрастанию.
3. чтобы не стало так чтобы группа i+1 получалась из группы i перестановкой, первые элементы групп должны быть так же отсортированы по возрастанию. То есть выбираем только из тех оставшихся, которые больше, чем первый элемент в предыдущей группе.
4. в качестве элементов используем изначально упорядоченный массив чисел 1..N*K, т.к. для них применима операция сравнения.
Пример для 4-х элементов:

Код:

a b  c d     a<b, c<d, a<c
a c  b d     a<c, b<d, a<b
a d  b c     a<d, b<c, a<d

алгоритм перебора: последовательно выбираем все элементыв сортированном списке и помечае отобранные
1. выбирать первые элементы групп лучше с начала списка (и не трогать последние K-1)
2. выбирать остальные элементы групп лучше с конца списка, чтобы хватило для заполнения самых последних групп
Таким образом переберёшь все и ни разу не повторишься

[ALI]

Добрый день, дамы и господа! Некоторое время назад я задавал вопрос по поводу комплектования малых подгрупп.
Задачу выполнил с помощью pva и используя данный алгоритм (функция формирования перестановок).
Но! Дело в том, что при количестве людей большем 12, алгоритм перебора начинает захлебываться, то есть жутко тормозить или зависать. Поэтому встает вопрос: как можно ускорить процесс? Вкратце опишу суть того, что я делаю: формирую всевозможные перестановки N людей. На определенном шаге отсекаю все варианты, начинающиеся с 2. Варианты, начинающиеся с 3, 4 и т.д. уходят автоматически. Таким образом, количество перестановок резко сокращается. На каждом шаге формирования перестановки я осуществляю проверку на невозрастание внутри подгруппы и невозрастание первых людей подгрупп в соотвествии с алгоритмом, предложенным pva, . Если все ОК, то записываю перестановку в поток (TStream). После записи всех "правильных" перестановок (c учетом подгрупп) в поток я считываю данные из потока в ClientDataSet и далее они автоматически переносятся в DBGrid.
Понятно, что промежуточные звенья (TStream и ClientDataSet) значительно тормозят процесс, но даже если их отключить и оставить алгоритм формирования перестановок работающим "вхолостую", то процесс все равно захлебывается. Что делать? Как выкрутиться из этой непростой ситуации?

[pva]

ALI, вот код, который я использовал для проверки (Metrowerks codewarrior 8.0):

Код:

#include <windows.h>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
//------------------------------------

class permutation1
{
    vector<int> _current;
    vector<int> _avaible;
    unsigned _stack_level;

    static vector<pair<unsigned,unsigned> > _program;
    static unsigned _gp_count, _gp_size, _stats;

    permutation1(unsigned size);

    permutation1(
            const permutation1& prev,
            unsigned value_avaible,
            unsigned value_permuted);

    void exec();

public:

    static void main(unsigned gp_count, unsigned gp_size);
};

vector<pair<unsigned,unsigned> > permutation1::_program;
unsigned permutation1::_gp_count, permutation1::_gp_size, permutation1::_stats;

void permutation1::main(unsigned gp_count, unsigned gp_size)
{
    if (gp_size && gp_count)
    {
        _gp_count = gp_count;
        _gp_size  = gp_size;
        _stats    = 0;

        // составляем программу выборок
        _program.reserve(gp_count*gp_size);

        unsigned long time1 = GetTickCount();

        for (unsigned group1=0; group1<gp_count; ++group1)
        {
            _program.push_back(make_pair(-1, group1*gp_size));
        }

        for (unsigned group1=gp_count; 0<group1--; )
        {
            for (unsigned element1=gp_size; 0<--element1; )
            {
                unsigned offset1 = group1*gp_size;
                _program.push_back(make_pair(offset1, offset1 + element1));
            }
        }

        permutation1(gp_count*gp_size).exec();

        unsigned long time2 = GetTickCount();

        cout << "permutation count: " << _stats << "\n"
            "finished in: " << double(time2-time1)/1000. << " seconds\n";
    }
    else
    {
        throw invalid_argument("permutation1::main nonzero both count and size expected");
    }
}

permutation1::permutation1(unsigned size) :
    _current(size),
    _avaible(size),
    _stack_level()
{
    for (unsigned n=0; n<size; ++n)
    {
        _avaible[n] = n;
    }
}

permutation1::permutation1(
        const permutation1& prev,
        unsigned value_avaible,
        unsigned value_permuted) :
    _current(prev._current),
    _avaible(prev._avaible.size()-1),
    _stack_level(prev._stack_level+1)
{
    copy(prev._avaible.begin() + value_avaible + 1, prev._avaible.end(),
            copy(prev._avaible.begin(), prev._avaible.begin() + value_avaible, _avaible.begin()));

    _current[value_permuted] = prev._avaible[value_avaible];
}


void permutation1::exec()
{
    if (_stack_level < _program.size())
    {
        pair<unsigned,unsigned>& instr1(_program[_stack_level]);

        if (instr1.first != -1)
        {
            unsigned left_to_fill = instr1.second-instr1.first;

            // выбор элементов
            for (unsigned element1 = _avaible.size();
                    left_to_fill <= element1 &&
                    _current[instr1.first]<_avaible[(--element1)-left_to_fill]; )
            {
                permutation1(*this,
                    /*доступный элемент*/ element1,
                    /*что заменить*/ instr1.second).exec();
            }
        }
        else
        {
            // выбор групп
            unsigned group1=0;

            for (; group1<_avaible.size() && _avaible[group1]<=int(instr1.second); ++group1)
            {
                permutation1(*this, group1, instr1.second).exec();
            }

            if (_avaible.size()<=group1) throw logic_error("bug found: permutation1::avaible no group candidate");
        }
    }
    else
    {
        for ( unsigned g=0; g<_gp_count; ++g)
        {
            cout << "group ";
            cout.width(3);
            cout << g << ": ";

            for ( unsigned f=0; f<_gp_size; ++f)
            {
                cout.width(4);
                cout << _current[g*_gp_size + f];
            }

            cout << "\n";
        }

        cout << "\n";

        ++_stats;
    }
}
//------------------------------------

int main()
{
    filebuf outbuf;
    outbuf.open("output.txt", ios::out|ios::app);
    streambuf* coutbuf = cout.rdbuf(&outbuf);

    try
    {
        permutation1::main(7,3);
    }
    catch(exception& e)
    {
        clog << e.what() << "\n";
    }

    cout.rdbuf(coutbuf);
    return 0;
}
//------------------------------------

На машинке pentium-4, 1600 МГц, 768 МБ ОЗУ, WinXP sp2 результаты следующие:
использование памяти 384 МБ, в памяти:
система, qip, winamp, IDE компилятора, файловый менеджер, браузер, справочная литература, антивирь и диспетчер задач.. ну и программа конечно.
параметры: 4x3 (итого 12 чел)
сборка debug: 127805 вариантов за 10.359 секунд
сборка release: 127805 вариантов за 2.61 секунд
не захлебнулось ;-)
output:

[ALI]

Как файл скачать-то?
Дык, с 12-ю людьми и у меня все нормально, а вот если речь заходит о 16 и более, то там начинаются проблемы.

[pva]

у меня случались какие-то глюки, когда я его засылал. Проще собери и получи за 2 секунды результат. Прошу прощения, не заметил "больше". Попробовал на большем числе - действительно уходит в большую обработку. Причём память использует на прежднем уровне. Я заметил, что на один результат в среднем уходит 100 байт. 120 тыс. комбинаций даёт 1.2 меговый файл. Когда запустил 4х4, подождал 30 минут, получил 1.5 гиговый файл и дальше ждать не стал. Вся проблема в том, что слишком большое число комбинаций. Я даже боюсь что может не хватить 32-разрядного регистра чтобы подсчитать их количество. Задача приобретает нерешаемый в силу временных ограничений характер.
Если всё-же хочешь ускорить процесс, предлагаю ввести распараллеливание (сейчас в моде многоядерные машины). Написаный выше мной код это сделать позволяет, т.к. на каждом следующем этапе используется своя независимая копия памяти. А вообще советую пересмотреть задачу

[ALI]

Я, скорее всего, переделаю задачу через сочетания:
http://forum.algolist.ru/algorithm-m...-podgrupp.html
Как там написал один товарисч, сочетаний значительно меньше, чем перестановок, посему алгоритм времени будет жрать меньше.

[pva]

сочетаний значительно меньше

Задача детерминированная, количество решений не зависит от метода. Лучше меняй постановку на попроще

[ALI]

Как ты представляешь себе смену постановки на попроще, а?
Смысл вот в чем: у меня есть "ручной" алгоритм, разработанный, кстати говоря, мной, в котором люди разбиваются на подгруппы за конечное число шагов на основе социометрии. Но проблема в чем? Проблема состоит в том, чтобы разбить этих людей ТАК, чтобы получить оптимальное решение с точки зрения взаимоотношений в исходной группе. Т.е. надо получить ТАКИЕ подгруппы, где люди меньше всего конфликтуют между собой.
Получив решение на основе "ручного" алгоритма, я хочу посмотреть какое место оно будет занимать в "иерархии" разбиений, полученных методом перебора. Иерархия выстраивается по КГср (средний коэффициент когерентности).
Пояснение: КГ (коэффициент когерентности) - мера связанности подгруппы, лежащая в пределах от -100 до 100. То бишь подгруппа с КГ=-100 - это самая худшая группа, которая только может существовать. Соответственно, подгруппа с КГ = 100 - это идеальная подгруппа.
В каждом разбиении считаются КГi (КГ для каждой подгруппы), КГср, а далее они выстраиваются по возрастанию, т.е. наверху таблицы находятся разбиения с максимальным КГср, а внизу - с минимальным. Эта таблица и есть результат работы алгоритма перебора. Потом я ищу в общей массе разбиение, полученное ручным методом и смотрю, насколько высоко или низко оно находится с точки зрения КГср. В зависимости от полученного результата, я буду "подкручивать" ручной алгоритм, чтобы он поднялся как можно выше. Поэтому, так или иначе, но мне приходится просматривать ВСЕ разбиения.
Если ты когда-нибудь сталкивался с транспортной задачей, задачей о рюкзаке, теорией графов, СМО и др. подобными задачками, то это из этой оперы.

[pva]

ВОТ!!! совершенно другое дело! я поправлю условие:
есть симметричная таблица взаимоотншений m(i,j) из диапазона [-100,100], причём m(i,i)=0
найти такие перестановки столбцов (и строк соответсвенно), чтобы функция среднего взаимоотношения во всех группах КГср была максимальной

Код:

  1 2 3 4 5 6
1 А A A - - -
2 А А A - - -
3 А А А - - -
4 - - - Б Б Б
5 - - - Б Б Б
6 - - - Б Б Б

Вот теперь совершенно дикая идея: пусть ГКi линейно относительно ГК. написать критерий и отсортировать список по возрастанию шаблоном std::sort (пузырьковой сортировкой). Критерий: один элемент считается больше другого, если он при перестановке местами даёт больший вклад в ГКi. Может я туманно выразился :SCRATCH:, но по идее компьютеру отсортировать 100 записей - сущая безделица, даже по трудному критерию.