1. Generating Permutations
2. Generating Subsets
3. Exercises

**Algorithms
for Generating Combinatorial Objects**

*1. Generating Permutations*

*2. Generating Subsets*

*3. Exercises*

In this
section, we keep our promise to discuss algorithms for generating
combi-natorial objects. The most important types of combinatorial objects are
permuta-tions, combinations, and subsets of a given set. They typically arise
in problems that require a consideration of different choices. We already
encountered them in Chapter 3 when we discussed exhaustive search.
Combinatorial objects are stud-ied in a branch of discrete mathematics called
combinatorics. Mathematicians, of course, are primarily interested in different
counting formulas; we should be grate-ful for such formulas because they tell
us how many items need to be generated. In particular, they warn us that the
number of combinatorial objects typically grows exponentially or even faster as
a function of the problem size. But our primary interest here lies in
algorithms for generating combinatorial objects, not just in counting them.

**Generating
Permutations**

We start
with permutations. For simplicity, we assume that the underlying set whose
elements need to be permuted is simply the set of integers from 1 to ** n**; more generally, they can be
interpreted as indices of elements in an

We can
insert ** n** in the previously generated
permutations either left to right or right to left. It turns out that it is
beneficial to start with inserting

The
advantage of this order of generating permutations stems from the fact that it
satisfies the ** minimal-change requirement**: each permutation can be ob-tained
from its immediate predecessor by exchanging just two elements in it. (For the
method being discussed, these two elements are always adjacent to each other.

Check
this for the permutations generated in Figure 4.9.) The minimal-change
re-quirement is beneficial both for the algorithm’s speed and for applications
using the permutations. For example, in Section 3.4, we needed permutations of
cities to solve the traveling salesman problem by exhaustive search. If such
permuta-tions are generated by a minimal-change algorithm, we can compute the
length of a new tour from the length of its predecessor in constant rather than
linear time (how?).

It is
possible to get the same ordering of permutations of ** n** elements without explicitly
generating permutations for smaller values of

3 and 4
are mobile while 2 and 1 are not. Using the notion of a mobile element, we can
give the following description of the ** Johnson-Trotter algorithm** for
generating permutations.

**ALGORITHM** *JohnsonTrotter**(n)*

//Implements
Johnson-Trotter algorithm for generating permutations //Input: A positive
integer *n*

//Output:
A list of all permutations of {1** , . . . , n**}

**while **the last permutation has a mobile
element** do **find its largest mobile
element *k*

swap ** k** with the adjacent element

reverse
the direction of all the elements that are larger than ** k** add the new permutation to the
list

Here is
an application of this algorithm for ** n** = 3, with the largest mobile
element shown in bold:

