CODEWITHSUNDEEP
c++
Qasim
Qasim

Reputation: 21

Permutations of characters in an array

I input a character array and want to get all possible combinations of that array as output. For example, if I input character array = 'a,b,c', I want to have output in this form:

a b c,
a c b,
b a c,
b c a,
c a b,
c b a

and similarly if I input 4 characters I want to get 24 combinations out of it. I have made a code for this but it returns combinations only 2 times the amount of input characters. That is, the code return 6 combinations if I input 3 characters (that's right), but if I input 4 characters it returns only 8 possible combinations rather than 24 combinations. My code is as follows:

#include <iostream>
#include<string.h>
#include<stdio.h>
using std::cout;
void getCombination(char *);

int main()
{
    const int maxStringSize = 26;
    char thisString[maxStringSize];
    cout<<"Enter String = ";
    gets (thisString);
    getCombination(thisString);
    return 0;
}

void getCombination(char *thisString)
{
    int stringSize=strlen(thisString);
    for(int i = 0; i<stringSize; i++)
    {
        for(int j = 0; j<stringSize; j++)
        {
            cout<<thisString[(i+j)%stringSize];
        }
        cout<<"\n";
        for(int k = stringSize-1; k>=0; k--)
        {
            cout<<thisString[(i+k)%stringSize];
        }
    cout<<"\n";
    }
}

Upvotes: 2

Views: 3585

Answers (5)

Node
Node

Reputation: 3509

You can do it using std::next_permutation in the algorithm part of the standard library. See the code snippet below for an example. Note that I sort theString first, as this is required by next_permutation to find all combinations.

#include <iostream>
#include <algorithm>

int main()
{
    std::string theString = "abc";

    std::sort(theString.begin(), theString.end()); 

    do
    {
        std::cout << theString << std::endl;
    }
    while (std::next_permutation(theString.begin(), theString.end()));

    return 0;
}

Upvotes: 1

Amm Sokun
Amm Sokun

Reputation: 1298

I guess it could be done this way:

void swap( char &a, char &b) {
char c=a;
a = b;
b = c;
}


void get_Combination( string word, int d ) {
if (d == word.size()) {
    cout<<word<<endl;
    return;
}

for (int i=d; i< word.size(); ++i) {
    swap(word[i],word[d]);
    get_combination( word, d+1 );
    swap(word[i],word[d]);
}
}

Explanation: U start by calling get_combination( word, 0). Now to find all the permutations of the string, each character at every position should appear at the first location in one or other permutation. Thus we start with d=0 and swap every character until the end of the string with the character at d. With the first character in place we repeat the process starting with the second character by calling get_combination(word,d+1). Also note the second swap which is needed to bring back the initially swapped characters to their original locations and then swapping the next character with the character at location d.

Example:

Given the string abc, here is the recursion tree, gc=get_combination 

gc("abc",0)

   gc(abc,1)

      gc(abc,2)

        cout<<"abc"

      gc(acb,2)

        cout<<"acb"

   gc(bac,1)

      gc(bac,2)

        cout<<"bac"

      gc(bca,2)

        cout<<"bca"

  gc(cba,1)

      gc(cba,2)

        cout<<"cba"

      gc(cab,2)

        cout<<"cab"

Upvotes: 0

Priyank Bhatnagar
Priyank Bhatnagar

Reputation: 814

Why your code fails?

Your code produces 2 times permutations because that's what you are doing. You are choosing a prefix and then printing the string in order and in reverse order, that is, two outputs for every prefix. Total number = n*2. (this way how can you possibly print all permutations?)

Solution!

What you need is std::next_permutation. Remember to sort the array before passing it in next_permutation, it produces the permutations in increasing order, which is specifically what you need(according to your example).

You can read about the recursive implementation which produces correct output and how next_permutation is implemented in C++ here.

Upvotes: 2

Joel Falcou
Joel Falcou

Reputation: 6357

http://www.sgi.com/tech/stl/next_permutation.html

std::next_permutation should help you going

Upvotes: 2

trutheality
trutheality

Reputation: 23455

Comment about terminology: these are called permutations not combinations.

That's because you're only looking at permutations that are formed by:

  • picking the first letter and
  • putting the rest in order or,
  • putting the rest in reverse order

Particularly, you can never form acbd from abcd this way.

I recommend trying a recursive solution instead as a first pass (picking the first letter and then looking at all permutations of the rest).

Then from the recursive solution you can make a solution that uses a data structure like a stack if you're worried about stack overflows caused by too many recursion calls.

Upvotes: 1

Related Questions