I have written a C++ program to print permutations of letters of a word. I want to know are there other simpler ways to do it?

Question

Here is the code. I have used a self calling function to create a nested loop of exact size(that is determined by the length of word entered by user) neccessary. I took me about 5hrs to write it and debug it. Have I over did it? Are there any other simpler ways to do it without using any specifically designed c++ library functions?

//PROGRAM TO PRINT ALL PERMUTAIONS OF LETTERS OF A WORD

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
char a[11],p[11];   //a to store the word entered
int flag;           //p to store a permutaion untill it is printed

void permute(int* chk,int n ,int pos)
{   int i,j,k;
    int nxtchk[10];
    flag=1;

    for(i=0; i<n ; i++ )
    {  for(j=0;j<n;j++)
        nxtchk[j]=1;

        if(chk[i])
        {
            p[pos]=a[i];
            chk[i]=0;
            for(j=0;j<=pos;j++)
                for(k=0;k<n;k++)
                   if(p[j]==a[k])
                     nxtchk[k]=0;

         if(pos+1<n)
            permute(nxtchk,n,pos+1);
        }
    }
    if(flag)  //flag used to ensure each permutation is printed once only
       { cout<<p<<"   "; flag=0; }
}

int main()
{
    int chk[10]={1,1,1,1,1,1,1,1,1,1};
    cout<<"Enter a word whose letters are all different: ";  gets(a);
    int n=strlen(a);
    p[n]='\0';
    permute(chk,n,0);
}

It's a bit rough to change your question to exclude Standard Library functions after someone's answered. Did you study the `std::next_permutation` implementation for ideas? — Tony Delroy, Feb 25 '16 at 04:15
@TonyD sorry man but i am at high school. the only mathematical or logical functions header file i know is math.h. I had never heard of the next_permutation function untill he posted the answer. — Prajwal Samal, Feb 25 '16 at 05:31
wasn't blaming you for not having heard of it beforehand - just meant to ask if you'd had a look after Alex told you about it? Did it give you some good ideas? Do you have questions about it, or other questions about the general problem? There are many other S.O. questions you could look at too - e.g. [here](http://stackoverflow.com/questions/7537791/understanding-recursion-to-generate-permutations), and [here](http://stackoverflow.com/questions/6716847/converting-recursive-permutation-generator-to-iterative). — Tony Delroy, Feb 25 '16 at 06:21
@TonyD thanks for the links. both the codes are so short! i feel like a noob now.. — Prajwal Samal, Feb 26 '16 at 00:04

score 3 · Answer 1 · answered Feb 25 '16 at 02:33

You can look at std::next_permutation:

// next_permutation example
#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort

int main() {
    int myints[] = { 1,2,3 };

    std::sort(myints, myints + 3);

    std::cout << "The 3! possible permutations with 3 elements:\n";
    do {
        std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
    } while (std::next_permutation(myints, myints + 3));

    std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';

    return 0;
}

You may also want to browse this article: C++ Algorithms: next_permutation().

D. Alex · Answer 2 · 2016-02-25T13:12:11.150

It is a variant of permutation without any specifically designed library functions (except std::swap but this can be easily substituted by code)


#include <iostream>
#include <vector>
#include <list>
#include <iterator>

void permute(std::vector<int> a, int i, int n)
{
    int j;
    if (i == n) {
       std::copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
       std::cout<<'\n';
    }
    else
    {
        for (j = i; j <= n; j++)
        {
            std::swap(a[i], a[j]);
            permute(a, i+1, n);
            std::swap(a[i], a[j]);
        }
    }
}

int main()
{
    std::vector<int> v = { 5,7,3,8 };
    permute(v, 0, v.size() -1 );

    return 1;
}

also possible to use prev_permutation

I have written a C++ program to print permutations of letters of a word. I want to know are there other simpler ways to do it?

2 Answers2