VPF::заранее не известно количество циклов

htzg

Дата 23.10.2010, 22:25 (ссылка)

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

Загрузка ...

Бывалый

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

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

народ! Целый день бьюсь с задачей:
есть файл в котором идут по очереди группы букв. Разделителем группы является символ "#". Пример:

Код


# a b c # a b # a b c d # a # a b c

т.е. новая группа начинается после "#"
Задача: как перебрать все сочетания букв из разных групп?
В выше приведенном примере кол-во сочетаний равно 3*2*4*1*3 = 72.
Заранее не известно что файле(сколько групп и сколько букв в группе).

mes

Дата 23.10.2010, 22:31 (ссылка)

(голосов:1)

Загрузка ...

любитель

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

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

http://cplusplus.com/reference/algorithm/next_permutation/ ?

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

http://opendots.net

Dov

Дата 24.10.2010, 00:48 (ссылка)

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

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

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

Цитата(htzg @ 23.10.2010, 21:25

)

народ! Целый день бьюсь с задачей:

А можно на результаты битвы хотя бы одним глазком взглянуть?

з.ы. кстати, там между 'буквами' пробелы стоят или мне показалось? И что, по-твоему, означает количество сочетаний?

Это сообщение отредактировал(а) Dov - 24.10.2010, 00:52

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

Тут вечности запах томительный,
И свежие фрукты дешевые,
А климат у нас – изумительный,
И только соседи – #уевые.
Игорь Губерман.

htzg

Дата 24.10.2010, 11:17 (ссылка)

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

Загрузка ...

Бывалый

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

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

Цитата(Dov @ 24.10.2010, 00:48

)

А можно на результаты битвы хотя бы одним глазком взглянуть?

Можно, но на самом деле я задачу(здесь) в упрощенном виде представил.
Вместо букв будут массивы из string.

Код


// Creator.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <cctype>
#include <vector>
#define REMSYMB  "//" 

void toupperstr(std::string &s)
{
    for(int i=0 ; i < s.size() ; ++i)
        s.at(i) = toupper(s.at(i)) ;
}

void trimr(std::string &s)
{
    int i = s.size();
    if(i > 0)
    {
        for( std::string::iterator iter = s.end()-1 ; iter != s.begin() && (*iter == ' ' || *iter == '\t' ) ; --iter)
            --i;
        s = s.substr(0,i);
        if(s == "\t" || s == " ")
            s.clear();
    }
}

void tospec(std::string &s)
{
    std::string sn;
    for( std::string::iterator iter = s.begin() ; iter != s.end() ; ++iter)
        if( *iter == '\\')
        {
            sn.push_back('\\');
            sn.push_back('\\');
        }
        else
            sn.push_back(*iter);
    s = sn ;
}

bool gitm(std::ifstream &ifile, std::string &str, std::string RemSymb, bool ToUpperCase=0)
{
    if( ifile.eof() )
        return 0;
    do{
        std::getline(ifile,str);
        int f = str.find(RemSymb.c_str());
        if(f > -1)
            str = str.substr(0,f);
        trimr(str);
    }while(str.size() == 0 && !ifile.eof() );
    if( str.size()==0 )
        return 0;
    if(ToUpperCase)
        toupperstr(str);
    return 1;
}

struct SStrSharps
{
    std::string str;
    unsigned int sharps;
};

struct SMatrElem
{
    std::vector<SStrSharps>::iterator it1,it2;
    bool act;
};


void getme(SMatrElem &me, std::vector<SStrSharps>::iterator &iter1, std::vector<SStrSharps>::iterator &iter2 )
{
    if(iter1  == iter2)
        return 0;
    for(std::vector<SStrSharps>::iterator iter = iter1+1 ; iter != iter2 ; ++iter)
        if( (*iter).sharps > (*iter1).sharps )
        {
            iter1 = iter;
            return getme(me, iter1, iter2 );  /////   recursion
        }
        else if( (*iter).sharps == (*iter1).sharps )
        {
            me.it1 = iter1 ;
            me.it2 = iter-1 ;
            iter1 = iter ;
            me.act = 1 ;
            return 1 ;
        }
        else if( (*iter).sharps < (*iter1).sharps && (*iter).sharps != 0 )
        {
            me.it1 = iter1 ;
            me.it2 = iter-1 ;
            iter1 = iter ;
            me.act = 1 ;
            return 0 ;
        }
    me.it1 = iter1 ;
    me.it2 = iter-1 ;
    iter1 = iter ;
    me.act = 1 ;
    return 0 ;
}

