Before you start: read the lesson Recursive algorithms. How to practise: first try to solve the task on your own (at least on paper), then open the hint, and the solution only at the end. The solutions are mostly in C or C++; if you are learning Java or Python, rewrite the idea in your language.
Combinatorics – Example Tasks
This page contains various example tasks from combinatorics. The first four tasks are repeated from the
page about recursive algorithms
because of their connection with this topic.
Introduction to combinatorics
Combinatorics is a branch of mathematics that studies the ways in which elements can be arranged or combined.
The key concepts include:
Variations
Variations are arrangements of k elements out of n elements in total, where the order of the elements matters.
We distinguish variations with and without repetition:
Permutations are a special case of variations when all n elements are taken:
Pn = n!
If some elements in the sequence are not different, this formula is used:
Pn = n! / (k1! * k2! * ... * kr!)
Combinations
Combinations are choices of k elements out of n elements, where the order does not matter:
Cn,k = n! / (k! * (n - k)!)
If repetition of elements is allowed, this formula is used:
C'n,k = (n + k - 1)! / (k! * (n - 1)!)
1. The next variation
Note: a task from the collection cpp2 – a methodical collection of algorithm tasks on
petlja.org (in Serbian)
Write a program that determines the next variation of length k of the set
{1, ..., n} in lexicographic order.
Input:
The first line contains the number k (1 ≤ k ≤ 100), the second the number
n (1 ≤ n ≤ 100). The third line contains the variation
described by numbers separated by single spaces.
Output:
Print the next variation in lexicographic order or, if the given variation
is the lexicographically largest one, print -.
Example:
Input
5
4
1 1 2 3 4
Output
1 1 2 4 1
Hint — how to think
A variation can be viewed as a number written in "base" n, except that
instead of the digits 0, 1, 2, ... we use the values from 1 to
n.
As with an ordinary number, we get the next variation by:
starting from the right end,
trying to increase the last element,
if it is already equal to n, setting it back to 1 and "carrying"
further to the left.
This is exactly the same as adding one when you go past the largest digit.
The key idea
We look at the variation from right to left.
If some element equals n, it cannot grow any more, so we
change it to 1.
When we find the first element that is not n, we increase it by 1 and that
gives the next variation.
All the elements to the right of that place have already been set to 1, because
that is the smallest possible value.
An example run
1 1 2 3 4
^
the last element is 4 = n, so it rolls over to 1
1 1 2 3 1
^
this element is 3 < n, so it is simply increased to 4
1 1 2 4 1
This way we get the next variation in lexicographic order.
When is there no next variation?
If all the elements equal n, the variation is already the last one.
For example:
4 4 4 4 4
In that case we print -.
Complexity
In the worst case we go through the whole variation once:
O(k)
The memory is:
O(k)
⚠ Before you look at the solution, try on your own!
#include <iostream>
#include <vector>
using namespace std;
// ------------------------------------------------------------
// The function determines the next variation in lexicographic order.
// The variation is written with the numbers from 1 to n.
//
// The idea:
// - we start from the right end
// - if an element equals n, we set it back to 1 and move left
// - when we find an element that is not n, we increase it by 1
// - if all the elements were n, there is no next variation
// ------------------------------------------------------------
bool nextVariation(vector<int>& variation, int n) {
int k = (int)variation.size();
int pos = k - 1;
// As long as the current element is the largest one, we set it to 1
// and move to the left.
while (pos >= 0 && variation[pos] == n) {
variation[pos] = 1;
pos--;
}
// If we have gone through the whole variation, it is already the last one.
if (pos < 0) return false;
// We increase by 1 the first element that was not n.
variation[pos]++;
return true;
}
int main() {
int k, n;
cin >> k >> n;
vector<int> variation(k);
// We read a variation of length k.
for (int i = 0; i < k; i++) {
cin >> variation[i];
}
if (nextVariation(variation, n)) {
// We print the new variation.
for (int x : variation) {
cout << x << ' ';
}
cout << '\n';
} else {
// If the next variation does not exist.
cout << "-\n";
}
return 0;
}
Final explanation
This task is a variant of "counting upwards" in a system where the allowed values are
from 1 to n.
The most important thing is to look at the right end as the least significant digits:
if it can be increased, we increase it;
if it cannot, we set it back to 1 and move to the next position on the left;
when we find a position that can be increased, we stop there.
That is why the solution is simple, fast and works in linear time.
2. All variations
Note: a task from the collection cpp2 – a methodical collection of algorithm tasks on
petlja.org (in Serbian)
Write a program that determines all the variations with repetition of length
k of the set {1, ..., n}.
Input:
The number n (1 ≤ n ≤ 5) is read from the standard input,
and in the next line the number k (1 ≤ k ≤ 5).
Output:
Print all the variations, sorted lexicographically.
We need to print all the possible variations of length
k made of the numbers
1, 2, ..., n.
Since repetition is allowed, at every position we can put
any number from 1 to n.
The key idea
We build the variation gradually, one position at a time.
For every new position we have:
n possible choices,
every choice leads to new variations.
That is why it is natural to use recursion.
How does the recursion work?
Suppose that:
n = 2
k = 3
First we choose the first element:
1
2
If we have chosen:
1
then for the next position we can again choose:
1 1
1 2
Then we continue in the same way until we form
a variation of length k.
When do we print the result?
When the current variation reaches the length:
k
then we have formed one complete variation and we can print it.
Why is the order lexicographic?
We add the numbers in order:
1, 2, ..., n
at every position.
Because of that, the variations are generated exactly in the order in which they
would appear in lexicographic order.
The number of variations
At each of the k positions we have n choices.
The total number of variations is:
n^k
That is why the algorithm has to go through all n^k possibilities.
⚠ Before you look at the solution, try on your own!
#include <iostream>
#include <vector>
using namespace std;
// ------------------------------------------------------------
// We generate all the variations with repetition recursively.
//
// variation
// the variation formed so far.
//
// When its length becomes k,
// we print it.
// ------------------------------------------------------------
void generateVariations(
int n,
int k,
vector<int>& variation
) {
// --------------------------------------------------------
// A complete variation has been formed.
// --------------------------------------------------------
if ((int)variation.size() == k) {
for (int number : variation) {
cout << number << ' ';
}
cout << '\n';
return;
}
// --------------------------------------------------------
// At the next position we can put
// any number from 1 to n.
// --------------------------------------------------------
for (int i = 1; i <= n; i++) {
// we add the number
variation.push_back(i);
// we fill the rest of the variation
generateVariations(n, k, variation);
// we restore the state before the next attempt
variation.pop_back();
}
}
int main() {
int n, k;
cin >> n >> k;
vector<int> variation;
generateVariations(n, k, variation);
return 0;
}
Final explanation
This is one of the simplest examples of recursive generation.
Instead of knowing the whole variation in advance, we build it step by step:
we choose a number for the next position,
we fill the rest recursively,
we go back and try the next choice.
Backtracking
The instruction:
variation.pop_back();
takes us back to the previous state.
This way of searching is called
backtracking.
After we have processed all the possibilities that start with one choice,
we go one step back and try the next one.
The key lesson
When we need to generate:
all the variations,
all the combinations,
all the subsets,
all the words of a given length,
very often the most natural solution is exactly recursion and backtracking.
3. All the words from given letters
A string s gives a set of lowercase letters of the English alphabet, and a
natural number k is given.
Write a program that prints all the words of length
k in lexicographic order.
Input:
The first line contains the string s of length at most 10,
and the second line the number k
(k ≤ 6, k ≤ n).
Output:
Print all the required words in lexicographic order,
each in a separate line.
Example:
Input
amx
2
Output
aa
am
ax
ma
mm
mx
xa
xm
xx
Hint — how to think
We need to generate all the possible words of length
k.
At every position we can choose any letter from the string
s.
Since repetition of letters is allowed,
every position has the same set of possible choices.
The key idea
We build the word letter by letter.
For every new position:
we choose one letter from the string,
we add it to the end of the current word,
we fill the rest recursively.
An example
Let:
s = "amx"
k = 2
For the first letter we can choose:
a
m
x
If we choose:
a
for the second letter we again have:
aa
am
ax
All the other words are formed in the same way.
Why is the order lexicographic?
We go through the letters in the order in which they appear in the string
s (in the example they are already sorted).
That is why the recursion naturally generates the words in lexicographic order.
The number of words
If the string contains n letters,
and the word has the length k,
the total number of possible words is:
n^k
⚠ Before you look at the solution, try on your own!
#include <iostream>
#include <string>
using namespace std;
// ------------------------------------------------------------
// We generate all the words of length k recursively.
//
// currentWord
// is the part of the word formed so far.
// ------------------------------------------------------------
void generateWords(
const string& letters,
int k,
string currentWord
) {
// --------------------------------------------------------
// A complete word has been formed.
// --------------------------------------------------------
if ((int)currentWord.size() == k) {
cout << currentWord << '\n';
return;
}
// --------------------------------------------------------
// At the next position we can put
// any letter from the string.
// --------------------------------------------------------
for (char letter : letters) {
generateWords(
letters,
k,
currentWord + letter
);
}
}
int main() {
string s;
int k;
cin >> s;
cin >> k;
generateWords(s, k, "");
return 0;
}
Final explanation
This task is exactly the same type of problem as generating
all the variations with repetition.
The only difference is that we use letters instead of numbers.
numbers → the elements of the variation
letters → the characters of the word
The recursion builds the word character by character,
and when we reach the length k,
the word is ready to be printed.
The key lesson
A large number of generation tasks can be reduced to:
choose one element,
solve a smaller problem recursively,
repeat for all the possible choices.
That is the basic idea of recursive search and backtracking.
4. All subsets
Write a program that prints all the subsets of a given set.
Input:
The number
n
(3 ≤ n ≤ 10)
is read from the standard input,
followed by n natural numbers
sorted in ascending order.
Output:
Print all the subsets of the set,
each in a separate line,
with the elements separated by a single space.
Example:
Input
3
1 2 3
Output
3
2
2 3
1
1 3
1 2
1 2 3
Hint — how to think
For every element of the set there are only two possibilities:
the element belongs to the subset,
the element does not belong to the subset.
That is why for every element we make one of two decisions.
The key idea
Let us look at the element at the current position.
The recursion makes two branches:
we do not take the element,
we take the element.
Then we process the next element in the same way.
An example
Let the set be:
1 2 3
For the element 1 there are two possibilities:
do not take 1
take 1
For each of these possibilities we decide again for the element
2, and then for the element 3.
This is how the whole tree of all the subsets is formed.
The decision tree
{}
/ \
no yes
1 1
/ \ / \
... ...
Every path from the root to a leaf represents one subset.
When do we print a subset?
When we have processed all the elements of the set.
Then the sequence of decisions is complete and we know exactly which elements
belong to the subset.
How many subsets are there?
For each of the n elements we have two possibilities:
it is taken
it is not taken
The total number of subsets is:
2^n
Since the example does not show the empty set,
we skip it when printing.
⚠ Before you look at the solution, try on your own!
#include <iostream>
#include <vector>
using namespace std;
// ------------------------------------------------------------
// We generate all the subsets recursively.
//
// position
// marks the element we are currently deciding about.
//
// subset
// contains the elements we have chosen so far.
// ------------------------------------------------------------
void generateSubsets(
const vector<int>& set,
int position,
vector<int>& subset
) {
// --------------------------------------------------------
// All the elements have been processed.
// --------------------------------------------------------
if (position == (int)set.size()) {
// The example does not ask for the empty set to be printed.
if (subset.empty())
return;
for (int x : subset)
cout << x << " ";
cout << '\n';
return;
}
// --------------------------------------------------------
// 1) The current element does not go into the subset.
// --------------------------------------------------------
generateSubsets(
set,
position + 1,
subset
);
// --------------------------------------------------------
// 2) The current element goes into the subset.
// --------------------------------------------------------
subset.push_back(
set[position]
);
generateSubsets(
set,
position + 1,
subset
);
// --------------------------------------------------------
// We restore the state before the next branch.
// --------------------------------------------------------
subset.pop_back();
}
int main() {
int n;
cin >> n;
vector<int> set(n);
for (int i = 0; i < n; i++) {
cin >> set[i];
}
vector<int> subset;
generateSubsets(
set,
0,
subset
);
return 0;
}
Final explanation
Unlike the previous two tasks,
here we do not choose one of several elements.
Instead,
for every element we make a decision:
it is taken,
it is not taken.
Backtracking
When we add an element:
subset.push_back(...)
after that branch is finished we must go back
to the previous state:
subset.pop_back()
That is exactly the essence of backtracking.
The key lesson
Many combinatorial problems can be reduced to:
choose the element,
or skip it.
Whenever there are two decisions for every object,
a recursion tree with
2^n leaves very often appears.
5. The next subset
Write a program that determines the subset of the set of numbers
{1, ..., n} that comes immediately after the given subset
in lexicographic order.
The subsets are given in the form of strictly increasing arrays.
Input:
The first line contains the number n
(1 ≤ n ≤ 100), and the next line a subset whose elements are
given sorted in ascending order, separated by single spaces.
Output:
Print the elements of the required subset in one line on the standard output,
or - if the given subset is the lexicographically largest one.
Example:
Input
5
1 2 3 4 5
Output
1 2 3 5
Hint — how to think
We look at the subsets as increasing sequences of numbers.
Lexicographic order means that they are compared in order, element by element,
like words in a dictionary.
That is why it is very important to understand that:
if one subset is a prefix of another, the shorter one is smaller,
if they differ at some position, the smaller one is the one with the smaller number
at that position.
The key idea
We look for the next subset by looking from right to left.
There are three cases:
if the subset is empty, the next one is {1},
if the last element is smaller than n, the subset is extended with the element "last + 1",
if the last element equals n, we remove it and increase the new last element by 1.
An example of the order of subsets
For the set {1,2,3,4} (n = 4) the order begins like this:
In the same way, for n = 5, after the subset 1 2 3 4 5 comes
1 2 3 5.
Why do we remove the suffix?
When we increase some element, all the elements to its right can no longer stay
the same, because the new subset would be "too large".
That is why we choose the shortest possible continuation, which means that we delete all the elements to the right of
the changed position.
How to recognise the end?
If no element can be increased, it means that we have reached the
lexicographically largest subset (that is the subset {n}).
Then we print -.
Complexity
In the worst case we go through the subset once from right to left:
O(k)
where k is the number of elements in the given subset.
⚠ Before you look at the solution, try on your own!
#include <iostream>
#include <vector>
#include <sstream>
#include <string>
#include <limits>
using namespace std;
// ------------------------------------------------------------
// Determines the next subset in lexicographic order.
//
// The subset is represented as a strictly increasing array,
// and the array is changed directly.
// Returns false if there is no next subset.
// ------------------------------------------------------------
bool nextSubset(int n, vector<int>& subset) {
// --------------------------------------------------------
// If the subset is empty, the next one is {1}.
// --------------------------------------------------------
if (subset.empty()) {
subset.push_back(1);
return true;
}
int k = (int)subset.size();
// --------------------------------------------------------
// If we can extend the subset by one more element,
// that is the next subset in lexicographic order.
// --------------------------------------------------------
if (subset.back() < n) {
subset.push_back(subset.back() + 1);
return true;
}
// --------------------------------------------------------
// Otherwise we look for the first element from the right
// that can be increased.
//
// When we increase it, we delete all the elements to its right.
// --------------------------------------------------------
int i = k - 1;
while (i >= 0 && subset[i] == n) {
i--;
}
if (i < 0) {
return false;
}
subset[i]++;
// --------------------------------------------------------
// All the elements to the right of position i are removed.
// --------------------------------------------------------
subset.resize(i + 1);
return true;
}
int main() {
int n;
cin >> n;
cin.ignore(numeric_limits<streamsize>::max(), '\n');
// --------------------------------------------------------
// We read the whole next line.
// If the line is empty, an empty subset has been read.
// --------------------------------------------------------
string line;
getline(cin, line);
vector<int> subset;
stringstream ss(line);
int number;
while (ss >> number) {
subset.push_back(number);
}
if (nextSubset(n, subset)) {
// the result is printed in all the cases
for (int x : subset) {
cout << x << ' ';
}
cout << '\n';
} else {
cout << "-" << '\n';
}
return 0;
}
Final explanation
The most important thing is not to look at the subset as a set, but as
a sequence of elements in increasing order.
Then we get the next subset in the same way as the "next word" in a dictionary:
we start from the right side,
we look for the first element that can grow,
we increase it,
and we delete everything to its right.
If there is no element that can be increased, the subset is already the last one.
The key lesson
With lexicographic order it is often enough to look only at
the first position where a change happens.
Here it is exactly the element that we change from right to left.
6. The next binary sequence without adjacent ones
Let us look at the lexicographically ordered binary sequences of length n that contain zeros and ones, but do not contain two adjacent ones.
For example, such sequences of length 3 are: 000, 001, 010, 100 and 101.
Write a program that determines the next sequence in lexicographic order for a given sequence.
Input:
A binary sequence of length n (1 ≤ n ≤ 50) without consecutive ones is read from the standard input.
All the elements are written one after another, without spaces.
Output:
The only line of the standard output should contain the elements of the next sequence in lexicographic order
(printed one after another, without spaces) or the text does not exist if the given sequence is the lexicographically largest one.
Example 1
Input
10101000100001010
Output
10101000100010000
Example 2
Input
10101010
Output
does not exist
The next sequence is obtained as when counting in binary, but we must not get two adjacent ones:
Look for the rightmost position i with a zero that can be changed into a one – the zero to its left must also be a zero (or i is the first position).
Write a one at position i, and set all the positions to its right to zero – that is the smallest possible continuation (and the one at i now has a zero on its right).
If there is no such position, the sequence is the largest one (1010…) and we print does not exist.
The complexity is O(n). Simply "adding one" until a valid sequence appears is not a good idea: for n = 50 it could take billions of steps.
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
cin >> s;
int n = s.size();
// the rightmost zero that can become a one (there is no one to its left)
for (int i = n - 1; i >= 0; i--) {
if (s[i] == '0' && (i == 0 || s[i - 1] == '0')) {
s[i] = '1';
for (int j = i + 1; j < n; j++) s[j] = '0'; // the smallest continuation
cout << s << endl;
return 0;
}
}
cout << "does not exist" << endl;
return 0;
}
7. Numbers whose binary notation has no two adjacent zeros
Write a program that prints the decimal notation of all the natural numbers that in the binary system have
at most n binary digits and do not have two consecutive zeros.
Input:
The first line of the standard input contains a natural number n (1 ≤ n ≤ 20).
Output:
Print the required numbers on the standard output in ascending order, each number in a separate line.
Example
Input
3
Output
1
2
3
5
6
7
8. The next combination
Note: a task from the collection cpp2 – a methodical collection of algorithm tasks on petlja.org (in Serbian)
Write a program that determines the next combination of length k of the set {1, ..., n} in lexicographic order.
Input:
The first line contains the number k (1 ≤ k ≤ 100), the second the number n (1 ≤ n ≤ 100). The third line contains the combination described by numbers separated by single spaces.
Output:
Print the next combination in lexicographic order or, if the given combination is the lexicographically largest one, print "-".
Example 1:
Input
4
5
1 2 3 4
Output
1 2 3 5
Example 2
Input
3
5
1 3 4
Output
1 3 5
Example 3
Input
3
5
1 3 5
Output
1 4 5
Example 4
Input
3
5
3 4 5
Output
-
A combination is written as an increasing sequence. At position i (counting from 0) the largest possible value is n − (k − 1 − i), because after it there must still be room for k − 1 − i larger numbers.
Look from the right for the first position i whose element is smaller than its largest possible value. If there is none, print -.
Increase that element by 1.
Fill the positions to its right with consecutive numbers: c[j] = c[j − 1] + 1 – that is the smallest possible continuation.
For example, for 1 3 5 (n = 5): the last element 5 is already the largest, the middle one 3 can be at most 4 – it becomes 4, and after it comes 5: 1 4 5.
#include <iostream>
#include <vector>
using namespace std;
bool nextCombination(vector<int>& combination, int n) {
int k = combination.size();
int pos = k - 1;
// the first position from the right that has not reached its largest value
while (pos >= 0 && combination[pos] == n - (k - 1 - pos)) {
pos--;
}
if (pos < 0) return false; // the last combination
combination[pos]++;
for (int j = pos + 1; j < k; j++) // the smallest continuation
combination[j] = combination[j - 1] + 1;
return true;
}
int main() {
int k, n;
cin >> k >> n;
vector<int> combination(k);
for (int i = 0; i < k; i++) {
cin >> combination[i];
}
if (nextCombination(combination, n)) {
for (int x : combination)
cout << x << " ";
cout << endl;
} else {
cout << "-" << endl;
}
return 0;
}
9. The next variation without repetition
Note: a task from the collection cpp2 – a methodical collection of algorithm tasks on petlja.org (in Serbian)
Write a program that determines the next variation without repetition of length k of the set {1, …, n} in lexicographic order.
Input:
The first line of the standard input contains the number k (1 ≤ k ≤ 100), the second the number n (1 ≤ n ≤ 100). The third line contains the variation described by numbers separated by single spaces.
Output:
Print the next variation in lexicographic order, if it exists, or print - if the given variation is the lexicographically largest one.
Example:
Input
4
5
1 3 2 4
Output
1 3 2 5
Keep an array used that marks which values are already in the variation.
Go from the right end. At every position release the value (used = false) and check whether there is a free value larger than the current one. The first position where such a value exists is the one that changes.
Put at that position the smallest free value larger than the current one.
Fill the positions to its right with the smallest free values in ascending order – that is the smallest possible continuation.
If no position can be changed, print -.
#include <iostream>
#include <vector>
using namespace std;
// the smallest free value larger than x, or -1 if there is none
int smallestFreeAbove(int x, int n, const vector<bool>& used) {
for (int v = x + 1; v <= n; v++)
if (!used[v]) return v;
return -1;
}
bool nextVariation(vector<int>& variation, vector<bool>& used, int n) {
int k = variation.size();
for (int pos = k - 1; pos >= 0; pos--) {
used[variation[pos]] = false; // we release the value at this position
int v = smallestFreeAbove(variation[pos], n, used);
if (v != -1) {
variation[pos] = v; // the smallest larger free value
used[v] = true;
int next = 1;
for (int i = pos + 1; i < k; i++) { // the smallest free values in ascending order
while (used[next]) next++;
variation[i] = next;
used[next] = true;
}
return true;
}
}
return false; // there is no position to change
}
int main() {
int k, n;
cin >> k >> n;
vector<int> variation(k);
vector<bool> used(n + 1, false);
for (int i = 0; i < k; i++) {
cin >> variation[i];
used[variation[i]] = true; // mark that this number is taken
}
if (nextVariation(variation, used, n)) {
for (int c : variation) cout << c << " ";
cout << endl;
} else {
cout << "-" << endl;
}
return 0;
}
10. All combinations with repetition
Write a program that generates and prints all the combinations with repetition of length K of the elements of the set {1, 2, …, N} in lexicographic order. In a combination with repetition the elements are written in non-decreasing order.
Input:
The first line contains two numbers: N (the largest value of an element) and K (the length of the combination).
Output:
Print all the combinations with repetition on the standard output, each in a separate line.
Write a program that generates all the combinations with repetition of length K of the set {1, …, N} in lexicographic order. The steps of the solution:
Define a function process that prints the current combination.
Implement a recursive function generateCombinations that fills the combination array at the positions from 0 to K-1. For the first element use the value 1, and for the others the value of the previous element – this allows repetition.
When all K elements are filled, the function process is called to print the combination.
Call the function allCombinations, which starts generating the combinations.
The number of combinations with repetition is C'(N, K) = (N + K − 1)! / (K! · (N − 1)!); for N = 5, K = 3 that is 35.
#include <iostream>
#include <vector>
using namespace std;
/* A function that prints the current combination */
void process(const vector<int>& combination) {
for (int v : combination) {
cout << v << " ";
}
cout << "\n";
}
/* A recursive function that generates the combinations with repetition */
void generateCombinations(vector<int>& combination, int pos, int N, int K) {
if (pos == K) { // if all the positions are filled, the combination is printed
process(combination);
return;
}
// We start from the value 1 for the first element or from the previous element for the others
int start = (pos == 0) ? 1 : combination[pos - 1];
for (int i = start; i <= N; i++) {
combination[pos] = i;
generateCombinations(combination, pos + 1, N, K);
}
}
/* A function that starts generating all the combinations */
void allCombinations(int N, int K) {
vector<int> combination(K, 1);
generateCombinations(combination, 0, N, K);
}
int main() {
int N, K;
cin >> N >> K;
allCombinations(N, K);
return 0;
}
11. The next permutation
All the permutations of the numbers from 1 to n can be ordered lexicographically. For a given n and a given sequence
of n numbers (a permutation), determine the next permutation in that order. If the given sequence is the last
permutation, print does not exist.
Input:
The first line contains the number n (n < 1000). In the next n lines there is one element of the permutation in each.
Output:
Print the elements of the next permutation, each in a separate line, or the message does not exist in one line.
Example:
Input
5
3
1
4
5
2
Output
3
1
5
2
4
The algorithm for "the next permutation" in lexicographic order:
Find the largest index i such that a[i] < a[i+1]. If there is none, this is the last permutation.
Find the largest index j > i such that a[j] > a[i].
By swapping a[i] and a[j] you move the permutation to the next block.
Reverse the segment a[i+1..n-1] to get the smallest possible permutation in the continuation.
Example input: 5 3 1 4 5 2
Example output: 3 1 5 2 4
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Finding and printing the next permutation
bool nextPermutation(vector<int>& a) {
int n = a.size();
int i = n - 2;
while (i >= 0 && a[i] >= a[i+1]) {
--i;
}
if (i < 0) return false;
int j = n - 1;
while (a[j] <= a[i]) {
--j;
}
swap(a[i], a[j]);
reverse(a.begin() + i + 1, a.end());
for (int x : a) {
cout << x << "\n";
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
if (!nextPermutation(a)) {
cout << "does not exist\n";
}
return 0;
}
12. All permutations
Write a program that generates and prints all the permutations of the set {1, 2, …, n}.
Input:
The number n (1 ≤ n ≤ 8) is read from the standard input.
Output:
Print all the permutations of the set {1, …, n} on the standard output. Print every permutation in a separate line, with the elements separated by a single space. The order of the permutations can be arbitrary (e.g. lexicographic).
Example:
Input
3
Output
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
The steps of the solution:
Make a vector perm of size n and initialise it with 1,2,…,n. Also make an array used of length n+1 and mark all the values that are in perm as taken.
Print the initial permutation.
Call the function nextVariation(perm, used, n), which implements the algorithm for the next lexicographic permutation:
Find the largest index i at which you can increase perm[i], releasing the taken values on the way.
Replace perm[i] with the next larger free number.
Fill the positions to the right of i with the smallest possible free numbers.
Repeat printing the permutation as long as nextVariation returns true.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Checks whether the set contains a free number larger than the current element
bool hasInSet(int element,
int n,
const vector<bool>& usedValues)
{
// Start from the position after the current element and look for a free (false) element
auto it = usedValues.begin() + element + 1;
while ((it = find(it, usedValues.end(), false)) != usedValues.end())
{
int freeElement = distance(usedValues.begin(), it);
// If the free number found is within the set {1, ..., n}
if (freeElement <= n)
return true;
++it;
}
return false;
}
// A function that generates the next lexicographic permutation
bool nextVariation(vector<int>& variation,
vector<bool>& usedValues,
int n)
{
int k = variation.size();
int pos = k - 1;
// We look from right to left for a position that can be increased
while (pos >= 0 &&
!hasInSet(variation[pos], n, usedValues))
{
// We release the currently taken value
usedValues[variation[pos]] = false;
pos--;
}
// If there are no more permutations
if (pos < 0) return false;
// We release this value too so that we can replace it
usedValues[variation[pos]] = false;
// We find the smallest possible free number larger than the current one
auto it = usedValues.begin() + variation[pos] + 1;
while ((it = find(it, usedValues.end(), false)) != usedValues.end())
{
int newValue = distance(usedValues.begin(), it);
if (newValue <= n)
{
variation[pos] = newValue;
usedValues[newValue] = true;
break;
}
++it;
}
// We fill the right part with the smallest free values
for (int i = pos + 1; i < k; i++)
{
auto it2 = find(usedValues.begin() + 1,
usedValues.begin() + n + 1,
false);
if (it2 != usedValues.begin() + n + 1)
{
int freeEl = distance(usedValues.begin(), it2);
variation[i] = freeEl;
usedValues[freeEl] = true;
}
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// We initialise the permutation 1,2,...,n
vector<int> perm(n);
vector<bool> used(n + 1, false);
for (int i = 0; i < n; i++)
{
perm[i] = i + 1;
used[i + 1] = true;
}
// We print all the permutations
do {
for (int x : perm)
cout << x << " ";
cout << "\n";
} while (nextVariation(perm, used, n));
return 0;
}
13. All the palindromes from a given word
A word r written in lowercase letters of the English alphabet is given. Write a program that prints in lexicographic
order all the palindromes that can be obtained by rearranging the letters of the given word.
Input:
The first and only line of the standard input contains the word r with at most 20 lowercase letters of the English alphabet.
Output:
Print the required palindromes on the standard output. If no palindrome can be formed, print a dash -.
A palindrome is a string that reads the same from left to right and from right to left.
A word can form a palindrome if at most one letter appears an odd number of times.
We make half of the palindrome (we take every letter count / 2 times) and generate all the distinct permutations of that half.
To every permutation we add the middle character (if there is one) and the reversed half – this forms the whole palindrome.
We print all the palindromes obtained in lexicographic order.
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
using namespace std;
int main() {
string word;
cin >> word;
int length = word.size();
map<char,int> letterCount;
for (char c : word) {
letterCount[c]++;
}
int oddCount = 0;
char middleChar = 0;
for (auto &p : letterCount) {
if (p.second % 2 != 0) {
oddCount++;
middleChar = p.first;
}
}
if (oddCount > 1) {
cout << "-\n";
return 0;
}
string half;
half.reserve(length / 2);
for (auto &p : letterCount) {
half += string(p.second / 2, p.first);
}
sort(half.begin(), half.end());
bool found = false;
do {
string palindrome = half;
if (middleChar) {
palindrome.push_back(middleChar);
}
palindrome += string(half.rbegin(), half.rend());
cout << palindrome << "\n";
found = true;
} while (next_permutation(half.begin(), half.end()));
if (!found) {
cout << "-\n";
}
return 0;
}
Introduction to the partitions of the number n
A partition of a natural number n is a way to express it as a sum of positive integers:
n = a1 + a2 + … + ak, where the terms are
a1 ≥ a2 ≥ … ≥ ak ≥ 1.
The order of the terms does not matter – we always write them in non-increasing order.
Why partitions?
Partitions appear in combinatorics, number theory, and even in physics and cryptography,
when we want to explore all the possible ways of dividing some quantity into parts.
An example for n = 5:
5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
In the task "All partitions" we have to generate and print exactly such a complete
list, sorting the partitions lexicographically in non-increasing (normalised) form.
14. The next partition
The partitions of the number n are decompositions of that number into terms whose value is between 1 and n.
For example, the number 10 can be partitioned as 5+2+2+1. Every partition is normalised so that the terms are
sorted in non-increasing order. Write a program that determines the next partition in lexicographic order for a given partition.
Input:
A normalised partition is entered from the standard input, with the terms separated by the sign + (their sum < 1000).
Output:
Print the next normalised partition in lexicographic order (the terms separated by +),
or the word no if such a partition does not exist.
Example:
Input
5+2+2+1
Output
5+3+1+1
The steps of the solution:
Parsing the input: Read the whole line and turn the terms separated by + into a vector part.
Looking for the next partition: For i from the end towards the beginning:
Calculate prefixSum = the sum of the terms before i.
Determine maxVal = (if i==0 then N, otherwise part[i-1]).
Try newVal from part[i]+1 to maxVal and calculate rem = N - prefixSum - newVal.
If rem ≥ 0, form the new partition:
part[0..i-1], newVal, 1,1,…,1 (rem times) and print it.
The end: If no position i worked, print no.
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 1) Parsing the input
string line;
if (!getline(cin, line)) return 0;
vector<int> part;
{
int number = 0;
for (char c : line) {
if (c == '+') {
part.push_back(number);
number = 0;
} else if (c >= '0' && c <= '9') {
number = number * 10 + (c - '0');
}
}
part.push_back(number);
}
int k = part.size();
int N = accumulate(part.begin(), part.end(), 0);
// 2) Looking for the next partition
for (int i = k - 1; i >= 0; --i) {
int prefixSum = 0;
for (int j = 0; j < i; ++j) prefixSum += part[j];
int maxVal = (i == 0 ? N : part[i-1]);
for (int newVal = part[i] + 1; newVal <= maxVal; ++newVal) {
int rem = N - prefixSum - newVal;
if (rem < 0) break;
vector<int> next;
next.reserve(i + 1 + rem);
for (int j = 0; j < i; ++j) next.push_back(part[j]);
next.push_back(newVal);
for (int t = 0; t < rem; ++t) next.push_back(1);
for (int idx = 0; idx < (int)next.size(); ++idx) {
if (idx) cout << '+';
cout << next[idx];
}
cout << "\n";
return 0;
}
}
// 3) If there is no next partition
cout << "no\n";
return 0;
}
15. All partitions
The partitions of the number n are decompositions of that number into terms whose value is between 1 and n.
We normalise every partition so that the terms are sorted in non-increasing order, and we print them in ascending lexicographic order.
Write a program that prints all the normalised partitions of the number n for a given number n (1 ≤ n ≤ 25).
Input:
One integer n.
Output:
All the normalised partitions of the number n, one per line, with the terms separated by a space.
Example:
Input
5
Output
1 1 1 1 1
2 1 1 1
2 2 1
3 1 1
3 2
4 1
5
The steps of the solution:
Representing a partition: We keep the current partition in the vector currentPartition.
Recursion (buildPartitions):
The argument remaining tells how much we still have to cover.
The argument maxTerm is the largest allowed next term, so that the partition is non-increasing.
If remaining == 0, we print currentPartition.
Otherwise, for every p from 1 to min(maxTerm, remaining):
We add p to the partition, make a recursive call with remaining - p and p, and then remove p.
The main program: It reads the number n and calls buildPartitions(n, n).
#include <iostream>
#include <vector>
using namespace std;
// keeps the current partition
vector<int> currentPartition;
// remaining = how much we still have to cover,
// maxTerm = the largest allowed next term
void buildPartitions(int remaining, int maxTerm) {
if (remaining == 0) {
// print the finished partition
for (int i = 0; i < (int)currentPartition.size(); i++) {
if (i) cout << ' ';
cout << currentPartition[i];
}
cout << "\n";
return;
}
// we choose a term from 1 to min(maxTerm, remaining)
for (int p = 1; p <= maxTerm && p <= remaining; ++p) {
currentPartition.push_back(p);
// the next term must be ≤ p for the partition to be non-increasing
buildPartitions(remaining - p, p);
currentPartition.pop_back();
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int number;
cin >> number;
buildPartitions(number, number);
return 0;
}
Podešavanja kolačića
Koristimo kolačiće da bismo vam pružili najbolje moguće iskustvo. Takođe nam omogućavaju da analiziramo ponašanje korisnika kako bismo stalno poboljšavali veb lokaciju za vas.