Search for the next permutation. Combinatorial formulas

First of all, let us examine the basic concepts of combinatorics - selections and their types: permutations, placement and combinations. It is necessary to know them in order to solve a large part of the USE 2020 in mathematics of both levels, as well as for ninth-graders to pass the OGE. Let's start with an example.

Permutations. Counting the number of permutations.

Imagine that you have chosen a profession that, it would seem, is in no way related to mathematics, for example, an interior designer. Imagine that the customer made a request to you:

"Arrange 4 books on the shelf so that the burgundy and blue volumes are not side by side. Show me all placement options. I will choose the preferred one. "

What are you going to do? Most likely, you will start arranging and showing. However, in order not to get confused, not to miss any of the possible options and not to repeat, you need to do this according to some system.

For example, at first we leave the burgundy volume in the first place, next to it there may be green or orange. If the green volume is in second place, then either orange and blue, or blue and orange can stand next. If the orange volume is in second place, then either green and blue, or blue and green can stand next. In total, there are 4 possible options.

Any of the 4 volumes can be in the first place, which means that the described procedure must be repeated 3 more times. The case when the blue volume comes first is obtained by the same reasoning.

And the next two cases differ in that the remaining three places should contain the burgundy and blue volumes, but not next to each other. For example, when the green volume comes first, the orange volume must be in third place to separate the burgundy and blue volumes, which may be in second and fourth, or fourth and second, respectively.

As a result, we got only 12 options for placing 4 books on the shelf with a given limit. Is it a lot or a little? If you spend one minute moving books and discussing the resulting version with the customer, then, perhaps, fine. For 12 minutes you can move books and talk. (Try to count how many permutations of 4 books would have turned out without any restrictions?)

Now imagine that the customer has more books than 4. Well, at least 5. It is clear that there will be more placement options, and it really takes longer to rearrange them from place to place, and it is easier to get confused and start repeating ... fight without preparation is no longer worth it. You must first plan your options on paper. For brevity, we will number our colored volumes and rearrange their numbers on paper. To make less mistakes, first we write out all the permutation options, and then delete those that fall under the restriction. So:

"Arrange 5 books on the shelf so that the 1st and 2nd volumes are not side by side. Show all permutation options. "

We have 5 books (or 5 numbers), each of which can come first. Let's make our own plate for each of these 5 cases. In second place can be any of the remaining 4 digits, for each of them we will reserve a column in the plate.

In each column we place pairs of lines in which one of the remaining 3 digits is in third place, and the last two digits are interchanged. Thus, we carefully write out all permutation options. Let's count their total number.

5 (tables) × 4(column) × 3(pairs of lines) × 2(strings) × 1 (option) \u003d 120 (options).

And, finally, delete from all tables the options containing "12" or "21". There were 6 of them in the first and second plates and 12 in the remaining 3, a total of 48 options that did not satisfy the restriction. This means that the customer needs to show 120 - 48 \u003d 72 variants of the arrangement of 5 books. It will take over an hour, even if it takes only a minute to discuss each option.

But where have you seen a person who will hire a designer to rearrange five books? In reality, such tasks arise in libraries where you need to arrange books for the convenience of visitors, in large bookstores where you need to arrange books so as to ensure an increase in demand, etc. That is, where there are not a few books, and not even tens, but hundreds and thousands.

Permutations aren't just about books. This can be required for a large number of any objects in almost any field of activity. This means that both designers and people of other professions may need an assistant, or even better a tool to facilitate the preparatory stage, analyze possible results and reduce unproductive labor. Such tools were created and created by scientists-mathematicians, and then give them to society in the form of ready-made formulas. Mathematicians have not ignored the issues related to permutations, as well as to the placement and combinations of different elements. The corresponding formulas have been around for centuries. These formulas are very simple, they are "handed" to the growing part of society in the lessons of school mathematics. Therefore, everything that was written above is essentially an "invention of the wheel", which had to be resorted to due to the assumption that an interior designer would never need mathematics. Well, let's give up this assumption. Let's review the math concepts, and then go back to the bookshelf problem.

Combinatorics is called the area of \u200b\u200bmathematics in which questions are studied about how many different combinations, subject to certain conditions, can be made up of elements of a given set. When making combinations, we actually select different elements from this set and combine them into groups according to our needs, therefore, instead of the word "combinations", the word "selections" of elements is often used.

Formula for the number of permutations.

Permutations selections of elements are called that differ only in the order of the elements, but not in the elements themselves.

If permutations are performed on a set from n elements, their number determined by the formula
P n = n·( n−1) ( n−2) ... 3 2 1 \u003d n!

n! - a designation that is used to concisely record the work of all natural numbers from 1 to n inclusive and called " n-factorial "(translated from English" factor "-" multiplier ").

Thus, the total number of permutations of 5 books P 5 \u003d 5! \u003d 1 · 2 · 3 · 4 · 5 \u003d 120, which is what we got above. In fact, we derived this formula for a small example. Now let's solve a bigger example.

Problem 1.

The bookshelf holds 30 volumes. How many ways can they be arranged so that volumes 1 and 2 do not stand side by side?

Decision.

Determine the total number of permutations of 30 elements by the formula P 30=30!
To calculate the number of "extra" permutations, first determine how many variants in which the 2nd volume is next to the 1st to the right of it. In such permutations, the 1st volume can take places from the first to the 29th, and the 2nd from the second to the 30th - only 29 places for this pair of books. And for each such position of the first two volumes, the remaining 28 books can occupy the remaining 28 places in an arbitrary order. Rearrangement options for 28 books P 28\u003d 28! In total, if the 2nd volume is located to the right of the 1st, it will turn out to be 29 · 28! \u003d 29 !.
Similarly, consider the case when the 2nd volume is located next to the 1st, but to the left of it. It turns out the same number of variants 29 · 28! \u003d 29 !.
This means that there are 2 · 29! "Superfluous" permutations! And there are 30 necessary arrangement methods! −2 · 29! Let's calculate this value.
thirty! \u003d 29! 30; 30! −2 · 29! \u003d 29! (30−2) \u003d 29! 28.
So, we need to multiply all natural numbers from 1 to 29 and multiply by 28 again.
Answer: 2.4757335 10 32.

This is a very large number (there are 32 more digits after the 2). Even if it took a second for each permutation, it would take billions of years. Is it worth fulfilling such a customer's requirement, or is it better to be able to reasonably object to him and insist on the application of additional restrictions?

Permutations and probability theory.

Even more often, the need to count the number of options arises in probability theory. Let's continue the book theme with the next task.

Problem 2.

There were 30 volumes on the bookshelf. The child dropped the books from the shelf and then arranged them in random order. What is the likelihood that he not put the 1st and 2nd volumes side by side?

Decision.

First, let us determine the probability of event A, consisting in the fact that the child put the 1st and 2nd volumes side by side.
An elementary event is a certain arrangement of books on the shelf. It is clear that the total number all elementary events will be equal to the total number of all possible permutations P 30=30!.
The number of elementary events favorable to event A is equal to the number of permutations in which the 1st and 2nd volumes are side by side. We considered such permutations, solving the previous problem, and got 2 · 29! permutations.
The probability is determined by dividing the number of favorable elementary events by the number of all possible elementary events:
P (A) \u003d 2 29! / 30! \u003d 2 29! / (29! 30) \u003d 2/30 \u003d 1/15.
Event B - child not put the 1st and 2nd volumes side by side - opposite to event A, so its probability P (B) \u003d 1 - P (A) \u003d 1−1 / 15 \u003d 14/15 \u003d 0.9333
Answer:0,9333.

Note: If it is not clear how fractions with factorials can be canceled, then remember that factorial is a short notation of a product. It can always be written long and crossed out the repeating factors in the numerator and in the denominator.

The answer turned out to be a number close to one, which means that with such a number of books, accidentally putting two given volumes side by side is more difficult than not putting them.

Accommodation. Counting the number of placements.

Now suppose the customer has a lot of books and it is impossible to fit them all on open shelves. His request is that you need to select a certain number of any books and place them beautifully. It turned out beautifully or ugly is a matter of the customer's taste, i.e. he wants to see again all options and decide for yourself. Our task is to count the number of all possible book placement options, reasonably convince him and introduce reasonable restrictions.

To understand the situation, let's first assume that "many" are 5 books, that we have only one shelf, and that it only holds 3 volumes. What will we do?
We choose one of 5 books and put it in the first place on the shelf. We can do this in 5 ways. Now there are two places left on the shelf and we have 4 books left. We can choose the second book in 4 ways and put it next to one of the 5 possible first ones. There can be 5 · 4 such pairs. There are 3 books and one place left. One book out of 3 can be selected in 3 ways and placed next to one of the possible 5 · 4 pairs. You get 5 · 4 · 3 different triplets. This means that there are 5 ways to place 3 books out of 5 5 · 4 · 3 \u003d 60.

The figure shows only 4 placement options out of 60 possible. Compare the pictures. Please note that placements can differ from each other either only in the order of the elements, as in the first two groups, or in the composition of the elements, as in the following.

Formula for the number of placements.

Accommodations of n elements by m (places) are called such samples which, having m items selected from data n elements differ from one another either in the composition of the elements or in the order of their arrangement.

Number of placements from n by m denoted A n m and is determined by the formula
A n m \u003d n·( n - 1) ( n - 2) ... ( n − m + 1) = n!/(n - m)!

Let's try to calculate using this formula A n n, i.e. number of placements from n by n.
A n n = n·( n-one)·( n-2) ... ( n-n + 1) = n·( n-one)·( n-2) ... 1 \u003d n!
In this way, A n n = P n = n!

No wonder that the number of placements from n by n turned out to be equal to the number of permutations n elements, because we used the whole set of elements to compose the arrangements, which means that they can no longer differ from each other in the composition of the elements, only in the order of their arrangement, and these are permutations.

Problem 3.

How many ways can 15 volumes be arranged on a bookshelf if you choose from the 30 available books?

Decision.

Determine the total number of placements of 30 elements of 15 by the formula
A 30 15 \u003d 30 29 28 ... (30−15 + 1) \u003d 30 29 28 ... 16 \u003d 202843204931727360000.
Answer: 202843204931727360000.

Will you post real books? Good luck! Count how many lives it will take to go through all the options.

Task 4.

How many ways can 30 books be arranged on two shelves if each of them holds only 15 volumes?

Decision.

Method I.
Let's imagine that we fill the first shelf in the same way as in the previous task. Then the accommodation options from 30 books to 15 will be A 30 15 \u003d 30 29 28 ... (30−15 + 1) \u003d 30 29 28 ... 16.
And every time we place books on the first shelf, we still P 15 \u003d 15! ways we can arrange books on the second shelf. After all, for the second shelf we have 15 books left with 15 seats, i.e. only permutations are possible.
There will be total ways A 30 15 P 15, in this case, the product of all numbers from 30 to 16 will still need to be multiplied by the product of all numbers from 1 to 15, you get the product of all natural numbers from 1 to 30, i.e. thirty!
Method II.
Now let's imagine that we had one long shelf with 30 seats. We placed all 30 books on it, and then sawed the shelf into two equal parts to meet the condition of the problem. How many placement options could there be? As many permutations as possible from 30 books, i.e. P 30 = 30!
Answer: 30!.

It doesn't matter how you solve a math problem. You solve it the way you imagine your actions in a life situation. It is important not to deviate from logic in your reasoning in order to get the right answer anyway.

Placements and probability theory.

In probability theory, placement problems are somewhat less common than problems for other types of samples, since placements have more identifying features - both the order and the composition of the elements, and therefore are less susceptible to random selection.

Problem 5.

The bookshelf contains a collection of works by one author in 6 volumes. Books of the same format are arranged in no particular order. The reader takes 3 books without looking. What is the likelihood that he took the first three volumes?

Decision.

Event A - the reader has the first three volumes. Taking into account the order of selection, he could take them in 6 ways. (These are permutations of 3 elements P 3 \u003d 3! \u003d 1 2 3 \u003d 6, which are easy to list 123, 132, 213, 231, 312, 321.)
Thus, the number of favorable elementary events is 6.
The total number of possible elementary events is equal to the number of placements from 6 to 3, i.e. A 6 3 \u003d 6 ... (6−3 + 1) \u003d 6 5 4 \u003d 120.
P (A) \u003d 6/120 \u003d 1/20 \u003d 0.05.
Answer: 0,05.

Combinations. Counting the number of combinations.

And the last case - all the customer's books are the same color and the same size, but only a part of them can be placed on the shelf. It would seem that the designer has no problems at all, choose as many books from the total as you need, and arrange them on the shelf in no particular order, because the books are outwardly indistinguishable. But they differ, and significantly! These books are different in content. And the customer, perhaps, does not care where Shakespeare's tragedies are, and where Rex Stout's detectives are, on an open shelf or in a closet. Thus, we have a situation when the composition of the sample elements is important, but the order of their arrangement is unimportant.

The figure shows two selections from the "collected works of one author in 5 volumes". The first will appeal to the customer more if he often rereads the early works of this author, placed in the first three volumes, the second - if he more often refers to the later works placed in the last volumes. Both groups look equally beautiful (or equally ugly) and it doesn't matter if the group is located as 123 or as 321 ...

Formula for the number of combinations.

Unordered selections are called of n elements by m and denoted FROM n m.
Number of combinations determined by the formula FROM n m \u003d n!/(n - m)! / m!

There are two divisors in this formula and the symbol " / "which is more web page friendly. But divisions can also be denoted by colons" : "or a horizontal bar" −−− ". In the latter case, the formula looks like an ordinary fraction, in which successive division is represented by two factors in the denominator ... For those who understand more about the fractional representation, all formulas are duplicated at the beginning and at the very end of the page. When analyzing solutions to problems, compare my entry with the usual one.
In addition, all factors and divisors in this formula are products of consecutive natural numbers, so the fraction can be reduced well if it is written in detail. But I skip the detailed reduction in the tasks, it is easy to check it yourself.

It is clear that for the same initial sets from n elements and the same sample sizes (by m elements) the number of combinations must be less than the number of placements. After all, when calculating the placements for each selected group, we also take into account all permutations of the selected m elements, and when calculating combinations, permutations are not taken into account: C n m = A n m/P m = n!/(n − m)!/m!

Problem 6.

How many ways can you arrange 15 volumes on a bookshelf if you choose them from the outwardly indistinguishable 30 books available?

Decision.

We solve this problem in the context of the work of an interior designer, so the order of 15 apparently identical books selected on the shelf does not matter. It is necessary to determine the total number of combinations of 30 elements of 15 by the formula
FROM 30 15 = 30! /(30 − 15)!/15! = 155117520.
Answer: 155117520.

Problem 7.

How many ways can 30 seemingly indistinguishable books be arranged on two shelves if each of them holds only 15 volumes?

If we again answer this question from the perspective of an interior designer, then the order of the books on each shelf is irrelevant. But the customer may or may not care how the books are distributed among the shelves.
1) For example, if both shelves are side by side, both are open, both at the same height, then the customer can say that it does not matter. Then the answer is obvious - 1 way, since the arrangement uses the entire set of 30 books, and no permutations are taken into account.
2) But when one of the shelves is too high, it is important for the customer which books are located on it. In this case, the answer will be the same as in the previous problem - 155117520 ways, because we fill the first shelf with combination selections from 30 to 15, and on the second we place the remaining 15 books without taking into account permutations.

So, there are such formulations of problems that the answers can be ambiguous. For an accurate decision, additional information is needed, which we usually obtain from the context of the situation. The creators of exam assignments, as a rule, do not allow double interpretation of the condition of the problem, they formulate it somewhat longer. However, if you have any doubts, it is better to ask the teacher.

Combinations and probability theory.

In probability theory, combination problems are most common, because grouping without order is more important precisely for indistinguishable elements. If some elements differ significantly from each other, it is difficult to choose them randomly, there are guidelines for non-random selection.

Problem 8.

The bookshelf contains a collection of works by one author in 6 volumes. The books are similarly decorated and arranged in no particular order. The reader takes 3 books at random. What is the likelihood that he took the first three volumes?

Decision.

Event A - the reader has the first three volumes. These are the 1st, 2nd and 3rd volumes. Without considering the order in which he chose the books, but only according to the end result, he could take them in one way. The number of favorable elementary events is 1.
The total number of possible elementary events is equal to the number of groups from 6 to 3 formed without regard to the order of the elements in the group, i.e. equal to the number of combinations S 6 3 \u003d 6! / 3! / (6 - 3)! \u003d 4 5 6 / (1 2 3) \u003d 4 5 \u003d 20.
P (A) \u003d 1/20 \u003d 0.05.
Answer: 0,05.

Compare this problem with problem 5 (on placement). In both problems, very similar conditions and completely identical answers. In essence, this is just one and the same everyday situation and, accordingly, one and the same task that can be interpreted in one way or another. The main thing is that when counting elementary events, both favorable and all possible, there is one and the same understanding of the situation.

Concluding remarks.

For a strict derivation of all formulas (which I did not give here), use two basic rules of combinatorics:

Multiplication rule (the rule " and"). According to it, if element A can be chosen n ways, and for any choice of A, element B can be selected m ways, then the pair A and B can be chosen n m ways.

This rule generalizes to arbitrary length of the sequence.

Addition rule (the rule " or"). It states that if element A can be chosen n ways, and element B can be selected m ways, then choose A or B can n + m ways.

These rules are also needed for solving problems.

Concept factorial also applies to zero: 0! = 1 , since it is believed that the empty set can be ordered in a unique way.

Calculating factorials of large numbers by direct multiplication on a calculator is very long, and very large numbers - even on a computer is not fast. How did you cope with this before computers and calculators were created? Back in the early 18th century, J. Stirling and independently of him A. Moivre obtained a formula for the approximate calculation of factorials, which is the more accurate the larger the number n... This formula is now called by the Stirling formula:

Final challenge.

When solving problems in probability theory using combinatorial methods, it is necessary to carefully analyze the proposed situation in order to correctly choose the type of sample. Try this with the following problem. Solve it, compare the answer, and then click the button to open my solution.

Problem 9.

From the aquarium, in which 6 carp and 4 carp, caught 5 fish with a net. What is the probability that among them there will be 2 carp and 3 carp?

Decision.

An elementary event is "a group of 5 fish in the net". Event A - "among 5 fish caught, there were 3 carp and 2 carp ".
Let n - the total number of all possible elementary events, it is equal to the number of ways to group 5 fish. Total fish in the aquarium 6 + 4 \u003d 10. In the process of catching with a net, the fish are outwardly indistinguishable. (We do not know whether we caught a fish named Baska or Koska. Moreover, until we pulled the net up and looked into it, we do not even know whether it is a carp or carp.) Thus, "catch 5 fish from 10 "means to select a combination type from 10 to 5.
n = S 10 5 = 10!/5!/(10 - 5)!
Having pulled out the net and looking into it, we can determine whether this is a favorable outcome or not, i.e. Does the catch consist of two groups - 2 carp and 3 carp?
A group of carp could be formed by a choice of 6 carp by 2. And it doesn't matter which of them was the first to climb into the net, and who was the second. this is a sample of a combination of 6 to 2. Let us denote the total number of such samples m 1 and calculate it.
m 1 = S 6 2 = 6!/2!/(6 - 2)!
Similarly, the total number of possible groups of 3 carp is determined by the number of combinations from 4 to 3. We denote it m 2.
m 2 = S 4 3 = 4!/3!/(4 - 3)!
Groups of carp and carp are formed in the net independently of each other, therefore, to calculate the number of elementary events favorable to event A, we use the multiplication rule ("and" -rule) of combinatorics. So, the total number of favorable elementary events
m \u003d m 1 m 2 = S 6 2· S 4 3
The probability of event A is determined by the formula P (A) \u003d m / n \u003d С 6 2 С 4 3 / С 10 5
We substitute all the values \u200b\u200bin this formula, write out the factorials, cancel the fraction and get the answer:
P (A) \u003d 6!4! 5! (10 - 5)! / 2! / (6 - 2)! / 3! / (4 - 3)! / 10! \u003d 5/21 ≈ 0.238

Remarks.
1) Combinations are usually found in tasks where the process of forming a group is not important, but only the result is important. It doesn't matter for Sazan Baske he was the first to hit the net or the last, but it is very important for him which group he ended up in - among those in the net, or among those who are free.
2) Please note that we use the "i-rule", because the union "and" is directly in the description of event A, for which we need to calculate the probability of a joint catch of two groups. However, we apply it only after we are convinced of the independence of the samples. Indeed, the carp, swimming up to the net, cannot count its brethren there, and say to the carp: "It's your turn, there are already two of ours." And will the carp agree to climb into the net to please the carp? But if they could agree, then this rule would no longer be applicable. It would be necessary to turn to the concept of conditional probability.

Answer: 0,238.

Show solution.

If you are a school graduate and will take the USE, then after studying this section, return (10 for the basic and 4 for the profile levels of the USE 2020 in mathematics), which can be solved using combinatorial elements and without it (for example, tossing a coin). Which of the possible ways of solving the problem do you like best now?

