Search for array permutations without loops

Question

I saw this interview question on LinkedIn here

To summarize if I have an array

[1,2,3,4,5]

and input

3

I need a conclusion

[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 a certain order.

I already thought about it. I came up with various solutions, but all methods use for-loops.

I think it is clear that in order to exclude loops, it must be recursive.

It seemed to me that I did this very closely, recursively splitting the array and combining the elements, but with great disappointment I ended up requiring another loop.

It seems to me that this is impossible (which cannot be, otherwise why the question of an interview?).

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

Answer 1

{1,.., n}. 0 2 ^ n-1 : x 0 2 ^ n-1, , 1, x , 2, x ,...

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 , " ... , .

, , - for-loops, .

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

.

Answer 4

, for-loop, for-loop.

, . 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 5

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)

: , node - , node . , , ,

Answer 6

JavaScript. - choose, , (permutator SO, , : 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);
}

:

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