2

考虑以下数字列表：0, 1, 2, 3

我试图找到长度为 2、3 和 4 的列表的所有排列。

IE

(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 只给出 list 的排列0, 1, 2。

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

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-ac-program-to-print-all-permutations-of-a-given-string/

4

4 回答 4

2

您可以通过对 [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 实现相同的结果。

于 2013-06-19T15:19:18.897 回答
1

您可以使用组合生成算法，该算法将吐出 C(n, k) 组合的序列以在外循环中增加 k，并应用 P(k, k) 置换算法为每个组合生成置换序列。

c = empty_combination();
for (k = 0; k <= n; ++k) {
    do {
        c = next_combination(c, sequence, k);
        p = empty_permutation();
        do {
            p = next_permutation(p, c);
            print_permutation(p);
        } while (! is_empty_permutation(p));
    } while (! is_empty_combination(c));
}
于 2013-06-19T15:17:54.480 回答
0

在 C++ 中执行此操作非常简单。使用 (next_permutation()) 方法。

http://www.cplusplus.com/reference/algorithm/next_permutation/

于 2013-06-19T15:19:16.023 回答
0

这是生成所有子集的迭代方法！
子集的总数是 2^n - 1
所以它生成所有长度的子集。
如果您想要特定长度的子集，只需添加一个计数器并检查您是否正在打印特定长度。

main(){
int a[]={0,1,2,3};
int n=pow(2,4) - 1;
for(int i=0;i<=n;i++){
    int p = i;
    int l=0;
    while(p){
        if(p%2==1)
            printf("%d",a[l]);
        p>>=1;
        l++;
    }
    printf("\n");
}
}
于 2013-06-19T16:51:30.387 回答