And if you want to practice a little more in solving combinatorial problems in order to learn how to quickly determine the type of selection and find the necessary formulas, then go to the page

Permutation  notation as a product of independent cycles

makes it easy to find the order of permutation

.

Theorem 2. Order
permutations
(the order of the cyclic subgroup
)is equal least common multiple(LCM) of lengths of independent cycles included in the decomposition of .

Evidence. Imagine the permutation
as a product of independent cycles

. (7)

Since the cycles
are independent (they act on different sets
), and if q is the order of the cyclic subgroup,

,

,

where
.

Therefore, q is the common multiple of the orders of the cycles  k, which coincide with their lengths .

If q is the smallest positive number for which

then

The main theorem of arithmetic. Each positive integer n not equal to one can be written as a product of prime numbers

. (9)

This notation is unique up to the order of the factors.

Replacing the products of coinciding primes in (9) by their powers, we obtain

where

Lots of primes

Example.Any two integers m and n can be written as products of the same prime numbers

,

Example. Determine permutation order
kind

Decision. We represent the permutation  as a product of independent cycles, i.e.

Lengths of independent cycles
are equal

Therefore, the order of the considered permutation is 28.

Decomposition of a permutation into a product of transpositions.

Definition. A cycle of length two is called transposition. Any transposition has the form
and leaves all characters in place except
.

Theorem. Each permutation
can be represented as a product of transposition.

Evidence. The theorem will be proved if we can represent in the form of products of transpositions each of the cycles  k included in the decompositions of the permutation:
.

Consider an arbitrary loop , eg
and decompose it into a product of transpositions.

Cycle decomposition algorithm
into the product of transpositions is shown in Figure 2.

Cycle
transpositions

Fig 2. - Cycle decomposition
into the product of transpositions.

After completing all operations in place of each element of the cycle the next item was found, and the first item moved to the last place. So the loop turned out to be decomposed into a product of transpositions:

Naturally, this decomposition is not unique. for example

Another thing is important - both in the first and in its second decomposition there are an equal number of transpositions - four. If
, then the number of transpositions is
... Expanding each cycle in the same way
permutations into the product of the transposition, we get the decomposition of the entire permutation into the product of transpositions.

Comment. Number of transpositions in a loop
maybe more than four! Take an arbitrary transposition from the decomposition of this cycle, for example,
... Then the product
coincides with the identity permutation and the cycle
can be represented as

It is easy to see that in all these cases the number of transpositions is even and equal to 4, 6, 8. It is clear that the method that "lengthens" the expansion does not change the parity of the original expansion.

Theorem. Let  be a permutation from , a

. (9)

any decomposition  in the product of transpositions.

Then the number

(10)

is called the parity (signature or sign) of the permutation  and is completely determined by , that is, does not depend on the way of decomposing the permutation  into a product of transpositions. Moreover, if
then

. (11)

Definition. Permutation
is called even if
, and odd if
.

It follows from the definition of parity of a permutation that all transpositions are odd permutations.

Indeed, if - transposition, then
then

Corollary 1. All even permutations of degree n form a subgroup
order
(it is called an alternating group of degree n).

Corollary 2. Let the permutation
decomposed into a product of independent cycles

,

where
,
, …,
, …,
- lengths of independent cycles.

. (12)

Evidence. Indeed, by the previous theorem, we have

.

Besides,
since everyone the cycle is written as a product
transpositions, then

A permutation is a combination of elements from N different elements taken in a specific order. In a permutation, the order of the elements is important, and in the permutation, all N elements.

Task: Find all possible permutations for a sequence of numbers 1, 2, 3.
The following permutations exist:

1: 1 2 3
2: 1 3 2
3: 2 1 3
4: 2 3 1
5: 3 1 2
6: 3 2 1

Permutations without repetitions

The number of permutations for N different elements is N!... Really:

• in the first place can be placed any of N elements (all options N),
• any of the remaining ones can be placed in the second position (N-1) elements (total options N (N-1)),
• if we continue this sequence for all N places, we get: N · (N-1) · (N-2) · ... · 1, that is, all N! permutations.

Consider the problem of obtaining all permutations of numbers 1 ... N (that is, sequences of length N), where each of the numbers appears exactly 1 time. There are many options for the order in which permutations are obtained. However, the problem of generating permutations in lexicographic order (see example above). In this case, all permutations are sorted first by the first number, then by the second, etc. in ascending order. So the first will be the permutation 1 2 ... N, and the last one - N N-1 ... 1.

