Finding permutations of Array without for loops

Question

I saw this interview question on a LinkedIn group here

To summarise, if I have an array

[1,2,3,4,5]

and input

3

I require the output

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

In no particular order.

I have been thinking about this one for a while now. I have come up with various different ways of solving but all methods use for-loops.

I think it's clear that in order to eliminate loops it must be recursive.

I thought I got close to doing this recursively partitioning the array and joining elements, but with great frustration I ended up requiring another for loop.

Im beginning to think this is impossible (which it can't be, otherwise why the interview question?).

Any ideas or links? The amount of possible outputs should be 5PN, where N is the input.

Answer 1

The following recursive algorithm will attempt to print every subset of {1,.., n}. These subsets are in one to one with numbers between 0 and 2^n-1 via the following bijection: to an integer x between 0 and 2^n-1, associate the set that contains 1 if the first bit of x is set to one, 2 if the second bit of x is set to one, ..

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);
}

You need to call it with n = 5 (in your case), m=3 (in your case), and x = 0.

Then you need to implement the two functions "print the set corresponding to x" and "x has m bits set to one" without for loops... but this is easily done using again recursion.

However, I think this is more of a challenge -- there is no point in completely eliminating for-loops, what makes sense is just to use them in a smart way.

Answer 2

Your first thought is right. Every loop can be replaced with recursion. In some languages (for example Scheme), loops are actually implemented with recursion. So just start with any solution, and keep on turning loops into recursion. Eventually you will be done.

Here is a working solution in 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

I don't think the solution is not to use for-loop but there is an optimum way to use for-loop.

And so, there is the Heap's Algorithm. Below from 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

Answer 4

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)

Basic idea: all permutations of a given number of elements form a tree, where the node is the empty permutation and all childnodes of a node have one additional element. Now all the algorithm has to do is to traverse this tree level by level, until the level is equal to the required length of the permutation and list all nodes on that level

Answer 5

You could use recursion here, and every time you call an inner level, you give it the location it is in the array and when it returns it return an increased location. You'd be using one while loop for this.

Pseudo code:

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]);
 }
}

This is a very basic outline of my idea.

• shapiro yaacov: @vib. yes it is. Just re-read the question - I was under the impression the goal was one loop instead of two.
• Greg Peckory: Thanks for the help, I managed it with one loop also. Im wondering is it possible with no loops? While or For.
• shapiro yaacov: I actually think @vib is on to something here. Seeing how all the combinations can be represented as bits in a number, going through the number from 0 to 2^n-1 gives you all permutations. If you use recursion instead of a loop, that might do it. The remaining problem would be the actual print - you'll need a loop there...
• vib: No, you can do recursion (on the bit index). Start your recursive call with your number and an extra number target = 1 as parameter. You check whether last bit is one, if so you print target. Then divide the number by two, pass it to the recursive call along with target +1. Stop when number = 0.

Answer 6

Here are two recursive functions in JavaScript. The first is the combinatorial choose function to which we apply the second function, permuting each result (permutator is adapted from the SO user, delimited's, answer here: Permutations in JavaScript?)

function 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);
}

Output:

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]]

Answer 7

We can do it using recursion as well as using queue.

Note: it use loop but not multiple loops

With recursion:

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)
}

Using queue:

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;
}

Call function like

permutations([1, 2, 3, 4,5], 3, false);
permutationsWithQue([1, 2, 3, 4,5], 3, false);