Athlete Rankings
Autumn Tournament (2013)
Submission name: sport.cpp
Problem summary
Each athlete has a distinct lowercase letter. Print all possible rankings of the athletes in lexicographic order.
Input
A string of distinct lowercase Latin letters.
Output
Every permutation, one per line, in increasing lexicographic order.
Constraints
3 ≤ number of athletes ≤ 7.
Worked example
Original statement sample.
Input
acd
Output
acd adc cad cda dac dca
Solution analysis
- A ranking is a permutation: each athlete appears exactly once. Sort the letters first, so the initial string is the lexicographically smallest ranking.
- C++ next_permutation replaces the current arrangement with its immediate lexicographic successor. Use a do-while loop so the initial sorted arrangement is printed too. Stop when no successor exists.
- For acd, the successors are adc, cad, cda, dac, and dca. There are 3!=6 rankings. The input itself need not be sorted: dca must still produce exactly this ordered list.
Why it works
Sorting gives the smallest permutation. Each successful next_permutation advances to the next larger permutation without skipping any. Consequently the loop prints every ranking exactly once and in the required order.
Watch out. Start from a sorted string or earlier rankings are missed. Print the first arrangement before requesting its successor. Letters are distinct under the stated constraints.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Sorting gives the smallest permutation. Each successful next_permutation advances to the
// next larger permutation without skipping any.
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
int main(){
string ranking;
cin>>ranking;
sort(ranking.begin(),ranking.end());
do{
cout<<ranking<<'\n';
}
while(next_permutation(ranking.begin(),ranking.end()));
}