Dynamic Programming - Generate Permutation Set

1. Problem Description

This is a Google interview question for software developer engineer from careercup. Here is the original thread,

"

Given a set of values 0-9, return all permutations of that set of length n. Example: n=2, set ={2,3,4} Return: {2,2}, {3,3}, {4,4}, {2,3}, {3,2}, {3,4}, {4,3}, {2,4}, {4,2}

- PradeepN about a month ago in United States | Report Duplicate | Flag ".

2. Analysis

This is a similar sort of problem like Dynamic programming - Generate power set given a set. Again the key is to find the sub-problem.
Assume a given set as S with M elements and N, S = {x1, x2, ..., xm}.
    - N = 1, F(1) = {{x1}, {x2}, ..., {xm}}
    - N = 2, F(2) = {{x1, x1}, {x1, x2}, ..., {x1, xm},
                            {x2, x1}, {x2, x2}, ..., {x2, xm},
                                       ......
                            {xm, x1}, {xm, x1}, ..., {xm, xm}}
    - Assume N-1, F(N-1) = {X1, X2, ..., Xk}, where k = M^(N-1)
    - N, F(N) = {{X1, x1}, {X1, x2}, ..., {X1, xm},
                       {X2, x1}, {X2, x2}, ..., {X2, xm},
                                      ......
                       {Xk, xm},  {Xk, xm}, ..., {Xk, xm}}, total k*M = M^N

As long as F(n-1) is known, then F(n) can be compute as each set of F(n-1) combining with each element in S to form the new set. And the size of set can be easily computed as M^n.

3. C++ Implementation and Test

- Given set with size M

- Given N.

    * if N = 0, then return empty set

    * if N > M, then return empty set as well.

    * Otherwise return the permutation set with size of power(M, N).

// ********************************************************************************

// Implementation

// ********************************************************************************

#include <vector>

template<typename T>

void PermuteSet(std::vector<T> const &input, size_t len, std::vector<std::vector<T>> &result)

{

    if (len == 0) {

        return;

    }

    const size_t currentSize = result.size();

    auto iter = input.begin();

    auto iterEnd = input.end();

    if (currentSize == 0) {

        // very first time

        for (; iter != iterEnd; ++iter) {

            std::vector<T> initialSet(1, *iter);

            result.push_back(initialSet);

        }

    }

    else {

        auto iterBeginOfResult = result.begin();

        ++iter;

        // Keep F(n-1) and generate the values for F(n)

        for (; iter != iterEnd; ++iter) {

            size_t count = 0;

            for (auto iterOfResult = iterBeginOfResult; count < currentSize; ++iterOfResult, ++count) {

                std::vector<T> copy(*iterOfResult);

                copy.push_back(*iter);

                result.push_back(copy);

            }

        }

        // Update F(n-1) as elements of F(n) 

        size_t count = 0;

        auto firstVal = input.begin();

        for (auto iterOfResult = iterBeginOfResult; count < currentSize; ++iterOfResult, ++count) {

            (*iterOfResult).push_back(*firstVal);

        }

    }

    PermuteSet(input, len - 1, result);

}

template<typename T>

std::vector<std::vector<T>> PermuteSet(std::vector<T> const &input, size_t len)

{

    if (input.empty() || len == 0 || len > input.size()) {

        return std::vector<std::vector<T>>();

    }

    std::vector<std::vector<T>> result;

    result.reserve(static_cast<size_t>(pow(input.size(), len)));

    PermuteSet(input, len, result);

    return result;

}

// ********************************************************************************

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

    }

}