CareerCup

The number of permutations is equal to the length of the array to the power of n, in our example it's 3^2 = 9;

Then we loop from 0 to the number of permutations calculated above, and treat each iteration as a number with base n,

void Permutations( std::vector<int>* input, int n )
{
   int j;
   int index;
   int number;
   size_t length = input->size();
   int total_permutations = pow( (double)length, (double)n );

   for ( int i = 0 ; i < total_permutations ; i++ )
   {
      number = i;
      for ( j = 0 ; j < n ; j++ )
      {
         index = number%length;
         
         std::cout << input->at(index) << ", ";
         number /= length;
      }

      std::cout << "\n";
   }
}

here is the output when n = 2
2, 2,
3, 2,
4, 2,
2, 3,
3, 3,
4, 3,
2, 4,
3, 4,
4, 4,

here is the output when n = 3

2, 2, 2,
3, 2, 2,
4, 2, 2,
2, 3, 2,
3, 3, 2,
4, 3, 2,
2, 4, 2,
3, 4, 2,
4, 4, 2,
2, 2, 3,
3, 2, 3,
4, 2, 3,
2, 3, 3,
3, 3, 3,
4, 3, 3,
2, 4, 3,
3, 4, 3,
4, 4, 3,
2, 2, 4,
3, 2, 4,
4, 2, 4,
2, 3, 4,
3, 3, 4,
4, 3, 4,
2, 4, 4,
3, 4, 4,
4, 4, 4,

// ZoomBA permutations 
def permutate ( n ){
   join( @ARGS = list([0:n]) -> { [0:n] } ) :: {
      #|set($.o)| == #|$.o|
   }
}
println( permutate(3) )

c++, implementation
{2, 3, 4}, 2 => {2, 2}, {2, 3}, {2, 4}, {3, 2}, {3, 3}, {3, 4}, {4, 2}, {4, 3}, {4, 4}

bool nextIndex(vector<int>& indexes, int size) {
	int i, up;

	up = 0;
	i = indexes.size() - 1;
	indexes[i]++;
	while (i >= 0) {
		indexes[i] += up;
		if (indexes[i] < size) return true;
		indexes[i] = 0;
		up = 1;
		i--;
	}

	return false;
}

vector<vector<int>> getPermutation(vector<int>& arr, int n) {
	vector<vector<int>> permutations;
	
	if (arr.size() == 0 || n <= 0 || arr.size() < n) return permutations;

	vector<int> indexes;
	vector<int> item;
	int i;

	indexes.assign(n, 0);

	while (true) {
		item.clear();
		for (i = 0; i < indexes.size(); i++) {
			item.push_back(arr[ indexes[i] ]);
		}
		permutations.push_back(item);
		if (nextIndex(indexes, arr.size()) == false) break;
	}

	return permutations;
}

void PrintPermutations(char permutation[], char alpha[], int n, int current_len, int expected_len)
{
    if (current_len == expected_len)
    {
        for (int i = 0; i < expected_len; ++i)
        {
            std::cout << permutation[i];
        }

        std::cout << std::endl;
        
        return;
    }

    for (int i = 0; i < n; ++i)
    {
        permutation[current_len] = alpha[i];
        PrintPermutations(permutation, alpha, n, current_len + 1, expected_len);
    }
}

In Java:

List<String> result = new ArrayList<>();
        Set<Integer> valueSet = new HashSet<>();
        valueSet.add(2);
        valueSet.add(3);
        valueSet.add(4);

        Iterator<Integer> outerIter = valueSet.iterator();
        while (outerIter.hasNext()) {
            Integer outerValue = outerIter.next();
            Iterator<Integer> innerIter = valueSet.iterator();
            while (innerIter.hasNext()) {
                Integer innerValue = innerIter.next();
                result.add(outerValue.toString() + " " + innerValue.toString());
            }
        }

        System.out.println(result);

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

vector<unordered_set<int>> permutations(vector<int> & givenSet, int N) {
    vector<unordered_set<int>> result;
    
    if(N == 1) {
        for(int i = 0; i < givenSet.size(); ++i) {
            unordered_set<int> perm;
            perm.insert(givenSet[i]);
            result.push_back(perm);
        }
        return result;
    } else if(N>1) {
        vector<unordered_set<int>> resultMinusOne = permutations(givenSet, N-1);
        for(int j = 0; j < resultMinusOne.size(); ++j) {
            for(int i=0; i<givenSet.size(); ++i) {
                unordered_set<int> temp = resultMinusOne[j];
                temp.insert(givenSet[i]);
                if(temp.size() == N) {
                    result.push_back(temp);
                }
            }
        }
    }
    return result;
}

