Комбинации мономов n-й степени в C ++ - PullRequest
Новая
       40

Комбинации мономов n-й степени в C ++

1 голос
/ 09 апреля 2019

Итак, я должен сгенерировать вектор мономов. Вот как я сделал это для 3 измерений для произвольного порядка: 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int dim = 3; 
    int order = 2;
    std::vector<std::vector<int>> powers;

    for (int ord = 0; ord <= order; ord++) {
        if (dim == 1) {
            powers.push_back({ord});
        } else if (dim == 2) {
            for (int i = 0; i < ord + 1; i++) {
                powers.push_back({i, ord - i});
            }
        } else if (dim == 3) {
            for (int i = 0; i < ord + 1; i++) {
                for (int j = 0; j < ord + 1 - i; j++) {
                    powers.push_back({i, j, ord - i - j});
                }
            }
        } else if (dim == 4){
            for (int i = 0; i < ord + 1; i++) {
                for (int j = 0; j < ord + 1 - i; j++) {
                    for (int k = 0; k < ord + 1 - i - j; k++) {
                        powers.push_back({i, j, k, ord - i - j - k});
                    }
                }
            }
        } else {
            // "Monomials of dimension >= 4 not supported."
        }
    }
    cout << "Finished!" << endl;
    return 0;
}

Теперь моя цель - поддержать N измерений и порядок N-го мономов. Любые идеи о том, как распространить код выше на N пространств? Я не вижу простой способ реализовать это выше. Я думал об использовании комбинаторики и как-то исключил дополнительные термины, но я не уверен в скорости.

РЕДАКТИРОВАТЬ (ожидаемый результат): Для заданных входных данных order = 2 и dim = 3 ожидаемый результат (не обязательно в этом порядке): 

000
001
002
010
011
020
100
101
110
200

для order = 1 и dim = 3: 

000
001
010
100

и для order = 2 и dim = 2: 

00
01
10
11
02
20

Ответы [ 2 ]

2 голосов
/ 09 апреля 2019

Это классическая рекурсивная функция:

Каждый раз, когда вам нужно выбрать порядок текущей переменной x_1 (скажем, i), и тогда у вас останутся все возможности для монома со степенью ord - iна n -1 переменных.

(рабочий) код выглядит следующим образом: 

   std::vector<std::vector<int>> getAllMonomials(int order, int dimension) {
    std::vector<std::vector<int>> to_return;
    if (1 == dimension) {
        for (int i = 0 ; i <= order; i++){
            to_return.push_back({i});
        }
        return to_return;
    }

    for (int i = 0 ; i <= order; i++) {
        std::vector<std::vector<int>> all_options_with_this_var_at_degree_i = getAllMonomials(order - i, dimension - 1);
        for (int j = 0; j < all_options_with_this_var_at_degree_i.size(); j++) {
            all_options_with_this_var_at_degree_i.at(j).insert(all_options_with_this_var_at_degree_i.at(j).begin(), i);
        }
        to_return.insert(to_return.end(), all_options_with_this_var_at_degree_i.begin(), all_options_with_this_var_at_degree_i.end());

    }
    return to_return;
}
1 голос
/ 09 апреля 2019

Pyrhon рекурсивное решение

ideone 

def compose(leng, summ, res):
    if leng == 0:
        print(res)
        return
    for i in range(summ + 1):
        compose(leng - 1, summ -i, res + str(i) + " ")

compose(3, 2, "")
...