不需要for循环的数组排列的求取

Question

我在LinkedIn 这里上看到了这个采访问题

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

[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循环。

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

有什么想法或联系吗？可能输出的数量应该是5PN，其中N是输入。

Answer 1

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

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循环是没有意义的，有意义的是以一种明智的方式使用它们。

Answer 2

你的第一个想法是对的。每个循环都可以用递归代替。在某些语言(例如Scheme)中，循环实际上是用递归实现的。因此，只要从任何一个解决方案开始，然后继续将循环转换为递归。最终你会完蛋的。

下面是Python中的一个工作解决方案。

def subsets_of_size (array, size, start=0, prepend=None):
    if prepend is None:
        prepend = [] # Standard Python precaution with modifiable defaults.
    if 0 == size:
        return [[] + prepend] # Array with one thing.  The + forces a copy.
    elif len(array) < start + size:
        return [] # Array with no things.
    else:
        answer = subsets_of_size(array, size, start=start + 1, prepend=prepend)
        prepend.append(array[start])
        answer = answer + subsets_of_size(array, size-1, start=start + 1, prepend=prepend)
        prepend.pop()
        return answer

print subsets_of_size([1,2,3,4,5], 3)

Answer 3

您可以在这里使用递归，每次调用内部级别时，都会给出数组中的位置，当它返回时返回一个增加的位置。为此您将使用一个while循环。

伪码：

int[] input = [1,2,3,4,5];
int level = 3;

int PrintArrayPermutation(int level, int location, string base)
{
    if (level == 0)
    {
        print base + input[location];
        return location + 1;
    }

    while (location <= input.Length)
    {
        location = 
            PrintArrayPermutation(level - 1, location, base + input[location]);
    }
}

这是我的想法的一个非常基本的大纲。