C++ std::next_permutation with std::array














































C++ std::next_permutation with std::array



 This article is about the next_permutation() algorithm function with std::array container. 
It is an STL algorithm in <algorithm> header file. It rearranges the elements in range
 [first, last) to the next lexicographically greater permutation. If there are N distinct 
 elements then there is N! different permutations. Different permutations can be ordered 
 according to how they compare lexicographically to each other.

next_permutation() can take two forms:
(1) template <class BidirectionalIterator>
bool next_permutation (BidirectionalIterator first,
BidirectionalIterator last);
(2) template <class BidirectionalIterator, class Compare>
bool next_permutation (BidirectionalIterator first,
BidirectionalIterator last, Compare comp);

If the function can determine the next higher permutation, it rearranges the elements as
 such and returns true. If that was not possible (because it is already at the largest 
 possible permutation), it rearranges the elements according to the first permutation 
 (sorted in ascending order) and returns false.
 
Two elements are compared equal using operator '<' in definition (1) or by using a
comp function in definition (2).

Here the first definition is discussed.

 Program: 
 We have to find all the possible words that can be formed using a given word.
 e.g.: If the word is "cat", then possible words formed are cat, act, atc, tac, tca and so
 on till 3!

#include<iostream>
#include<algorithm>
    #include<string.h>

    using namespace std;
    // to find the factorial of a given number (here the number of letters of the word)
    int fact(int a)
    {
        int k=1;
        while(a>1)
        {       
            k*=a;
            a--;
        }
        return k;
    }

    int main()
    {
        int i,l,a[26],num;
        char str[20];

        for(i=0;i<26;i++)
            a[i]=0;

        cout<<"Enter a word in uppercase: ";
        cin>>str;
        
        l=strlen(str);
        // to check if any letter is repeating we calculate the frequency of each letter in the word
        for(i=0;i<l;i++)
            a[str[i]-65]++;
            
        num=fact(l);

        // calculate total number of words formed using given letters(like
        //if a letter is repeating 3 times we divide the total num by 3)
        for(i=0;i<26;i++)
            if(a[i]>1)
                num/=a[i];

        // finding all the words after the permutation
        for(i=0;i<num;i++)
        {
            cout<<endl<<str;
            next_permutation(str,str+l);
        }
        return 0;
    }

Comments