使用nr_values打印N个元素的排列C

Question

我正在处理一个赋值，它说我需要在每个元素中打印N个元素的值为nr_values。

因此，输出应为..因此例如像的elements(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

而不是使用循环中，更简单的实现可能是使用递归。

假设你有nr_values = 4,N = 3。每个位置的可能值是{0, 1, 2, 3}有3个位置__ __ __：

继承人你如何实现你的递归算法线索：

找到所有的排列(_ _ _)等同于：

环流式通过第一个数字x = 0, 1, 2, ..的可能性，然后找到所有其余数字的排列x (_ _) ...

我在这里附上了一个简单的解决方案（万一你卡住了）。但是你应该尝试使用上面的概念自己的算法，因为它总是更有意义的解决它自己！

在你的主：

f(N-1, 0, nr_values, N); 

而对于f(..)功能：

void f(int N, int ans, int nr_values, int specifier) { 

    int i; //i is a looping variable 

    if (N == -1) { //base case 
     printf("%0*d\n", specifier, ans); //print leading zeros 
    } else { 
     for (i=0; i < nr_values ;i++) { 
      f(N-1, ans+i*pow(10,N), nr_values, specifier); //append the last digit to the integer 
     } 
    } 

    return; 
} 

Answer 2

你应该尽量实现回溯算法。我已经写下了相同的代码。为了更好的理解和可读性，我将代码分成许多函数。

• 解决方案向量是[N]，其中每个元素将通过backtrack（）函数填充。
• get_candidates()将返回可能数目的候选和候选[]向量为给定的插槽k。
• is_a_solution（）将返回true，如果解矢量被填满（即[]有N个元素被填充）。

。

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