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

Question

我正在寻找一种算法，给定一个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

Answer 1

#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;
}

Answer 2

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