Digit permutations

[DDomjosa]

Hi, I need to find all the permutions of some digits (or letters). This is my approach of finding all the permutations of the digits 0, 1, 2:

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
int combine(std::vector<int>&);
int main()
{
    int dig[3] = {0, 1, 2};
    std::vector<int> permutations, tempDigits;
    for (int a=0;a<3;a++)
    {
        for (int b=0;b<3;b++)
        {
            if (b == a) //Checking so it doesn't repeat the digits
                continue;
            for (int c=0;c<3;c++)
            {
                if (c == a || c == b)
                    continue;
                tempDigits.push_back(a);
                tempDigits.push_back(b);
                tempDigits.push_back(c);
                permutations.push_back(combine(tempDigits));
                tempDigits.clear();
            }
        }
    }
    for (int i=0;i<permutations.size();i++)
        std::cout << permutations[i] << " ";
}
int combine(std::vector<int>& digits) //This function takes a vector of digits (for example {1, 2, 3} and returns a digit that is the combination of those (123).
{
    std::string str;
    for (int i=0;i<digits.size();i++)
        str += std::to_string(digits[i]);
    int num;
    std::istringstream(str) >> num;
    return num;
}

It works and it's ok for 3 digits, but if I wanted to do all 10 or maybe even the whole alphabet, it would be a pain to write 26 or even 10 nested for loops. If you have any ideas on how to optimize this and how to make it flexible so I don't need to alter the source code for a different number of digits, please let me know. Thanks!

[dhayden]

You can do this using recursion. Given an array, you permute like this:
for each position N in the array
swap the first item with the Nth item
find all permutations of the array, starting with the second item
swap the first item and Nth items back.

[DDomjosa]

Ok, so I implemented your idea and it works for {0, 1, 2}:

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
unsigned long long int combine(std::vector<int>&);
void permutation(std::vector<int>&, std::vector<unsigned long long int>&, int);

int main()
{
    std::vector<unsigned long long int> permutations;
    std::vector<int> digits;
    for (int i=0;i<3;i++)
        digits.push_back(i);
    permutation(digits, permutations, 1);
    std::sort(permutations.begin(), permutations.end());
    for (int i=0;i<permutations.size();i++)
        std::cout << permutations[i] << " ";
}
unsigned long long int combine(std::vector<int>& digits)
{
    std::string str;
    for (int i=0;i<digits.size();i++)
        str += std::to_string(digits[i]);
    unsigned long long int num;
    std::istringstream(str) >> num;
    return num;
}
void permutation(std::vector<int>& digits, std::vector<unsigned long long int>& permutations, int counter)
{
    unsigned long long int tempPermutation = combine(digits);
    if (!permutations.size() || permutations[0] != tempPermutation)
    {
        permutations.push_back(tempPermutation);
        std::swap(digits[0], digits[counter]);
        counter++;
        if (counter >= digits.size())
            counter = 1;
        permutation(digits, permutations, counter);
    }
    else return;
}

But if I change the line 13 to this: for (int i=0;i<4;i++), it doesn't give me the right results. Why is this?