Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
r1se3
0 / 0 / 0
Регистрация: 18.09.2013
Сообщений: 37
#1

Замена элемента из множества - C++

09.07.2015, 17:51. Просмотров 266. Ответов 15
Метки нет (Все метки)

Подскажите с оптимальным решением задачи.

Имеется динамический vector элементов для подстановки.
std:vector<std::string> letters_rep;
letters_rep.push_back("r");
letters_rep.push_back("u");
letters_rep.push_back("z");
letters_rep.push_back("w");


Имеется строка, в которой необходимо заменить символ:
std:string str = "zLhpgjHps53p";

Задача:
Заменить элемент "p", на элементы из множества, получив все возможные вариации, т.е.:

zLhrgjHzs53u
zLhrgjHrs53z
zLhwgjHus53z
zLhzgjHzs53z
и т.д.


Заранее благодарен.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.07.2015, 17:51     Замена элемента из множества
Посмотрите здесь:

C++ Замена первого максимального элемента в одномерном массиве на 0
C++ Поиск и замена максимального элемента двумерного массива
Множества. Проверка множества на наличие элемента в нем C++
Множества. Вычислить количество элементов множества Q, связанного c исходными множествами C++
Замена элемента списка C++
замена элемента матрицы на пробел C++
C++ Число изъять из множества А, если оно является элементом множества А, но не является элементом множества В
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
S_el
2065 / 1572 / 301
Регистрация: 15.12.2013
Сообщений: 6,207
09.07.2015, 17:57     Замена элемента из множества #2
r1se3, а где ваше решение и что понимается под оптимальным?
r1se3
0 / 0 / 0
Регистрация: 18.09.2013
Сообщений: 37
09.07.2015, 18:05  [ТС]     Замена элемента из множества #3
S_el, Начал реализовать вот так, но не знаю как правильно оформить луп.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
std:string str = "zLhpgjHps53p";
size_t count_p = std::count(str.begin(), str.end(), 'p');
 
std:vector<std::string> letters_rep;
letters_rep.push_back("r");
letters_rep.push_back("u");
letters_rep.push_back("z");
letters_rep.push_back("w");
 
int iter = static_cast< int >(pow(letters_rep.size(), std::count(hash.begin(), hash.end(), 'p'))); //макс количество
 
//не знаю как реализовать луп, для изменения и проверки
set<std::string>my_set;
for
{
if (my_set.count("1234"))
   //уже есть
else
  my_set.insert("1234");
}
S_el
2065 / 1572 / 301
Регистрация: 15.12.2013
Сообщений: 6,207
09.07.2015, 18:07     Замена элемента из множества #4
r1se3, тогда давайте как обычно.Пишите алгоритм и к каждому пункту свое видение реализации на C++.
r1se3
0 / 0 / 0
Регистрация: 18.09.2013
Сообщений: 37
09.07.2015, 18:10  [ТС]     Замена элемента из множества #5
S_el, я выше написал свое видение.

Вычисляю возможное множество, количество_букв^сколько_раз_встретилось_р
Далее, необходимо реализовать луп, в котором произойдут возможные замены.
S_el
2065 / 1572 / 301
Регистрация: 15.12.2013
Сообщений: 6,207
09.07.2015, 18:15     Замена элемента из множества #6
Цитата Сообщение от r1se3 Посмотреть сообщение
я выше написал свое видение.
оно рабочее?

Кстати,что вы хотите сделать 10 строчкой?
r1se3
0 / 0 / 0
Регистрация: 18.09.2013
Сообщений: 37
09.07.2015, 18:34  [ТС]     Замена элемента из множества #7
S_el, нет, оно не рабочее, т.к. я не знаю как проитерировать все возможные вариации.

В 10 строке, я вычисляю возможное колчество итоераций.
т.е. 5^2 = 25, за 25 итераций, возможно получить все решения.

Добавлено через 15 минут
S_el,

Извиняюсь, у меня 4 буквы и 3 вхожения. Следовательно
4^3
S_el
2065 / 1572 / 301
Регистрация: 15.12.2013
Сообщений: 6,207
09.07.2015, 18:52     Замена элемента из множества #8
r1se3, давайте еще раз.
На входе вот это:
C++
1
std:string str = "zLhpgjHps53p";
и это:
C++
1
2
3
4
letters_rep.push_back("r");
letters_rep.push_back("u");
letters_rep.push_back("z");
letters_rep.push_back("w");
на выходе - вектор строк,каждая из которых образована заменой буквы p на символ из второго вектора?
r1se3
0 / 0 / 0
Регистрация: 18.09.2013
Сообщений: 37
09.07.2015, 18:53  [ТС]     Замена элемента из множества #9
S_el, да вы поняли верно.
S_el
2065 / 1572 / 301
Регистрация: 15.12.2013
Сообщений: 6,207
09.07.2015, 19:03     Замена элемента из множества #10
например так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# include<iostream>
# include<vector>
# include<string>
 
int main()
    {
    std::string str = "zLhpgjHps53p";
    std::vector<char> letters_rep;
    letters_rep.push_back('r');
    letters_rep.push_back('u');
    letters_rep.push_back('z');
    letters_rep.push_back('w');
    std::vector<std::string> res(letters_rep.size(),str);
 
    std::vector<size_t> vec_index;
    for(size_t i=0;i<str.size();i++)
        if(str[i]=='p')
            vec_index.push_back(i);
 
    for(size_t j=0;j<letters_rep.size();j++)
        for(const auto &i :vec_index)
            res[j][i]=letters_rep[j];
 
    for(const auto &el :res)
        std::cout<<el<<std::endl;
    return 0;
    }