import java.util.ArrayList;
import java.util.List;

/**
* Created by dbabu on 10/27/15.
*/
public class Permute {
public void permute(int[] array, int index, List<Integer> store, int constant){
for(int i=0;i<array.length ;i++){
store.add(constant - index, array[i]);
if(index == 0)
{
for(Integer a : store)
System.out.print(a);
System.out.println();
}
else
permute(array, index - 1, store, constant);
store.remove(constant - index);
}
}
public static void main(String[] args) {
int[] a = {2,3,4};
Permute p = new Permute();
p.permute(a, 1, new ArrayList<>(),1);
}
}

C# version

public List<List<int>> GetResult(List<int> input, int n)
{
List<List<int>> result = new List<List<int>>();
if (n <= 0 || !input.Any())
{
return result;
}

result.AddRange(from item in input select new List<int> { item });

if (n == 1)
{
return result;
}

int current = 2;

return BuildResult(current, n, input, result);

}

List<List<int>> BuildResult(int current, int n, List<int> input, List<List<int>> result)
{
if (current > n)
{
return result;
}

List<List<int>> newResult = new List<List<int>>();
foreach (List<int> item in result)
{
foreach (int i in input)
{
List<int> newItem = new List<int>(item);
newItem.Add(i);
newResult.Add(newItem);
}
}

current++;

return BuildResult(current, n, input, newResult);
}

public List<List<int>> GetResult(List<int> input, int n)
        {
            List<List<int>> result = new List<List<int>>();
            if (n <= 0 || !input.Any())
            {
                return result;
            }

            result.AddRange(from item in input select new List<int> { item });

            if (n == 1)
            {
                return result;
            }

            int current = 2;

            return BuildResult(current, n, input, result);

        }

        List<List<int>> BuildResult(int current, int n, List<int> input, List<List<int>> result)
        {
            if (current > n)
            {
                return result;
            }

            List<List<int>> newResult = new List<List<int>>();
            foreach (List<int> item in result)
            {
                foreach (int i in input)
                {
                    List<int> newItem = new List<int>(item);
                    newItem.Add(i);
                    newResult.Add(newItem);
                }
            }

            current++;

            return BuildResult(current, n, input, newResult);
        }

My solution is similar to koosha.nejad's
Dynamically generate:
1. count from 1 to m^n
2. convert index to base-m
3. convert each digit into index into element set
4. construct next value

def convert_to_base(num, base):
        digits = []
        while num > 0:
                digits.append(num % base)
                num = num / base
        digits.reverse()
        return digits

def set_permute(element_set, n):
        for i in xrange(0, len(element_set)**n):		# Step 1.
                digits = convert_to_base(i, len(element_set))  		#Step 2.
                for k in range(0, n - len(digits)):				#Step 3.
                        digits.insert(0, 0)

                next_element = [element_set[digit] for digit in digits]    #Step 4.
                yield next_element

Analysis:
Memory usage virtually eliminated, though convert_to_base is more computationally intensive. However, this a
lgorithm is embarrassingly parallelizable.

def permute_set(pref, sets, length):
  if len(pref) == length:
    print pref
  else:
    for i in sets:
      se = list(pref)
      se.append(i)
      permute_set(se, sets, length)

def main():
  sets = {2,3,4, 5}
  length = 4
  se= []
  count = 0
  permute_set(se, sets, length)



if __name__ == '__main__':
  main()

Recursive solution in c.

gcc -Wall -Werror permutations.c -o permutations

/* file: permutations.c */

#include <stdlib.h>
#include <stdio.h>


/* Compute the k-permutations of an array of size n
 * and print them to stdout 
 *
 * @param array   pointer to the population array
 * @param n       size of population array
 * @param k       size of permutations
 * @param perm    pointer to an array that contains 1 permutation
 * @param pos     current position to fill in the perm array
 */
void permutations(const int *array, const int n, const int k, int *perm, int pos)
{
  /* each recursive call take care of the pos-th element
   * in the perm array  */
  for(int i=0; i<n; i++)
    {
      /* fill the pos-th element in the perm array, with
       * the i-th element of array */
      perm[pos] = array[i];
      if(pos == k-1)
        {
          /* if this is the last element in perm, then we
           * can print its current state */

          for(int j=0; j < k; j++)
            {
              fprintf(stdout,"%d ", perm[j]);
            }
          fprintf(stdout,"\n");
        }
      else
        { /* otherwise we move on and take care of the next element */
          permutations(array, n, k, perm, pos+1);
        }
    }
}


