1

Тема: Знаходження всіх можливих комбінацій масиву цілих чисел

Є масив цілих чисел, наприклад {1, 2, 4}, потрібно знайти всі двозначні комбінації чисел з цього масиву.
Як це зробити? Перестановки я можу знайти з next_permutation. Є ще картезіанський добуток,
але він лише з С++23, а в мене С++17.

2 Востаннє редагувалося steamwater (21.08.2024 22:29:27)

Re: Знаходження всіх можливих комбінацій масиву цілих чисел

Пряме Декартове перемноження на себе не допоможе? Якщо комбiнації елементiв на себе ({1,1} {2,2} {4,4}) не потрiбнi то їx можна вiдкинути.

#include <iostream>
#include <utility>
#include <vector>

int main() {
    std::vector<int> source{ 1, 2, 4 };
    std::vector<std::pair<int, int>> result; // можна одразу видiлити пам'ять але я не знаю як бути
    // з комбiнацiями сам-на-сам, тож вирiшайте самi, а я буду пушбечити)

    for(auto el_first : source)
        for(auto el_second : source)
            if(el_first != el_second) // оминає сам-на-сам, якщо не потрiбно - закоментуйте
                result.push_back(std::pair<int, int>(el_first, el_second));

    for(const auto &pr:result)
        std::cout << pr.first << ' ' << pr.second << '\n';

    return 0;
}

Це мали на увазi?

Подякували: Teg Miles1

3

Re: Знаходження всіх можливих комбінацій масиву цілих чисел

Teg Miles написав:

картезіанський добуток

steamwater написав:

Декартове перемноження

*WALL* *WALL* *WALL*

Подякували: leofun011

4

Re: Знаходження всіх можливих комбінацій масиву цілих чисел

koala, щось не так?

5

Re: Знаходження всіх можливих комбінацій масиву цілих чисел

koala написав:
Teg Miles написав:

картезіанський добуток

steamwater написав:

Декартове перемноження

*WALL* *WALL* *WALL*

У мене в голові було std::ranges::views::cartesian_product,
тому картезіанський, а не декартовий:)

Подякували: leofun011

6

Re: Знаходження всіх можливих комбінацій масиву цілих чисел

steamwater написав:

koala, щось не так?

Та ми обоє неправильно назвали термін, а він фізик-пурист.
Йому це як пінопластом по склу:) У них тут ціла банда фізиків:)

Подякували: leofun011

7 Востаннє редагувалося Teg Miles (21.08.2024 23:20:45)

Re: Знаходження всіх можливих комбінацій масиву цілих чисел

steamwater написав:

Пряме Декартове перемноження на себе не допоможе? Якщо комбiнації елементiв на себе ({1,1} {2,2} {4,4}) не потрiбнi то їx можна вiдкинути.

#include <iostream>
#include <utility>
#include <vector>

int main() {
    std::vector<int> source{ 1, 2, 4 };
    std::vector<std::pair<int, int>> result; // можна одразу видiлити пам'ять але я не знаю як бути
    // з комбiнацiями сам-на-сам, тож вирiшайте самi, а я буду пушбечити)

    for(auto el_first : source)
        for(auto el_second : source)
            if(el_first != el_second) // оминає сам-на-сам, якщо не потрiбно - закоментуйте
                result.push_back(std::pair<int, int>(el_first, el_second));

    for(const auto &pr:result)
        std::cout << pr.first << ' ' << pr.second << '\n';

    return 0;
}

Це мали на увазi?