r1se3
0 / 0 / 0
Регистрация: 18.09.2013
Сообщений: 37
09.07.2015, 19:09  [ТС]     Замена элемента из множества #11
S_el, нет, вы не до конца поняли задачу.

Суть заключается в том, что они должны получится комбинаторно, т.е. как у меня вначале написанно:

zLhrgjHzs53u
zLhrgjHrs53z
zLhwgjHus53z
zLhzgjHzs53z

и т.д.

А в вашем решение, просто замена p одной буквой.

Должно получиться 4^3 = 64 решения(строки)
S_el
2065 / 1572 / 301
Регистрация: 15.12.2013
Сообщений: 6,207
09.07.2015, 20:16     Замена элемента из множества #12
Цитата Сообщение от S_el Посмотреть сообщение
на выходе - вектор строк,каждая из которых образована заменой буквы p на символ из второго вектора?
Цитата Сообщение от r1se3 Посмотреть сообщение
да вы поняли верно.
Надо точнее формулировать.
Напишите пример,который полно описывает задачу,мне пока не удалось понять по какому признаку следует проводить каждую замену.
r1se3
0 / 0 / 0
Регистрация: 18.09.2013
Сообщений: 37
10.07.2015, 11:22  [ТС]     Замена элемента из множества #13
S_el, Все возможные замены.
Признак очевидный, исходя из комбинаторика и теории вероятности, мы знаем какое количество замен 'p' возможно. Необходимо реализовать алгоритм, который будет рекурсивно/итеративно заменять элемент, на предложенные.
S_el
2065 / 1572 / 301
Регистрация: 15.12.2013
Сообщений: 6,207
10.07.2015, 17:13     Замена элемента из множества #14
r1se3, когда-то писал что-то похожее:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# include <iostream>
# include <vector>
# include <algorithm>
# include <iterator>
# include <functional>
# include <cmath>
# include <string>
 
std::vector<std::vector<size_t>> create_Index(const size_t &N,const size_t &M);
 
int main()
    {
    std::string str = "zLhpgjHps53p";
    std::vector<char> letters_rep;
    letters_rep.push_back('r');
    letters_rep.push_back('u');
    letters_rep.push_back('z');
    letters_rep.push_back('w');
 
    std::vector<size_t> vec_index;
    for(size_t i=0;i<str.size();i++)
        if(str[i]=='p')
            vec_index.push_back(i);
    size_t A=vec_index.size(),B=letters_rep.size();
    auto SI = create_Index(A,B);
    size_t C =SI.size();
    std::vector<std::string> res(C,str);
    for(size_t j=0;j<C;j++)
        for(size_t i=0;i<A;i++)
            res[j][vec_index[i]]=letters_rep[SI[j][i]];
            
    for(const auto &el :res)
        std::cout<<el<<std::endl;
 
    return 0;
    }
 
std::vector<std::vector<size_t>> create_Index(const size_t &N,const size_t &M)
    {
    std::vector<std::vector<size_t>> VS(pow(M,N)); 
    size_t count=0;
 
    std::function<void(size_t,std::vector<size_t>)> Var=
        [&](size_t ind,std::vector<size_t> vec)
        {
        if(ind==0) 
            {
            VS[count++] =vec; 
            return;
            }
        else
            {
            std::vector<size_t> newvec(vec);
            auto temp = N-ind+1;
            newvec.resize(temp);
            for(size_t j=0;j<M;j++)
                {
                newvec[temp-1]=j;
                Var(ind-1,newvec);
                }
            }
        };
    Var(N,std::vector<size_t>());
    return VS;
    }
r1se3
0 / 0 / 0
Регистрация: 18.09.2013
Сообщений: 37
13.07.2015, 10:32  [ТС]     Замена элемента из множества #15
S_el, я решил похоже.
У меня рандомно выбираеться буква для замены, и подставляется. И так для каждой 'p'. Все это помешщается в сет, и отнимается общий счетчик вариантов. Так по кругу, пока варианты не закончатся.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int iter = static_cast< int >(pow(letters_rep.size(), count_p));
 
        //create possibility
        std::set<std::string>mutationstr;
        if (count_p != 0)
        {
            do{
                std::string str = hash;
                int pos;
                for (int i = 0; i < count_p; i++)
                {
                    int output = 0 + (rand() % (int)(letters_rep.size() - 1 - 0 + 1));
                    while ((pos = str.find('p')) != std::string::npos)
                        str.replace(pos, 1, letters_rep[output]);
                }
                if (mutationstr.count(str)) iter--;
                else mutationstr.insert(str);
            } while (iter != 0);
        }
        else mutationstr.insert(hash);
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.07.2015, 11:14     Замена элемента из множества
Еще ссылки по теме:

Множества . Найти разность полученного множества с заданным C++
Где в коде происходит замена максимального и минимально элемента в строке массива? C++
Квадрат с вершинами из первого множества накрывает все точки второго множества и имеет минимальную площадь C++
C++ Замена максимального элемента массива на среднее арифметическое (арифметика указателей)
Замена элемента массива на нужное значение C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
S_el
2065 / 1572 / 301
Регистрация: 15.12.2013
Сообщений: 6,207
13.07.2015, 11:14     Замена элемента из множества #16
Цитата Сообщение от r1se3 Посмотреть сообщение
У меня рандомно выбираеться буква для замены, и подставляется. И так для каждой 'p'. Все это помешщается в сет, и отнимается общий счетчик вариантов. Так по кругу, пока варианты не закончатся.
Мне кажется такое решение будет не эффективным даже по сравнению с моим вариантом.
Yandex
Объявления
13.07.2015, 11:14     Замена элемента из множества
Ответ Создать тему
Опции темы

Текущее время: 18:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru