Algorithm 8.6 Permutation Generation Part 1

This page is a generated reference surface for selective reading. It exists to keep the learner apps guide-first while still preserving source access.

Learning objectives

• Explain the main ideas and vocabulary in Algorithm 8.6 Permutation Generation Part 1.
• Work through the source examples for Algorithm 8.6 Permutation Generation Part 1 without depending on raw chunk order.
• Use Algorithm 8.6 Permutation Generation Part 1 as selective reference when learner modules point back to How To Solve It By Computers.

Prerequisites

• None curated yet.

Module targets

• module-05-problem-solving

AI companion modes

• Explain simply
• Socratic tutor
• Quiz me
• Challenge my understanding
• Diagnose my confusion
• Generate extra practice
• Revision mode
• Connect forward / backward

Source-of-truth note

This unit is anchored to How To Solve It By Computers and the source chapter "Algorithm 8.6 Permutation Generation Part 1". Use external resources only to clarify, extend, or modernize details without replacing the chapter's conceptual spine.

External enrichment

No chapter-specific enrichment resources are curated yet. Add them in the unit manifest when a source clearly improves learning.

Source provenance

• Primary source: How To Solve It By Computers
• Source chapter: Algorithm 8.6 Permutation Generation Part 1
• Raw source file: 133-algorithm-8-6-permutation-generation-part-1.md

Merged source

Algorithm 8.6 Permutation Generation Part 1

---

id: '133-algorithm-8-6-permutation-generation-part-1' book: "How to Solve It by Computer" source_file: "../how-to-solve-it-by-computer-r-g-dromey-for-unit-1.pdf" ocr_source: "../ocr-extracted.txt" chunk_index: 133 chunk_total: 138 title: "Algorithm 8.6 PERMUTATION GENERATION (Part 1)" part: "" chapter: "3 BORDEN 4" pages: start: 443 end: 446 words: 1031

Algorithm 8.6 PERMUTATION GENERATION (Part 1)

3 BORDEN 4

Algorithm 8.6 PERMUTATION GENERATION

Prnhlam

firqt inteøerq Deqion nn nlonrithm that oenernteq all nermntntinnq of the n taken r at a time where n and r are greater than or equal to 1.

Algorithm development

AS we Silan see, tne protnem Oi pellilutauoll blia1Cb bU111c the characteristics of the last two problems. It also possesses other aspects which

should help to deepen our understanding of recursion. As with our previous

two problems, we will concentrate on dealing with the problem expressed in

terms of integers. Related problems for other than integers can be handled

similarly.

10 maKe a w IL 11 prot,uem wc vall 'COIIb1UC1 a

involving the generation of all permutations of the first 5 integers taken 3 at a

time. Unlike the combinations' situation, order is important and so sequen-

ces like {1, 2, 3}, {2, 1, 3} and {3, 1, 2} all represent distinct permutations.

Some of the permutations of the first 5

integers taken 3 at a time are:

1 1 1 1 1 5 5 1

2 2 2 3 3 3 4 4

2 3 3 4 2 4 5 5

VVV assume all of the 5 (n) values as in algorithm 8.4. However, within a given Dermutation. no value mav occur in more than one column (i.e. no reoeti-

tions are allowed). In the combination generation problem too, no repeti-

tions were allowed. We should therefore see if this approach can be used

here.

Unfortunately, when we try to solve the permutation generation prob-

lem in the same way as the combination generation problem we run into

trouble. The problem arises because the integers within a given permutation

permutation.

It may be worthwhile trying to phrase the problem in terms of a simple

hilt on

with the clues we need to solve the problem. At this point there are three

things we have discovered about permutation sets. Firstly, each column must

be able to take on all of the first n integer values. Secondly, the integers in a

permutation need not be ordered and, thirdly, there must be no repetitions

within a given permutation. Our work in algorithm 8.4 gave us a simple

nested-loop structure for ensuring that each column assumed all the values

in the range 1 to n. Three loops were needed to solve the 5 U3 problem. We

therefore might expect to be able to use three loops to solve the 5 PR problem.

If tn thic noprl napthnrl fnr thot nn

integer was repeated in each permutation printed. Applying this restriction,

the algorithm needed to solve the 5P3 problem might be:

for 1: = 1 to 5 do

for j.

1 to 5 do

fnr Lr - --

if "there are no duplicates among i, j, and k" then

"print out i, j, and k as next permutation"

Our experience with the last two algorithms has shown us that a set of r

nested loops can often oe replaceu oy a recursive proceuure that caus Itself to -s

depth r. We might therefore be encouraged to try to formulate a recursive

solution to the present problem. The explorations we have made so far

suggest that we may tentatively describe the required algorithm as follows:

for i.

1 to n do

"solve the remaining smaller problems similarly ensuring that

there are no duplicates."

end

Thic menhnniqm will hnndle the oenerntinn of the vnlneq in the firet "Olnmn b i o generate the range of values In the second column, we once again need a loop that generates integers in the range 1 to n. The generation of integers

for the second column is accompanied by a restriction. No second column

value can be the same as its first column value. Extending this argument to the

third column we see that although all integers in the range 1 to n are potential

-nndidnteq nn third on n he to either the firet nr

column values of the current permutation. The same argument applies to

subsequent columns. We must now face up to the problem of generating

these restricted column values. We might envisage using a collection of

complicated if-statements or a loop to do the job but these methods look as

though they will be unwieldy. We therefore need to look for a simple way of

remembering what the current situation is in the columns that precede the

1current column. w nat would be preferable IS a Single test to see If the current

integer is eligible for use in the current column. The question that remains is,

can we construct a one step test to decide the eligibility of the current integer in the permutation being generated? Since the test must not involve a series

of comparisons the issue is, in what other way can we remember what

integers have been used alreadv? Our onlv alternative seems to be to use an

all ay Ilitcgclb Ila vc vccll UbCU. quCbLIU11 1b, call an

array be compatible with making a single eligiblity test? Our answer to this

must be yes, provided we make the test by indexing. This will involve several

things. When integer i has been employed in a column we will need to mark

accordingly the ith position in our "remembering" array as it is used. At any

given time we can then test if a given integer k has already been used by

an a y at vccll Lilalr-scu. an lay vall ve used for this purpose.

Having overcome the nroblem of deciding what integers are eligible for

a particular column, we see that the problem that remains to be solved is almost the same as that for generating permutations with unrestricted repeti-

tions (algorithm 8.4). We can therefore summarize our nrogress with the

following outline for a permutation generation algorithm:

for i.

1 to n do

if integer i is eligible for the current column k then

(a) mark ith integer as no longer eligible for subsequent columns,

(b) save i as current column value,

(c) recursively generate values for the remaining columns for the cur-

rnnf

Studying this mechanism carefully, we see that it has a flaw because as soon