A frequently asked problem in programming is about permutations. In this tutorial we will see how we can achieve permutation of words in a sentence (character permutation follows the same logic).

For increased performance we will use the function “next_permutation” from the C++ Standard Library which takes a sorted container (increasing order) and rearrange its elements each time it’s called till we have it fully permuted (sorted in decreasing order).

A simple way to create a function like this is:
- Sort your container (array) (for this example in increasing order)
- Give this array to your function and use a sorting method to sort it the other way it was sorted before (for this example in decreasing order)
- Each time that an element needs to be swapped it means that a new sequence has been created so we must save or print the sequence and then move on with the next change

The program below asks for the user to type a line of text (terminated by the NewLine character, ENTER button). Then it uses two functions to save the permutations of the words in the sentence in two different ways.

permuteInput_full = makes all the permutations available ( n! permutations – where n is the number of words)
permuteInput = makes the necessary permutations so as each one of the words in the sentence will be at least once at the beginning of it

Below we have the #includes, function prototypes and the main() function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <vector>
#include <iostream>
#include <string>
#include <cctype>
#include <algorithm>
#include <iomanip>

using namespace std;

// PROTOTYPES
vector<string> sepInput(const string& input);
vector<string> permuteInput(const string& input);
vector<string> permuteInput_full(const string& input);

//*********************
// MAIN FUNCTION
//*********************
int main(){
    string input;
    vector<string> inputPermuted;
   
    // read the line from the user
    cout << "Enter your line: " << endl;
    getline(cin,input);
   
    // inputPermuted contains all the strings with each word appearing once as first
    if(input.size()!=0)
        inputPermuted = permuteInput(input);
    else{
        cout << "You have entered 0 length line" << endl;
        return 1;
    }
    // display the partial permuted sentences  
    cout << "\nYour text partially permuted is:\n" << endl;
    for(vector<string>::size_type j=0;j<inputPermuted.size();j++)
        cout << left << setw(2) << j+1 << ": " << inputPermuted[j] << endl;
       
    // display the FULL permuted sentences
    inputPermuted=permuteInput_full(input);
    cout << "\nYour text fully permuted is:\n" << endl;
    for(vector<string>::size_type j=0;j<inputPermuted.size();j++)
        cout << left << setw(2) << j+1 << ": " << inputPermuted[j] << endl;
       
    return 0;
}

Now we can see how each one of the functions work:

sepInput = takes the line entered by the user and creates a vector (array) where each one of the words is an element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//*********************
// Functions Definement
//*********************

// separates the input sentence into each word
vector<string> sepInput(const string& input){
    vector<string> inputSeparated;
    string::size_type i,j;
   
    i=0;
    while(i<input.size()){
        // i is the first character in a word
        while(i<input.size() && isspace(input[i]))
            i++;
        j=i;
        // j is the character right after the last char of the word
        while(j<input.size() && !isspace(input[j]))
            j++;
        // if i!=j it means that there is a word to add into the vector
        if(i!=j){
            inputSeparated.push_back(input.substr(i,j-i));
            i=j;
        }
    }
    return inputSeparated;
}

This is the code for:
permuteInput_full = makes all the permutations available ( n! permutations – where n is the number of words)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// complete permutation of the words ( n! permutations )
vector<string> permuteInput_full(const string& input){
    vector<string> inputSeparated,inputPermuted;
   
    // inputSeparated contains each word as a different element
    inputSeparated = sepInput(input);
    //we sort the inputSeparated vector in order to use it in next_permutation algorithm
    stable_sort(inputSeparated.begin(),inputSeparated.end());
   
    // our permutation is made by the "next_permutation" function in <algortihm> header
    // each time we savethe permutation into a string and add it to our vector containing all the permutations
    vector<string>::size_type inputSep_size=inputSeparated.size();
    do{
        // creates the permuted line for this turn using the temporary strin currentPermutation
        string currentPermutation;
        for(vector<string>::size_type j=0;j<inputSep_size;j++)
            currentPermutation += inputSeparated[j] + " ";
        // delete the last whitespace
        currentPermutation.erase(currentPermutation.size()-1,1);
           
        // add the currentPermutation to our vector
        inputPermuted.push_back(currentPermutation);
       
    }while(next_permutation(inputSeparated.begin(),inputSeparated.end()));
   
    // return all the permutations
    return inputPermuted;
}

The code for:
permuteInput = makes the necessary permutations so as each one of the words in the sentence will be at least once at the beginning of it

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// permutation so as every word is indexed FIRST at the sentence once
vector<string> permuteInput(const string& input){
    vector<string> inputSeparated,inputPermuted;
   
    // inputSeparated contains each word as a different element
    inputSeparated = sepInput(input);
   
    vector<string>::size_type i=0,inputSep_size=inputSeparated.size();
    while(i<inputSep_size){
        // creates the permuted line for this turn using the temporary strin currentPermutation
        string currentPermutation;
        for(vector<string>::size_type j=0;j<inputSep_size;j++)
            currentPermutation += inputSeparated[j] + " ";
        // delete the last whitespace
        currentPermutation.erase(currentPermutation.size()-1,1);
           
        // add the currentPermutation to our vector
        inputPermuted.push_back(currentPermutation);
       
        // rearrange the words
        string temp=inputSeparated.front();
        inputSeparated.erase(inputSeparated.begin());
        inputSeparated.push_back(temp);
       
        i++;
    }
   
    return inputPermuted;
}

As you may noticed this code is in C++ Language so you should use an appropriate compiler. For C users who are used to (gcc) you can use the (g++) compiler in the same way.

Thank you for reading this tutorial and for any questions or suggestions please comment !!!