int main()
{
  const int n = 10;
  const int k = 2;
  int array[n];
  int perm[k];

  /* init array with some numbers */
  for(int i = 0; i <n; i++)
    {
      array[i] = i;
    }

  /* permutation must be called with pos = 0*/
  permutations(array, n, k, perm, 0);

  return 0;
}

Scala

object Solve extends App {

  def gen(elems:List[Int], n:Int): List[List[Int]] = {
    println( s"$elems $n" )
    if(n == 0) List(List())
    else if(elems.isEmpty) Nil
    else {
      gen(elems.tail, n) :::
        gen(elems, n - 1).map(elems.head :: _)
    }
  }


  println(gen(List(2,3,4), 2))

}

Concise solution in Scala

def gen(elems:List[Int], n:Int): List[List[Int]] = {
    if(n == 0) List(List())
    else if(elems.isEmpty) Nil
    else {
      gen(elems.tail, n) :::
        gen(elems, n - 1).map(elems.head :: _)
    }
  }

public static void printPerm(int[] set, int n) {
        int total = (int) Math.pow(set.length, n);
        for (int i = 0; i < total; ++i) {
            int num = i;
            for (int j = 0; j < n; ++j) {
                int index = num % set.length;
                num /= set.length;
                System.out.print(set[index] + " ");
            }
            System.out.println();
        }

}

import itertools
def permutations(s,n):
    for i in itertools.combinations_with_replacement(s,n):
        print(i)
        if i[0]!=i[1]:
            a=tuple(reversed(i))
            print(a)
    return 0
permutations([2,3,4],2)

output:

(2, 2)
(2, 3)
(3, 2)
(2, 4)
(4, 2)
(3, 3)
(3, 4)
(4, 3)
(4, 4)

A recursive approach in Python:
We generate all the permutations with length n - 1 and for each one of those we append any number we have in the array. In an interview, you may want to cover also the case when n <= 0.

def permutations(values, n):
    if n == 1:
        return [[x] for x in values]
    perms = permutations(values, n - 1)
    result = []
    for x in values:
        for perm in perms:
            new_perm = perm[:]
            new_perm.append(x)
            result.append(new_perm)
    return result

Dynamic solution. Iterate form n=1 upwards to reach n.
Details: cpluspluslearning-petert.blogspot.co.uk/2015/12/dynamic-programming-generate.html

Test

#include <cassert>
void TestSetPermutation()
{
    {
        const std::vector<int> input;
        auto result = PermuteSet(input, 0);
        assert(result.empty() == true);
        result = PermuteSet(input, 1);
        assert(result.empty() == true);
    }

    {
        const std::vector<int> input = { 1 };
        auto result = PermuteSet(input, 0);
        assert(result.empty() == true);
        result = PermuteSet(input, 2);
        assert(result.empty() == true);
        result = PermuteSet(input, 1);
        assert(result.size() == 1);
        assert(result[0].at(0) == 1);
    }

    {
        const std::vector<int> input = { 2, 3, 4, 5 };
        auto result = PermuteSet(input, 0);
        assert(result.empty() == true);

        result = PermuteSet(input, 1);
        assert(result.size() == 4);
        assert(result[0].size() == 1);
        assert(result[0].at(0) == 2);
        assert(result[1].size() == 1);
        assert(result[1].at(0) == 3);
        assert(result[2].size() == 1);
        assert(result[2].at(0) == 4);
        assert(result[3].size() == 1);
        assert(result[3].at(0) == 5);

        result = PermuteSet(input, 2);
        assert(result.size() == 16);
        for (auto iter = result.begin(); iter != result.end(); ++iter) {
            assert(iter->size() == 2);
        }
        assert((*result.begin()) == std::vector<int>({2, 2}));
        assert((*result.rbegin()) == std::vector<int>({5, 5}));

        result = PermuteSet(input, 3);
        assert(result.size() == 64);
        for (auto iter = result.begin(); iter != result.end(); ++iter) {
            assert(iter->size() == 3);
        }
        assert((*result.begin()) == std::vector<int>({ 2, 2, 2 }));
        assert((*result.rbegin()) == std::vector<int>({ 5, 5, 5 }));

        result = PermuteSet(input, 4);
        assert(result.size() == 256);
        for (auto iter = result.begin(); iter != result.end(); ++iter) {
            assert(iter->size() == 4);
        }
        assert((*result.begin()) == std::vector<int>({ 2, 2, 2, 2 }));
        assert((*result.rbegin()) == std::vector<int>({ 5, 5, 5, 5 }));

        result = PermuteSet(input, 6);
        assert(result.empty() == true);
    }
}

