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

Question

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;
}

Technically your program isn't valid, since C++ doesn't have [variable-length arrays](https://en.wikipedia.org/wiki/Variable-length_array). And why don't you simply permutate `s` directly? — Some programmer dude, Feb 05 '18 at 09:16
As for your problem, if you read between the lines of e.g. [this `std::next_permutation`](http://en.cppreference.com/w/cpp/algorithm/next_permutation) (as well as see the example) you should know that the container you permutate needs to be *sorted*. — Some programmer dude, Feb 05 '18 at 09:22
Lastly, I suggest you read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — Some programmer dude, Feb 05 '18 at 09:27

AMA · Accepted Answer · 2018-02-05T09:43:41.633

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.

Hades · Answer 2 · 2018-02-05T09:36:07.590

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

Yes, i was missing sorting. – Mohit Negi Feb 05 '18 at 09:34 — Mohit Negi, Feb 05 '18 at 09:34

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

2 Answers2