c - 查找数组中 n 个数字的所有可能排列

Question

我有一个数组，其中包含 [25,15,8,20] 我想找到所有可能的数字排列方式。

预期输出:

25 15 8 20
25 15 20 8
25 20 15 8
25 20 8 15
25 8 20 15
25 8 15 20
15 25 8 20
15 25 20 8
15 20 25 8
15 20 8 25
15 8 20 25
15 8 25 20
20 25 15 8
20 25 8 15
20 8 25 15
20 8 15 25
20 15 25 8
20 15 8 25
8 15 20 25
8 15 25 20
8 25 15 20
8 25 20 15
8 20 15 25
8 20 25 15


void print(int *num, int n)
{
 int i;
 for ( i = 0 ; i < n ; i++)
    printf("%d ", num[i]);
   printf("\n");
}
int main()
{
 int num[N];
 int *ptr;
 int temp;
 int i, n, j;
 printf("\nHow many number you want to enter: ");
    scanf("%d", &n);
 printf("\nEnter a list of numbers to see all combinations:\n");
 for (i = 0 ; i < n; i++)
    scanf("%d", &num[i]);
 for (j = 1; j <= n; j++) {
    for (i = 0; i < n-1; i++) {
        temp = num[i];
        num[i] = num[i+1];
        num[i+1] = temp;
        print(num, n);
 }
}
 return 0;
}

上面的程序没有给出所有可能的输出。我如何获得内部交换并获得组合

Answer 1

• 诀窍是，您不能只排列相邻的值，看到当 3 固定在索引 = 1 时，4 永远不会在它旁边，因此您必须逐渐将排列扩展到更多值。

  #include <stdio.h>  
  #include <string.h> 
  #include <malloc.h> 
  
  void print(int *num, int n) 
  {   
   int i; 
   for ( i = 0 ; i < n ; i++) 
      printf("%d ", num[i]);  
     printf("\n");    
  }   
  
  int*permute(int*i,int h)    
  {       
       int temp = *i; 
      *i = *(i+h);    
      *(i+h) = temp;  
  return i+1; 
  
  }   
  void recursive_permute(int*i,int *j,int n)  
  {   
      if((j-i)==n-1) {print(i,n);return;};
  
      int *tmparray=(int*)malloc(n*sizeof(int));
      memcpy(tmparray,i,n*sizeof(int));
      recursive_permute(tmparray,tmparray+(j-i+1),n);
  
      for (int h=1;h<n-(j-i);h++) recursive_permute(tmparray,permute(tmparray+(j-i),h),n);
  }   
  
  int main()  
  {   
   int num[100];  
   int *ptr;  
   int temp;  
   int i, n, j;   
   printf("\nHow many number you want to enter: ");   
      scanf("%d", &n);    
   printf("\nEnter a list of numbers to see all combinations:\n");    
   for (i = 0 ; i < n; i++)   
      scanf("%d", &num[i]);   
   printf("my recursive method ---------------------------\n");   
   recursive_permute(num,num,n);  
  
   printf("your method -----------------------------------\n");   
  
   for (j = 1; j <= n; j++) { 
      for (i = 0; i < n-1; i++) { 
          temp = num[i];  
          num[i] = num[i+1];  
          num[i+1] = temp;    
          print(num, n);  
   }  
  }   
   return 0;  
  }   
  

See it running here