Перебор всех комбинаций

@Helen_2001 · Регистрация: 23.08.2017

Студворк — интернет-сервис помощи студентам

Всем приветики.
Помогите решить задачку, а то сойду с ума

Суть задачки. Есть массив в виде map. То, что в first не важно, а вот second очень важно.
Нужно перебрать все комбинации при учете, что длина вектора внимание, разная.
В данном примере массивы

[1,2,3,4]

[1,2]

[1,2,3]

Нужно чтобы получилась длина значений как arr.size() при этом перебрать все комбинации из arr.second

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

C++
1
2
3
4
5
  std::map<std::string, std::vector<int32_t>> arr;
 
  arr.emplace("a",std::vector<int32_t>({1,2,3,4}));
  arr.emplace("b",std::vector<int32_t>({1,2}));
  arr.emplace("c",std::vector<int32_t>({1,2,3}));

@zss · 11.10.2021, 19:15

Так, вроде бы это очевидно

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int x1[4]={1,2,3,4};
int x2[2]={1,2};
int x3[3]={1,2,3,};
int arr[3];
for(int i1=0;i1<4;i1++)
{
  arr[0]=x1[i1];
  for(int i2=0;i2<2;i2++)
  {
     arr[1]=x2[i2];
     for(int i3=0;i3<3;i3++)
     {
        arr[2]=x3[i3];
        for(int j=0;j<3;j++)
          cout<<arr[j]<<' ';
     }
  }
}

@Helen_2001 · 11.10.2021, 19:25 **[ТС]**

Сообщение от zss

Так, вроде бы это очевидно

size.arr() может быть не только 3, но и любое другое число.

@Helen_2001 · 12.10.2021, 13:04 **[ТС]**

Сообщение от zss

Так, вроде бы это очевидно

Как-то совсем не очевидно

C++
1
2
3
4
5
6
7
8
std::map<std::string, std::vector<int32_t>> arr;
 
  arr.emplace("a",std::vector<int32_t>({1,2,3,4}));
  arr.emplace("b",std::vector<int32_t>({1,2}));
  arr.emplace("c",std::vector<int32_t>({1,2,3}));
......
  arr.emplace("y",std::vector<int32_t>({1,2,3,4,5,6,7,8}));
  arr.emplace("z",std::vector<int32_t>({1,2,3,4,8}));

@Kastaneda · 12.10.2021, 14:27

Helen_2001,

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <map>
#include <vector>
 
int main() {
  std::map<std::string, std::vector<int32_t>> arr;
 
  arr.emplace("a", std::vector<int32_t>({1, 2, 3, 4}));
  arr.emplace("b", std::vector<int32_t>({1, 2}));
  arr.emplace("c", std::vector<int32_t>({1, 2, 3}));
  arr.emplace("y", std::vector<int32_t>({1, 2, 3, 4, 5, 6, 7, 8}));
  arr.emplace("z", std::vector<int32_t>({1, 2, 3, 4, 8}));
 
  for (const auto &array : arr) {
    std::cout << "[ ";
    for (int value : array.second) {
      std::cout << value << " ";
    }
    std::cout << "]" << std::endl;
  }
 
  return 0;
}

@Helen_2001 · 12.10.2021, 15:05 **[ТС]**

Мне нежно вывести не содержимое массива, а перебрать все возможные комбинации значений как я написала выше в примере.

Croessmah · 12.10.2021, 16:28

std::next_permutation подойдет?

@Helen_2001 · 12.10.2021, 16:36 **[ТС]**

Сообщение от Croessmah

std::next_permutation подойдет?

Вроде нет. Мне нужно брать по одному числу из каждого map..second. Но при этом значений должно быть фиксированно числу arr.size()

@Helen_2001 · 13.10.2021, 12:44 **[ТС]**

Так ничего и не придумала. Пришлось сделать плохо-плохо.
Создала массив, в который заполняются случаным образом данные с проверкой на уникальность. Получилось что-то вроде брутфорса.

Работает долго, но важен результат! Хорошо что никто не видит что внутри кода

)

@zayats80888 · 13.10.2021, 13:15

Сообщение от Helen_2001

Так ничего и не придумала.

https://rosettacode.org/wiki/C... ns#C.2B.2B

@Kastaneda · 13.10.2021, 14:22

Не по теме:

Сообщение от Helen_2001

Мне нежно вывести

Helen_2001, ох :)

@Helen_2001 · 13.10.2021, 14:27 **[ТС]**

Сообщение от zayats80888

https://rosettacode.org/wiki/C... ns#C.2B.2B

Длина arr[].second разная. Не подходит.

@zayats80888 · 13.10.2021, 14:29

Сообщение от Helen_2001

Длина arr[].second разная. Не подходит.

В каком месте не подходит?

@Helen_2001 · 13.10.2021, 14:33 **[ТС]**

Сообщение от zayats80888

В каком месте не подходит?

