arrays - 在没有 for 循环的情况下查找数组的排列

Question

我在 LinkedIn 群组上看到这个面试问题 here

总结一下，如果我有一个数组

[1,2,3,4,5]

并输入

3

我需要输出

[1,2,3], [3,2,1], [2,3,1], [2,1,3], [1,3,2], [3,1,2], [2,3,4], [4,3,2],...

排名不分先后。

我一直在想这个问题。我想出了各种不同的解决方法，但所有方法都使用 for 循环。

我认为很明显，为了消除循环，它必须是递归的。

我以为我已经接近于递归地对数组进行分区并连接元素，但非常沮丧，我最终需要另一个 for 循环。

我开始认为这是不可能的(这是不可能的，否则为什么面试问题？)。

有任何想法或链接吗？可能的输出量应该是 5PN，其中 N 是输入。

Answer 1

以下递归算法将尝试打印 {1,.., n} 的每个子集。这些子集通过以下双射与 0 和 2^n-1 之间的数字一对一:对于 0 和 2^n-1 之间的整数 x，如果 x 的第一位设置为，则关联包含 1 的集合one, 2 如果 x 的第二位设置为 1, ..

void print_all_subsets (int n, int m, int x) {
    if (x==pow(2,n)) {
        return;
    }
    else if (x has m bits set to one) {
        print the set corresponding to x;
    }
    print_all_subsets(n,m,x+1);
}

您需要使用 n = 5(在您的情况下)、m=3(在您的情况下)和 x = 0 来调用它。

然后您需要实现两个函数“打印对应于 x 的集合”和“x 将 m 位设置为 1”而不使用 for 循环...但这很容易再次使用递归完成。

但是，我认为这更具挑战性——完全消除 for 循环没有意义，有意义的是以巧妙的方式使用它们。