我在 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 循环。
我认为很明显，为了消除循环，它必须是递归的。
我以为我已经接近递归地分区数组和连接元素了，但是非常沮丧，我最终需要另一个 for 循环。
我开始认为这是不可能的（这是不可能的，否则为什么要问面试问题？）。
有什么想法或链接吗？可能的输出数量应为 5PN，其中 N 是输入。
以下递归算法将尝试打印 {1,.., n} 的每个子集。这些子集通过以下双射与 0 到 2^n-1 之间的数字一对一：对于 0 到 2^n-1 之间的整数 x，如果 x 的第一位设置为，则关联包含 1 的集合1, 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 循环是没有意义的，有意义的只是以聪明的方式使用它们。
你的第一个想法是对的。每个循环都可以用递归代替。在某些语言中（例如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)
我认为解决方案不是不使用 for 循环，而是有一种使用 for 循环的最佳方法。
因此，就有了堆算法。以下来自 wiki http://en.wikipedia.org/wiki/Heap%27s_algorithm
procedure generate(n : integer, A : array of any):
if n = 1 then
output(A)
else
for i := 0; i < n; i += 1 do
generate(n - 1, A)
if n is even then
swap(A[i], A[n - 1])
else
swap(A[0], A[n-1])
end if
end for
end if
define listPermutations:
input: int p_l , int[] prevP , int atElement , int[] val , int nextElement
output: list
if nextElement > length(val) OR atElement == p_l OR contains(prevP , val[nextElement]
return EMPTY
list result
int[] tmp = copy(prevP)
tmp[atElement] = val[nextElement]
add(result , tmp)
//create the next permutation stub with the last sign different to this sign
//(node with the same parent)
addAll(result , listPermutations(p_l , tmp , atElement , val , nextElement + 1))
//create the next permutation stub with an additional sign
//(child node of the current permutation
addAll(result , listPermutations(p_l , tmp , atElement + 1 , val , 0))
return result
//this will return the permutations for your example input:
listPermutations(3 , new int[3] , 0 , int[]{1 , 2 , 3 , 4 , 5} , 0)
基本思想：给定数量元素的所有排列形成一棵树，其中节点是空排列，并且节点的所有子节点都有一个附加元素。现在算法要做的就是逐层遍历这棵树，直到该层等于排列所需的长度并列出该层上的所有节点
您可以在这里使用递归，每次调用内部级别时，您都给它它在数组中的位置，当它返回时，它返回一个增加的位置。为此，您将使用一个
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]);
}
}
这是我想法的一个非常基本的轮廓。
这是 JavaScript 中的两个递归函数。第一个是组合
choosepermutatorfunction c(n,list){
var result = [];
function _c(p,r){
if (p > list.length)
return
if (r.length == n){
result = result.concat(permutator(r));
} else {
var next = list[p],
_r = r.slice();
_r.push(next)
_c(p+1,_r);
_c(p+1,r);
}
}
_c(0,[])
return result;
}
function permutator(inputArr) {
var results = [];
function permute(arr, memo) {
var cur, memo = memo || [];
function _permute (i,arr,l){
if (i == l)
return
cur = arr.splice(i,1);
if (arr.length === 0){
results.push(memo.concat(cur));
}
permute(arr.slice(), memo.concat(cur));
arr.splice(i, 0, cur[0]);
_permute(i + 1,arr,l)
}
_permute(0,arr,arr.length);
return results;
}
return permute(inputArr);
}
输出：
console.log(c(3,[1,2,3,4,5]))
[[1,2,3],[1,3,2],[2,1,3]...[4,5,3],[5,3,4],[5,4,3]]
我们可以使用递归以及使用队列来完成。
注意：它使用循环而不是多个循环
使用递归：
function permutations(items, size, withReplacement=false, results = [[]]) {
if(size === 0) {
return results;
}
const newResults = [];
results.forEach((arr) => {
items.forEach((item) => {
if(withReplacement || !arr.includes(item)) {
newResults.push([...arr, item])
}
})
})
console.log(newResults);
return permutations(items, size - 1, withReplacement, newResults)
}
使用队列：
function permutationsWithQue(items, size, withReplacement=false) {
const queue = [[]];
const results = [];
while(queue.length) {
const curPerm = queue.shift()
for(const item of items) {
if(!withReplacement && curPerm.includes(item)) {
continue;
}
const newPerm = [...curPerm, item];
if(newPerm.length === size) {
results.push(newPerm);
}
else {
queue.push(newPerm)
}
}
}
console.log(results);
return results;
}
调用函数如
permutations([1, 2, 3, 4,5], 3, false);
permutationsWithQue([1, 2, 3, 4,5], 3, false);