c - 在 C 中使用 nr_values 打印 N 个元素的排列

Question

我正在做一项作业，它说我需要打印 N 个元素的值，每个元素中都有 nr_values 。

所以输出应该是..例如元素数量(N) = 2 以及每个元素可以保存的值的数量hold(nr_values) = 2

所以值为:

 0 0
 0 1 
 1 0
 1 1

现在的问题是，在达到最终值集后我无法使其停止。

以下是我正在处理的代码..

    while(flag == 0)
        {
         recursive_helper_perm_rec_1(a,N,nr_vals);
         int incrementIndex;

      for(int i = (N-2); i >= 0; i--)
      {
        if(a[i] < (nr_vals-1))
        {
            a[i]++;
            incrementIndex = 1;
            break;
        }

    }
    for(int i = (incrementIndex + 1); i<N; i++)
    {
        if(a[i] == (nr_vals-1))
        {
            a[i] = 0;
        }
    }  




    for(int i=0; i<N ; i++)
    {
        if(a[i] == (nr_vals-1))
        {
            flag = 1;
        }
    }

}  

如有任何建议，我们将不胜感激..

谢谢

Answer 1

您应该尝试实现回溯算法。我为此编写了以下代码。为了更好的理解和可读性，我将代码分成了许多函数。

• 解 vector 是 [N]，其中每个元素将通过 backtrack() 函数填充。
• get_candidates() 将返回给定槽 k 的候选者的可能数量和候选者[] vector 。
• is_a_solution() 如果解 vector 已填满(即 a[] 已填满 N 个元素)，则返回 true。

.

#define  TRUE  1
#define  FALSE 0
#define  M  5 /* Possible values */
#define  N  4 /* No of slots */
typedef short int bool;

void get_candidates (int a[], int k, int *n_candidates, int candidates[])
{
    int possible[M];
    int i;

    for (i = 0; i < M; i++) {
        possible[i] = TRUE;
    }

    *n_candidates = 0;
    for(i = 0; i < k; i++) {
        possible[a[i]] = FALSE;
    }

    for (i = 0; i < M; i++) {
        if (possible[i] == TRUE) {
            candidates[*n_candidates] = i;
            *n_candidates = *n_candidates + 1;
        }
    }   
}

bool is_a_solution (int a[], int k)
{
    return (k == N);
}

void process_solution (int a[], int k)
{
    /* We will just print it */
    int i;
    for (i = 0; i < k; i++) {
        printf ("%d ", a[i]);
    }
    printf ("\n");
}

void backtrack (int a[], int k)
{
     int i, n_candidates = 0;
     int candidates[M];

     if (is_a_solution(a, k)) {
         process_solution (a, k);
         return;
     }

     get_candidates (a, k, &n_candidates, candidates);
     for (i = 0; i < n_candidates; i++) {
          a[k] = candidates[i];
          backtrack (a, k + 1);          
     }        
}

int main ()
{
     int a[N];
     backtrack (a, 0);
}