给出了一个带有一定约束的数字列表的置换算法

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. 在0,1字母表上构建所有有效字符串的base_set(应该很容易(

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