This
algorithm is one of the most efficient for generating permutations; it can be
implemented to run in time proportional to the number of permutations, i.e., in
** (n**!

One can
argue that the permutation ordering generated by the Johnson-Trotter algorithm
is not quite natural; for example, the natural place for permu-tation ** n(n** − 1

123 132 213 231 312 321*.*

So how
can we generate the permutation following *a*_{1}*a*_{2} *. . . a _{n}*

**ALGORITHM** *LexicographicPermute**(n)*

//Generates
permutations in lexicographic order //Input: A positive integer *n*

//Output:
A list of all permutations of {1** , . . . , n**} in lexicographic order
initialize the first permutation with 12

**while **last permutation has two
consecutive elements in increasing order**
do**

reverse
the order of the elements from *a _{i}*

add the
new permutation to the list

**Generating
Subsets**

Recall
that in Section 3.4 we examined the knapsack problem, which asks to find the
most valuable subset of items that fits a knapsack of a given capacity. The
exhaustive-search approach to solving this problem discussed there was based on
generating all subsets of a given set of items. In this section, we discuss
algorithms for generating all 2**^{n}** subsets
of an abstract set

The
decrease-by-one idea is immediately applicable to this problem, too. All
subsets of ** A** = {

Similarly
to generating permutations, we do not have to generate power sets of smaller
sets. A convenient way of solving the problem directly is based on a one-to-one
correspondence between all 2**^{n}** subsets
of an

and all 2**^{n}** bit strings

Note that
although the bit strings are generated by this algorithm in lexico-graphic
order (in the two-symbol alphabet of 0 and 1), the order of the subsets looks
anything but natural. For example, we might want to have the so-called ** squashed
order**, in which any subset involving

A more
challenging question is whether there exists a minimal-change algo-rithm for
generating bit strings so that every one of them differs from its immediate
predecessor by only a single bit. (In the language of subsets, we want every
subset to differ from its immediate predecessor by either an addition or a
deletion, but not both, of a single element.) The answer to this question is
yes. For example, for ** n **=

000 001 011 010 110 111 101 100*.*

Such a
sequence of bit strings is called the ** binary reflected Gray code**. Frank
Gray, a researcher at AT&T Bell Laboratories, reinvented it in the 1940s to
minimize the effect of errors in transmitting digital signals (see, e.g.,
[Ros07], pp. 642–

´

643).
Seventy years earlier, the French engineer Emile Baudot used such codes in
telegraphy. Here is pseudocode that generates the binary reflected Gray code
recursively.

**ALGORITHM** *BRGC**(n)*

//Generates
recursively the binary reflected Gray code of order ** n** //Input:
A positive integer

//Output:
A list of all bit strings of length ** n**
composing the Gray code

**else **generate list** **** L**1 of bit strings of size

add 0 in
front of each bit string in list ** L**1 add 1
in front of each bit string in list

**return ***L*

The
correctness of the algorithm stems from the fact that it generates 2**^{n}** bit strings and all of them are
distinct. Both these assertions are easy to check by mathematical induction.
Note that the binary reflected Gray code is cyclic: its last bit string differs
from the first one by a single bit. For a nonrecursive algorithm for generating
the binary reflected Gray code see Problem 9 in this section’s exercises.

**Exercises
4.3**

**
**Is it realistic to implement an algorithm that
requires generating all permu-tations of a 25-element set on your computer?
What about all the subsets of such a set?

**
**Generate all permutations of {1** ,** 2

**
**the bottom-up minimal-change algorithm.

**
**the Johnson-Trotter algorithm.

**
**the lexicographic-order algorithm.

**
**Apply *LexicographicPermute*
to multiset {1** ,** 2

**
**Consider the following implementation of the
algorithm for generating per-mutations discovered by B. Heap [Hea63].

**ALGORITHM** *HeapPermute**(n)*

//Implements
Heap’s algorithm for generating permutations

//Input: A positive integer ** n** and a global array

//Output:
All permutations of elements of *A*

**if ***n*** **=** **1** write ***A*

**else**

**for ***i*** **←** **1** to ***n*** do**

*HeapPermute**(n** *−* *1*)*

**if ***n*** **is odd

swap ** A**[1] and

**
**Trace the algorithm by hand for ** n** = 2

**
**Prove the correctness of Heap’s algorithm.

**
**What is the time efficiency of *HeapPermute*?

**
**Generate all the subsets of a four-element set ** A** = {

**
**What simple trick would make the bit string–based
algorithm generate subsets in squashed order?

**
**Write pseudocode for a recursive algorithm for
generating all 2**^{n}** bit
strings of length

**
**Write a nonrecursive algorithm for generating 2**^{n}** bit strings of length

**
****a. **Generate the binary reflexive
Gray code of order 4*.*

**
**Trace the following nonrecursive algorithm to
generate the binary re-flexive Gray code of order 4** .** Start
with the

**
**Design a decrease-and-conquer algorithm for
generating all combinations of ** k **items
chosen from

**
***Gray code
and the Tower of Hanoi*

**
**Show that the disk moves made in the classic
recursive algorithm for the Tower of Hanoi puzzle can be used for generating
the binary reflected Gray code.

**
**Show how the binary reflected Gray code can be used
for solving the Tower of Hanoi puzzle.

*Fair attraction *In olden days, one could
encounter the following attraction* *at
a fair. A light bulb was connected to several switches in such a way that it
lighted up only when all the switches were closed. Each switch was controlled
by a push button; pressing the button toggled the switch, but there was no way
to know the state of the switch. The object was to turn the light bulb on.
Design an algorithm to turn on the light bulb with the minimum number of button
pushes needed in the worst case for ** n**
switches.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Decrease and Conquer : Algorithms for Generating Combinatorial Objects |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.