c++ solution:
Idea: if we expand one slot each time, it will require n times to get one instance. Each time (each slot) has m possibilities, where m be the size of set.

1. start from empty set
2. run n rounds, each round expand one slot based on previous set
3. In i-th round, for each existing instance in the set, we have m choices for the i-th slots. therefore one instance generates i-th instances
4. save the result of one round for next round (1 slot more).

Is this DP? I don't know. Anyone knows? But it is definitely using memorization technique. Time complexity is \sum_{i=1, n} m^i, which is m^n?

class Solution {
public:
    vector<vector<int>> npermute(vector<int>& arr, int n)
    {   
        vector<vector<int>> ans = {{}};
    
        for (int i = 0; i < n; i++) {
            vector<vector<int>> tmp;    
            for (auto v : ans) {
                for(int j = 0; j < arr.size(); j++) {
                    vector<int> t = v;
                    t.push_back(arr[j]);
                    tmp.push_back(t);
                }   
            }   
            ans.swap(tmp);
        }   
        return ans;
    }   
};
int main(int argc, char** argv)
{
    vector<int> a = {4, 2, 3, 1}; 
    Solution s;
    vector<vector<int>> res = s.npermute(a, 3); 
    for (auto v : res) {
        for (auto a : v)  
            std::cout << a << " ";
        std::cout << "\n";
    }   
    return 0;
}

public static void permutaitonsN(int start,int[] arr,int n,List<Integer> allP){
if(allP.size() == n){
for(int i=0;i<n;i++){
System.out.print(allP.get(i) + ",");
}
System.out.println();
return;
}
int i =start;
for(int j=i;j<arr.length;j++){

allP.add(arr[j]);
swap(arr,i,j);
permutaitonsN(i,arr,n,allP);
allP.remove(allP.size()-1);
swap(arr,j,i);
}

}

public static void permutaitonsN(int start,int[] arr,int n,List<Integer> allP){
		if(allP.size() == n){
			for(int i=0;i<n;i++){
				System.out.print(allP.get(i) + ",");
			}
			System.out.println();
			return;
		}
		int i =start;
		for(int j=i;j<arr.length;j++){
			
			allP.add(arr[j]);
			swap(arr,i,j);
			permutaitonsN(i,arr,n,allP);
			allP.remove(allP.size()-1);
			swap(arr,j,i);
		}
		
	}

public static void permutaitonsN(int start,int[] arr,int n,List<Integer> allP){
		if(allP.size() == n){
			for(int i=0;i<n;i++){
				System.out.print(allP.get(i) + ",");
			}
			System.out.println();
			return;
		}
		int i =start;
		for(int j=i;j<arr.length;j++){
			
			allP.add(arr[j]);
			swap(arr,i,j);
			permutaitonsN(i,arr,n,allP);
			allP.remove(allP.size()-1);
			swap(arr,j,i);
		}

}

List<List<Integer>> result = new ArrayList<>();
        Set<Integer> valueSet = new HashSet<>(Arrays.asList(2, 3, 4));

        Iterator<Integer> outerIter = valueSet.iterator();
        while (outerIter.hasNext()) {
            Integer outerValue = outerIter.next();
            Iterator<Integer> innerIter = valueSet.iterator();
            while (innerIter.hasNext()) {
                Integer innerValue = innerIter.next();
                result.add(Arrays.asList(outerValue, innerValue));
            }
        }

        System.out.println(result);

List<List<Integer>> result = new ArrayList<>();
        Set<Integer> valueSet = new HashSet<>(Arrays.asList(2, 3, 4));

        Iterator<Integer> outerIter = valueSet.iterator();
        while (outerIter.hasNext()) {
            Integer outerValue = outerIter.next();
            Iterator<Integer> innerIter = valueSet.iterator();
            while (innerIter.hasNext()) {
                Integer innerValue = innerIter.next();
                result.add(Arrays.asList(outerValue, innerValue));
            }
        }

        System.out.println(result);

It is a Dynamic Programming question folks.