Ваш пример генерирует всё что в std::vector. А мне нужно взять по одному значению из вектора каждой итерации map

@zayats80888 · 13.10.2021, 15:22

Сообщение от Helen_2001

А мне нужно взять по одному значению из вектора каждой итерации map

Т.е. в вашем примере на первой позиции могут быть только числа {1,2,3,4}, а на второй позиции только {1, 2}?

@Helen_2001 · 13.10.2021, 16:09 **[ТС]**

Сообщение от zayats80888

Т.е. в вашем примере на первой позиции могут быть только числа {1,2,3,4}, а на второй позиции только {1, 2}?

C++
1
2
3
4
5
6
7
8
  std::map<std::string, std::vector<int32_t>> arr;
 
  arr.emplace("a",std::vector<int32_t>({1,2,3,4}));
  arr.emplace("b",std::vector<int32_t>({1,2}));
  arr.emplace("c",std::vector<int32_t>({1,2,3}));
......
  arr.emplace("y",std::vector<int32_t>({1,2,3,4,5,6,7,8}));
  arr.emplace("z",std::vector<int32_t>({1,2,3,4,8}));

из arr[0].second взять любой из 1,2,3 или 4. Это не важно какой тип вектора, главное массив там разной длины и нужно из него взять какое то одно значение.
потом идем в arr[1] и по той же схеме берем одно значение, скажем 1.

например получился массив

C++
1
2
  arr.emplace("a",std::vector<int32_t>({5,2));
  arr.emplace("b",std::vector<int32_t>({7}));

arr.siz() = 2 следовательно комбинаций будет



5 7

2 7

длина комбинаций,это arr.size() и по одному из second карты.
Мы генерируем все перечисления сверху виз.
И как это сделать я не пойму

Я придумала только случайно заполнить и проверить на уникальность

@zayats80888 · 13.10.2021, 16:11

Helen_2001,

Кликните здесь для просмотра всего текста

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
#include <cassert>
#include <cstdint>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <functional>
 
int main() {
  std::map<std::string, std::vector<int32_t>> arr;
 
  arr.emplace("a", std::vector<int32_t>({1, 2, 3, 4}));
  arr.emplace("b", std::vector<int32_t>({1, 2}));
  arr.emplace("c", std::vector<int32_t>({1, 2, 3}));
 
  ////////////////////////////////////////////////////
  using VecElement =
      std::pair<size_t, std::reference_wrapper<std::vector<int32_t> const>>;
  std::vector<VecElement> comb;
  for (auto const &p : arr) {
    assert(!p.second.empty());
    comb.emplace_back(0, p.second);
  }
  auto print = [&comb]() {
    std::cout << "[ ";
    for (auto p : comb) {
      std::cout << p.second.get()[p.first] << ' ';
    }
    std::cout << "]\n";
  };
  for (bool finish = comb.empty(); !finish;) {
    print();
    size_t i = 0;
    ++comb[i].first;
    for (; comb[i].first == comb[i].second.get().size();) {
      comb[i++].first = 0;
      if (i == comb.size()) {
        finish = true;
        break;
      }
      ++comb[i].first;
    }
  }
  ////////////////////////////////////////////////////
}

@_Ivana · 13.10.2021, 16:57

Семен Семеныч!... (С)

C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <vector>
#include <string>
 
std::vector<std::vector<int32_t>> v = {{1,2,3,4}, {1,2}, {1,2,3}};
 
void f (int i, std::string r) {
    if (i<0) std::cout << r << "\n"; else for (int j=0; j<v[i].size(); j++) f(i-1, std::to_string(v[i][j])+" "+r);
}
 
int main() { f(v.size()-1, ""); }

ЗЫ убогие индексы и глобальный доступ надо заменить на итераторы, но сами курите как их в плюсах инкрементировать и чекать выход за границы
ЗЗЫ выучите хотя бы один нормальный язык, и подобные задачки не будут вызывать никаких трудностей

Новые блоги и статьи Все статьи Все блоги /
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .

@Helen_2001 15 / 13 / 4 Регистрация: 23.08.2017 Сообщений: 187
	12.10.2021, 15:05 [ТС]
	Мне нежно вывести не содержимое массива, а перебрать все возможные комбинации значений как я написала выше в примере. 0

Croessmah Неэпический 18149 / 10731 / 2067 Регистрация: 27.09.2012 Сообщений: 27,035 Записей в блоге: 1
	12.10.2021, 16:28
	std::next_permutation подойдет? 0

@Helen_2001 15 / 13 / 4 Регистрация: 23.08.2017 Сообщений: 187
	13.10.2021, 12:44 [ТС]
	Так ничего и не придумала. Пришлось сделать плохо-плохо. Создала массив, в который заполняются случаным образом данные с проверкой на уникальность. Получилось что-то вроде брутфорса. Работает долго, но важен результат! Хорошо что никто не видит что внутри кода ) 0

Перебор всех комбинаций

Решение