如何使用递归打印出 C 中一系列数字的所有排列？

Question

我正在尝试制作一个递归函数，该函数将打印出具有整数数组重复项的所有排列，但数字有一个范围，数组大小也有范围。假设我们有一个数组 num[2] 并且它的范围是 0-1，例如，它会打印出类似

的内容

如果它是一个简单的排列，我可以使用这样一个简单的排列函数：

void permute(int *array,int i,int length) { 
  if (length == i){
     printArray(array,length);
     return;
  }
  int j = i;
  for (j = i; j < length; j++) { 
     swap(array+i,array+j);
     permute(array,i+1,length);
     swap(array+i,array+j);
  }
  return;
}

void swap(char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

但是如何让它通过给定数组大小的 n 大小的数字范围？

我的问题与这里的另一个问题不同，因为我没有包含值的集合数组，示例代码就是这样做的，但我需要的是帮助打印数组中范围 n 的所有排列k 个点，所以说 n 是 3，k 是 3 那么它将是

Answer 1

根据您的要求，您希望每个包含 n 个元素的数组和包含 k 个元素的结果数组打印所有 n^k 排列。所以在每个位置 i 我们必须放置数组的每个元素并为下一个继续这样做。像这样的代码：

void permute(int *array, int *result, int i, int n, int length) {
    if (length == i){
        printArray(result, length);
        return;
    }

    for (int j = 0; j < n; j++) {
        result[i] = array[j];
        permute(array, result, i + 1, n, length);
    }
}

int main()
{
    int a[] = { 0, 1, 2 }, b[2];
    permute(a, b, 0, 3, 2);
    return 0;
}

Answer 2

这个想法是通过将每个可能的数字连接到每个长度 n-1 的排列来生成长度 n 的排列。因此，如果您有数字 0-2 并且想要生成长度为 3 的排列，则首先生成长度为 2 的所有排列，然后附加或前置数字 0、1 和 2 给每一个：

长度为2的排列是：00,01,02,10,11,12,20,21,22

所以长度为 3 的排列是：000, 001, 002, 010, 011, 012, 020, 021, 022, 100, 101, 102, 110, 111, 112, 120, 121, 122, 200。 ..

那么，如何生成长度为 2 的所有排列？您生成长度为 1 的排列，并将您的每个数字添加到所有这些排列之前。如何生成长度为 1 的排列？没有长度为 0 的排列，所以你只列出数字。

这是伪代码：

permute(n, digits) {
    permutations = []
    smaller_permutations = permute(n-1, digits)
    for (i in digits) {
        if (length(smaller_permutation > 0) {
            for (j in smaller_permutations) {
                insert concatenate(i,j) into permutations
            }
        }
        else {
            insert i into permutations
        }
    }
    return permutations
}

如何使用递归打印出 C 中一系列数字的所有排列？

How to print out all the permutation of a range of numbers in C using recursion?

c

arrays

algorithm

recursion

permutation