c - 在 C 中查找长度增加的数字列表的排列

Question

考虑以下数字列表:0, 1, 2, 3
我试图找到长度为 2、3 和 4 的列表的所有排列。

即

(0, 1)
(0, 2)
(0, 3)
(1, 0)
(1, 2)
(1, 3)
(2, 0)
(2, 1)
(2, 3)
(3, 0)
(3, 1)
(3, 2)
(0, 1, 2)
(0, 1, 3)
(0, 2, 1)
(0, 2, 3)
(0, 3, 1)
(0, 3, 2)
(1, 0, 2)
(1, 0, 3)
(1, 2, 0)
(1, 2, 3)
(1, 3, 0)
(1, 3, 2)
(2, 0, 1)
(2, 0, 3)
(2, 1, 0)
(2, 1, 3)
(2, 3, 0)
(2, 3, 1)
(3, 0, 1)
(3, 0, 2)
(3, 1, 0)
(3, 1, 2)
(3, 2, 0)
(3, 2, 1)
(0, 1, 2, 3)
(0, 1, 3, 2)
(0, 2, 1, 3)
(0, 2, 3, 1)
(0, 3, 1, 2)
(0, 3, 2, 1)
(1, 0, 2, 3)
(1, 0, 3, 2)
(1, 2, 0, 3)
(1, 2, 3, 0)
(1, 3, 0, 2)
(1, 3, 2, 0)
(2, 0, 1, 3)
(2, 0, 3, 1)
(2, 1, 0, 3)
(2, 1, 3, 0)
(2, 3, 0, 1)
(2, 3, 1, 0)
(3, 0, 1, 2)
(3, 0, 2, 1)
(3, 1, 0, 2)
(3, 1, 2, 0)
(3, 2, 0, 1)
(3, 2, 1, 0)

我需要在 C 中实现它，但是我发现的所有算法 [1,2] 只给出长度等于数字列表长度的排列，即仅来自 (0, 1, 2, 3) 的结果在上面的块中。将长度从 4 减少到 3 仅给出列表 0, 1, 2 的排列.

我目前可以使用 itertools.permutation 在 Python 中实现我想要的，如下图。

import itertools

MaxN = 4

for Length in range(2, MaxN + 1):
    for perm in itertools.permutations(Indices, Length):
        print perm

关于如何在 C 中实现这一点的任何建议将不胜感激。

[1] http://rosettacode.org/wiki/Permutations#C

[2] http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

Answer 1

您可以通过对 [2] 稍加修改来做到这一点:

/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string.
   4. Length of permutation */
void permute(char *a, int i, int n, int m) 
{
   int j; 
   if (i == m)
   {
       char temp = *(a+i);
       *(a+i) = '\0';
       printf("%s\n", a);
       *(a+i) = temp;
   }
   else
   {
       for (j = i; j <= n; j++)
       {
          swap((a+i), (a+j));
          permute(a, i+1, n, m);
          swap((a+i), (a+j)); //backtrack
       }
   }
} 

会像这样使用:

char a[] = "0123";  
for (int i = 2; i <= 4; i++)
    permute(a, 0, 3, i);

这给出了与您的 Python 实现相同的结果。