Для початку підійде. Але в мене не лише двозначні числа,
там пінкод і в нього кожен раз різна довжина.
Окрім того дається ймовірний початковий набір цифр,
тому, як я згодом зрозумів, повністю всі перебирати буде непрактично.
Це таке завдання на Codewars (https://www.codewars.com/kata/5263c6999e0f40dee200059d).

8

Re: Знаходження всіх можливих комбінацій масиву цілих чисел

"Декартів" і "Картезіанський" - це одне й те саме слово (прикметник від Декарт), просто в першому випадку прикметник утворено в українській мові, а другому прикметник утворено у французькій мові, а далі запозичено.
Добуток і перемноження теж мають одне й те саме значення.
Порада замість картезіанського добутку застосувати декартове перемноження - це шило на мило.

Teg Miles, хочете реальну задачу? Напишіть власну реалізацію next_permutation і cartesian_product.

Подякували: leofun011

9

Re: Знаходження всіх можливих комбінацій масиву цілих чисел

Глянув - я всіма мовами, крім C, робив рекурсію.

10

Re: Знаходження всіх можливих комбінацій масиву цілих чисел

koala написав:

"Декартів" і "Картезіанський" - це одне й те саме слово (прикметник від Декарт), просто в першому випадку прикметник утворено в українській мові, а другому прикметник утворено у французькій мові, а далі запозичено.
Добуток і перемноження теж мають одне й те саме значення.
Порада замість картезіанського добутку застосувати декартове перемноження - це шило на мило.

Teg Miles, хочете реальну задачу? Напишіть власну реалізацію next_permutation і cartesian_product.

«Картезій» — це латина, звідти англійське cartesian. Тоді імена писали рідною мовою і латиною, як зараз рідною і англійською.
Довелося таки робити власну реалізацію:

std::vector<std::string> get_combo(std::vector<std::vector<std::string>>& all_numbers)
{
    int all_size = all_numbers.size();
    std::vector<std::vector<std::string>> temp(1, std::vector<std::string>());
    for (int i = 0; i < all_size; i++) {
        std::vector<std::vector<std::string>> new_temp;
        for (const std::vector<std::string>& product : temp) {
            for (const std::string& element : all_numbers.at(i)) {
                std::vector<std::string> temp_copy = product;
                temp_copy.push_back(element);
                new_temp.push_back(temp_copy);
            }
        }
        temp = new_temp;
    }
    int temp_size = temp.size();
    std::vector<std::string> answer(temp_size, "");

    for (int i = 0; i < temp_size; ++i) {
        for (const std::string& element : temp.at(i)) {
            answer.at(i) += element;
        }
    }
    return answer;
}

std::vector<std::string> get_pins(std::string observed)
{
    std::vector<int> obs_numbers;
    for (auto& number : observed) {
        obs_numbers.push_back(int(number - '0'));
    }
    std::vector<std::vector<std::string>> all_numbers;
    std::map<int, std::vector<int>> code_panel;
    code_panel.emplace(0, std::vector<int>({ 8 }));
    code_panel.emplace(1, std::vector<int>({ 2, 4 }));
    code_panel.emplace(2, std::vector<int>({ 1, 3, 5 }));
    code_panel.emplace(3, std::vector<int>({ 2, 6 }));
    code_panel.emplace(4, std::vector<int>({ 1, 5, 7 }));
    code_panel.emplace(5, std::vector<int>({ 2, 4, 6, 8 }));
    code_panel.emplace(6, std::vector<int>({ 3, 5, 9 }));
    code_panel.emplace(7, std::vector<int>({ 4, 8 }));
    code_panel.emplace(8, std::vector<int>({ 7, 5, 9, 0 }));
    code_panel.emplace(9, std::vector<int>({ 6, 8 }));
    for (auto& number : obs_numbers) {
        std::vector<std::string> helper;
        helper.push_back(std::to_string(number));
        for (auto& item : code_panel.at(number)) {
            helper.push_back(std::to_string(item));
        }
        all_numbers.push_back(helper);
    }
    std::vector<std::string> answer = get_combo(all_numbers);

    return answer;
}

Тільки не розумію, чи можна менше чим О(n в кубі) зробити?

11 Востаннє редагувалося steamwater (22.08.2024 13:02:23)

Re: Знаходження всіх можливих комбінацій масиву цілих чисел

Teg Miles написав:

Та ми обоє неправильно назвали термін, а він фізик-пурист.
Йому це як пінопластом по склу:) У них тут ціла банда фізиків:)

Так, це сiноними, але головне це перемноження на себе. Тобто з самим собою. Тут не важливо як воно зветься, але просто легше висловити. Що до фiзикiв, то я певною мiрою фiзик. Тож у бандi +1. Можу додати, що пуризм це про математикiв. Фiзики сьогодення - у бiльшостi є математики. Але попершу не всi, а подруге, математичний пуризм у кожного послаблюється у той мiрi у якiй вони є фiзики. Програмування працює на користь математики бо є роздiлом прикладної математики.
В цiлому важливо що на себе. Але перемноження теж має сенс. Добуток це бiльше про результат перемноження, тодi як перемноження це про процесс.
Teg Miles, у контекстi даної задачi ми маємо не одержати результуючу матрицю де кожен елемент Сij дорiвнює Ai*Bj. Нам потрiбно задокументувати властивicть Декартового перемноження комбiнувати, яка є частиною процеса. Це й робить простий алгоритм у котрому нема жодного слова про пана Декарта Рене батьковича. Тобто мої посилання на нього були досить прозорi.

Подякували: Teg Miles, leofun012