Алгоритм перестановки задан списком чисел с некоторым ограничением

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

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
   

Answer 2

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