int _tmain(int argc, _TCHAR* argv[])
{
    std::cout << "Ifile spec..." << std::endl;
    std::string ifilespec;
    std::cin >> ifilespec;
    tospec(ifilespec);
    std::ifstream ifile;
    ifile.open(ifilespec.c_str());

    if( ifile.fail() )
    {
        std::cout << " ifile problem" << std::endl;
        system("pause");
        return 0;
    }
    std::string ofspecpref;
    gitm(ifile,ofspecpref,"//");
    if(ofspecpref.at(ofspecpref.size()-1) != '\\')
        ofspecpref.push_back('\\');
    tospec(ofspecpref);
    std::string str;
    std::vector<SStrSharps> arr;
    //std::vector<unsigned int> sharpsarr;
    unsigned int R=0,C=0; //,outersharps=0;
    while( gitm(ifile,str,"//") )
    {
        SStrSharps strsh;
        strsh.sharps = 0 ;
        for(std::string::iterator iter=str.begin() ; iter!=str.end() ; ++iter)
            if( *iter == '#' )
                ++strsh.sharps ;
        //if( outersharps == 0 )
        //    outersharps = sharps;
        if( strsh.sharps == 1 )
            ++R;
        if( strsh.sharps > C )
            ++C;
        str.erase(0,strsh.sharps);
        strsh.str = str;
        arr.push_back(strsh);
    }
    /////begin
    SMatrElem **matr = new SMatrElem *[R];
    for(int r=0 ; r < R ; ++r)
        matr[r] = new SIter [C];
    /////end
    for(int c=0 ; c < C ; ++c)
        for(int r=0 ; r < R ; ++r)
        {
            SMatrElem me;
            me.act = 0;
            matr[r][c] = me;
        }
    std::vector<SStrSharps>::iterator iter1 = arr.begin();
    std::vector<SStrSharps>::iterator iter2 = arr.end();
    for(int r=0 ; r < R ; ++r)
    {
        bool stop=0;
        for(int c=0 ; !stop && c < C ; ++c)
        {
            SMatrElem me;
            if( getme(me, iter1, iter2 ) )
                stop=1;
            matr[r][c] = me;
        }
    }
    //unsigned int outersharps=sharpsarr.front();
    //for(std::vector<unsigned int>::iterator iter = sharpsarr.begin() ; iter!= sharpsarr.end() ; ++iter)
    //    if(*iter == outersharps)
    //        ++r;

    /////begin
    for(int c=0 ; c < C; ++c)
        delete [] matr[c] ;
    //delete [] matr ;
    /////end


    system("pause");
    return 0;
}

Цитата(Dov @ 24.10.2010, 00:48

)

И что, по-твоему, означает количество сочетаний?

На примере:
# a1 a2 a3 # b1 b2 b3 # c1 // всего 9 сочетаний ( 3 элемента из 1 группы, 3 элемента из 2 группы, 1 элемент из 3 группы, итого 3*3*1=9)
сочетание №1:
a1 b1 c1
сочетание №2:
a1 b2 c1
сочетание №3:
a1 b3 c1
сочетание №4:
a2 b1 c1
сочетание №5:
a2 b2 c1
...
сочетание №9:
a3 b3 c1

Это сообщение отредактировал(а) htzg - 24.10.2010, 11:18

mes

Дата 24.10.2010, 11:41 (ссылка)

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

Загрузка ...

любитель

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

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

поможет виртуальная машина паскаля..
заводите два массива цифр ( один лимиты, другой счетчики ) с размером равным кол-ву групп..
лимиты выставляете по кол-ву символов в соответсвующей группе (или плюс один, если символа из этой группы может не быть)..
потом начинаете перебирать младший счетчик, как достиг лимита обнуляете и увеличиваете на один следующий счетчик,
когда он в свою очередь достигнит лимита, также обнуляете и к следующий на один и т.д.

на каждой итерации теперь можно формировать строку, использую счетчики как индексы символа в группе.

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

http://opendots.net

htzg

Дата 24.10.2010, 15:08 (ссылка)

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

Загрузка ...

Бывалый

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

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

Цитата(mes @ 24.10.2010, 11:41

)

можно пример попросить? smile

mes

Дата 24.10.2010, 16:50 (ссылка)

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

Загрузка ...

любитель

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

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

Цитата(htzg @ 24.10.2010, 14:08

)

можно пример попросить?

http://liveworkspace.org/code/de3bf0578deb...00f066dd7bf4365

Код


#include <vector>
#include <string>
#include <iostream>

std::vector<size_t> limits;
std::vector<size_t> counters;

bool next_iterate ()
{    
  for (size_t i=0; i < limits.size(); ++i)  
    if (! (++counters[i] < limits[i]) ) counters[i]=0;
    else return true;
  return false;
}

int main ()
{
   std::vector<std::string> data;
   
   data.push_back("1345");   
   data.push_back("ab");
   data.push_back("cde");
   data.push_back("fghij");
   data.push_back("qwerty");
   
   for (size_t i=0; i<data.size(); ++i)   
      limits.push_back(data[i].size());

   counters.resize(data.size());
      
   do
   {
       for (size_t i=0; i<counters.size(); ++i )
         std::cout << data[i][counters[i]];
        
        std::cout << std::endl;       
       
   } while (next_iterate());   
}

Это сообщение отредактировал(а) mes - 24.10.2010, 17:58

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

http://opendots.net

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