CODEWITHSUNDEEP
c++permutation
Mohit Negi
Mohit Negi

Reputation: 52

Why this snippet of code isn't generating all the permutations?

For input string "bba", it's not generating all the integer permutations. The integers that will be stored in the array are: 2, 1, 1

The output is 2 1 1.

I want the output to be:

1 1 2

1 2 1

2 1 1

#include <bits/stdc++.h>

int main() {
    std::string s;
    std::cout << "Enter a string: ";
    std::cin >> s;
    int ss = s.size();
    int ar[ss];
    for(int i=0; i<ss; i++) {
        int tmp = int(s[i])-96;
        ar[i] = tmp;
    }  

    do {
        for(auto i: ar) std::cout << i;
        std::cout << '\n';
    } while(std::next_permutation(ar, ar+ss));

    return 0;
}

Upvotes: 1

Views: 112

Answers (2)

AMA
AMA

Reputation: 4214

The reason you are getting only one permutation is because there's no permutation lexicographically greater that the current state of array: [2, 2, 1]. See the documentation of std::permutation:

Transforms the range [first, last) into the next permutation from the set of all permutations that are lexicographically ordered with respect to operator< or comp. Returns true if such permutation exists, otherwise transforms the range into the first permutation (as if by std::sort(first, last)) and returns false.

Consider using std::vector instead of C-array and sorting it before calculating all the permutations:

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::string s = "bba";
    const int ss = s.size();
    std::vector<int> ar;
    ar.reserve(ss);
    constexpr int offset = 'a' - 1;
    for(int i=0; i<ss; i++) {
        int tmp = int(s[i]) - offset;
        ar.push_back(tmp);
    }  
    std::sort(ar.begin(), ar.end());
    do {
        for(auto i: ar) std::cout << i;
        std::cout << '\n';
    } while(std::next_permutation(ar.begin(), ar.end()));

    return 0;
}

This outputs:

122
212
221

Live example

Update: as it was pointed out by @Someprogrammerdude, please see: Why should I not #include <bits/stdc++.h>

Update 2: as it was pointed out by @Jarod42 consider using 'a' - 1 instead of magic-constant 96.

Upvotes: 4

Hades
Hades

Reputation: 119

Making an array of Integers before generating permutations seems unnecessary. You are missing a point where you sort your values.

Try this approach instead:

std::sort(s.begin(), s.end());
do {
    for(int i = 0; i < s.size(); i++){
        std::cout << int(s[i]) - 96 << " ";
    }
    std::cout << '\n';
} while(std::next_permutation(s.begin(), s.end()));

The output is

1 2 2                                                                                                                                                                                       
2 1 2                                                                                                                                                                                       
2 2 1

Upvotes: 2

Related Questions