查找数组中数字的所有可能排列

我有一个数组包含让我们说[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

找到所有排列和排列的数量有几个方面。 通过下面的注释显示，要计算n元素总数中k大小组的排列数，可以找到n上的阶乘除以可构成n元素的k大小组数的阶乘。 对于查找四元素arrays中所有4个元素的所有排列的情况，存在24可能的排列。

然后递归地找到可用的排列。 如果您有任何疑问，请查看以下内容并告诉我：

 #include  #include  void swap (int *x, int *y); unsigned long long nfact (size_t n); unsigned long long pnk (size_t n, size_t k); void permute (int *a, size_t i, size_t n); void prnarray (int *a, size_t sz); int main (void) { int array[] = { 25, 15, 8, 20 }; size_t sz = sizeof array/sizeof *array; /* calculate the number of permutations */ unsigned long long p = pnk (sz , sz); printf ("\n total permutations : %llu\n\n", p); /* permute the array of numbers */ printf (" permutations:\n\n"); permute (array, 0, sz); putchar ('\n'); return 0; } /* Function to swap values at two pointers */ void swap (int *x, int *y) { int temp; temp = *x; *x = *y; *y = temp; } /* calculate n factorial */ unsigned long long nfact (size_t n) { if (n <= 0) return 1; unsigned long long s = n; while (--n) s *= n; return s; } /* calculate possible permutations */ unsigned long long pnk (size_t n, size_t k) { size_t d = (k < n ) ? n - k : 1; return nfact (n) / nfact (d); } /* permute integer array for elements 'i' through 'n' */ void permute (int *a, size_t i, size_t n) { size_t j; if (i == n) prnarray (a, n); else for (j = i; j < n; j++) { swap ((a+i), (a+j)); permute (a, i+1, n); swap ((a+i), (a+j)); // backtrack } } void prnarray (int *a, size_t sz) { size_t i; for (i = 0; i < sz; i++) printf (" %2d", a[i]); putchar ('\n'); } 

使用/输出

 $ ./bin/permute4int total permutations : 24 permutations: 25 15 8 20 25 15 20 8 25 8 15 20 25 8 20 15 25 20 8 15 25 20 15 8 15 25 8 20 15 25 20 8 15 8 25 20 15 8 20 25 15 20 8 25 15 20 25 8 8 15 25 20 8 15 20 25 8 25 15 20 8 25 20 15 8 20 25 15 8 20 15 25 20 15 8 25 20 15 25 8 20 8 15 25 20 8 25 15 20 25 8 15 20 25 15 8 

注意：对于字符串，此方法可以正常工作，但不会导致对可能的排列进行词法排序。

Answer 2

• 诀窍是，你不能只置换相邻的值，看看当3固定在index = 1时，4永远不会放弃它，所以你必须逐渐将排列扩展到更多的值。

   #include  #include  #include  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((ji)==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 

看到它在这里运行