Consider an algorithm for solving the problem. An initial sequence of numbers is given. To obtain each next permutation, you must perform the following steps:

• It is necessary to view the current permutation from right to left and at the same time make sure that each next element of the permutation (element with a higher number) is no more than the previous one (element with a lower number). As soon as this ratio is violated, it is necessary to stop and mark the current number (position 1).
• Review the path traveled from right to left again until we reach the first number, which is greater than the one marked in the previous step.
• Swap the two received elements.
• Now in the part of the array, which is located to the right of position 1, you need to sort all the numbers in ascending order. Since before that they were all already written in descending order, it is necessary to simply flip this part of the subsequence.

Thus, we will get a new sequence, which will be considered as the starting one in the next step.

C ++ implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include
using namespace std;

{
int s \u003d a [i];
a [i] \u003d a [j];
a [j] \u003d s;
}
bool NextSet (int * a, int n)
{
int j \u003d n - 2;
while (j! \u003d -1 && a [j]\u003e \u003d a) j--;
if (j \u003d\u003d -1)
return false; // no more permutations
int k \u003d n - 1;
while (a [j]\u003e \u003d a [k]) k--;
swap (a, j, k);
int l \u003d j + 1, r \u003d n - 1;
while (l swap (a, l ++, r--);
return true;
}
void Print (int * a, int n) // permutation output
{
static int num \u003d 1; // permutation number
cout.width (3);
cout<< num++ << ": " ;
for (int i \u003d 0; i< n; i++)
cout<< a[i] << " " ;
cout<< endl;
}
int main ()
{
int n, * a;
cout<< "N = " ;
cin \u003e\u003e n;
a \u003d new int [n];
for (int i \u003d 0; i< n; i++)
a [i] \u003d i + 1;
Print (a, n);
while (NextSet (a, n))
Print (a, n);
cin.get (); cin.get ();
return 0;
}

Execution result

Permutations with repetitions

The task of generating permutations deserves special attention N elements in case the elements of the sequence can be repeated. Let's say the original sequence consists of elements n 1, n 2 ... n kwhere element n 1 repeats r 1 time, n 2 repeats r 2 times, etc. Wherein n 1 + n 2 + ... + n k \u003d N... If we count everything n 1 + n 2 + ... + n k elements of the permutation with different repetitions, then a total of different variants of permutations ( n 1 + n 2 + ... + n k)! ... However, among these permutations, not all are different. Indeed, all r 1 elements n 1 we can permute places with each other, and this permutation will not change. Likewise, we can rearrange elements n 2, n 3 and so on. As a result, we have r 1! variants of recording the same permutation with different arrangement of repeating elements n 1... Thus, any permutation can be written r 1! r 2! ... r k! ways. Therefore, the number of distinct permutations with repetitions is

To generate repetitive permutations, you can use the non-repetitive permutation generation algorithm above. Let's introduce a repeated element into array a. Below is the program code for generating permutations with repetitions (only the code of the main () function has been changed).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include
using namespace std;
void swap (int * a, int i, int j)
{
int s \u003d a [i];
a [i] \u003d a [j];
a [j] \u003d s;
}
bool NextSet (int * a, int n)
{
int j \u003d n - 2;
while (j! \u003d -1 && a [j]\u003e \u003d a) j--;
if (j \u003d\u003d -1)
return false; // no more permutations
int k \u003d n - 1;
while (a [j]\u003e \u003d a [k]) k--;
swap (a, j, k);
int l \u003d j + 1, r \u003d n - 1; // sort the rest of the sequence
while (l swap (a, l ++, r--);
return true;
}
void Print (int * a, int n) // permutation output
{
static int num \u003d 1; // permutation number
cout.width (3); // width of the output field of the permutation number
cout<< num++ << ": " ;
for (int i \u003d 0; i< n; i++)
cout<< a[i] << " " ;
cout<< endl;
}
int main ()
{
int n, * a;
cout<< "N = " ;
cin \u003e\u003e n;
a \u003d new int [n];
for (int i \u003d 0; i< n; i++)
a [i] \u003d i + 1;
a \u003d 1; // repeating element
Print (a, n);
while (NextSet (a, n))
Print (a, n);
cin.get (); cin.get ();
return 0;
}

The result of the above algorithm: