Combinatorial Problems – Examples

Page 4 of 5 · Algorithm examples
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:

Vn,k = n! / (n - k)!  (without repetition)
Vn,k = n^k            (with repetition)
  

Permutations

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

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.

Example:

Input
2
3

Output
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
2 2 2

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

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

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


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

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
-
            

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

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.

Example:

Input
5 3

Output
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 2 2
1 2 3
… (the other combinations, 35 in total)
5 5 5

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

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

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 -.

Example 1:
Input:
racecar
Output:
acrerca
arcecra
carerac
craearc
racecar
rcaeacr

Example 2:
Input:
abcdecda
Output:
-

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


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