给定一个具有一定约束条件的数字列表的换元算法。

问题描述 投票:0回答:1

我正在寻找一种算法,给定一个n个值的集合,每个值可以是{0,1,...m},可以高效地找到所有有效的排列组合。

规则。

只能有一个值> 1:

n = 3, m = 5
{ 0, 0, 0 } is valid
{ 1, 5, 0 } is valid
{ 5, 2, 1 } is not valid

当一个值 != 0, 那么前一个值就不能是0. 这个规则可以不被x位置的值所遵守:

n = 3, m = 5, x: 2
{ 1, 0, 0 } is valid
{ 0, 1, 0 } is invalid
{ 1, 0, 4 } is valid

如果我测试了一个随机集合,但它是无效的,那么我必须打印出原因。

{ 2, 5, 0 }: Value 5 is illegal, there can be only one value > 1 
{ 0, 3, 0 }: Value 3 is illegal, the previous value is 0
algorithm graph permutation graph-algorithm combinatorics
1个回答
0
投票
#include <iostream>
#include <vector>
using namespace std;

void generate(vector<int> &perm, int pos, int n, int m, int x, bool is_more_than_one) {
    if (pos == n) {
        for (auto i: perm) {
            cout << i << ' ';
        }
        cout << endl;
    } else {
        for (int i = 0; i <= m; i++) {
            if (i > 1) {
                if (!is_more_than_one) {
                    if (pos == x || (!pos || perm[pos - 1] != 0)) {
                        perm[pos] = i;
                        generate(perm, pos + 1, n, m, x, true);
                    }
                }
            } else {
                if (pos == x || (!pos || perm[pos - 1] != 0)) {
                    perm[pos] = i;
                    generate(perm, pos + 1, n, m, x, is_more_than_one);
                }
            }
        }
    }
}


int main() {
    vector<int> perm;
    int n = 3, m = 5, x = 2;
    perm.resize(n);
    generate(perm, 0, n, m, x, false);
    return 0;
}

0
投票
  1. 建立 base_set 上所有有效字符串的 0,1 字母表
  2. 构建其余。

    for each number k greater than one
        for each string s in the base_set
            for each position p in s
                if the s[p] is 1
                    replace s[p] with k
                    print the resulting string
                    set s[p] back to 1
    
© www.soinside.com 2019 - 2024. All rights reserved.