General Solution of the Combinatorial Problems

Using the Control Structure

 

Bipul Syam Purkayastha Arindam Bhattacherjee

and Aparajita Das

Department of Computer Science,

Assam University

Silchar

E-mail : bipul_sh@hotmail.com

 

Many combinatorial problems can be characterised as a selection problem, in which one is to find among all the solutions to a problem, one or more with particular properties. The selection problem is often related to efficient algorithms that produce the desired solutions. We have found that a control structure for variable number of nested loops is very suitable for solving a large number of combinatorial problems. Thus we propose a simple structure of general solution of the combinatorial problems.

 

1 Introduction

The combinatronics have been the subject of extensive studies for many years[1,2,3,4]. The motivation for this is partly due to the important role they play in many problems in computer science, as well as in various algebraic problems. Combinatronics provide the tools necessary for analysing algorithms, data structures, design of computer hardware by VLSI etc. Thus, combinatronics techniques will undoubtedly continue to play a role in computer science. Widely varied applications of combinatronics to problems in social sciences, and computer science have demonstrated the generality of the technique and enhanced its importance as a branch of applied mathematics. Many combinatorial problems require an exhaustive list of permutations, combinations and so on. Such problems are ubiquitous especially in computer science; since the computer can aid in such analyses. Thus combinatronics and computers science are symbiotic. This close connection works to the advantage of both areas.

Our interest in the problem arises not only because of the combinatorics involved but as it represents a problem that does not have simple general solution.

2 Algorithm and Implementation :

In many combinatorial problems we have to find the set of all vectors

(x1, x2, x3, xp), each component satisfying certain conditions, which can be obtained by using t nested loops with xt = It(Jt)Kt, where It, Jt, Kt are pre-specified natural numbers, which stands for starting limit, increment and the ending limit for xt . This process can be very easily implemented by the generalized control structure. To illustrate this idea we have considered three most common combinatorial problems, namely permutations, combinations and partitions.

We have considered all permutations and combinations of n natural numbers taking r at a time and all partitions of n objects into r mutually disjoint subsets.

 

Solution :

(i)                  Permutations

(a) 1 xi n "i 1 i r,

(b) xi xj "j i +1 j r.

(ii)                Combinations

(a) 1 xi n "i 1 i r,

(b) xj < xj+1 "j 1 j r - 1.

(iii)               Partitions

(a) 1 xi n "i 1 i r,

r

(b) xj xj+1 "j 1 j r 1 and S xk = n

k=1

r DO loops with indexing parameters 1(1)n for each loop will take care of the condition (a) in each of the above problems, which can be implemented with routine NEST.

The condition (b) can be tested very easily in the routine PRE with very minor modifications in code for the particular problem.

The implementation of the SUBROUTINE subprograms called NEST and PRE has been discussed in [2,4].

These are easier to implement than conventional formulae for the combinatorial problems. By very simple modifications of the program for generation of permutation we can take care of the generation of combinations. To accommodate further cases like permutation without restrictions etc. involves just changing the conditions in the loop and no major modification.

For problems (ii), (iii) even better solutions are possible.

(ii) (a), (b) 1 x1 n + 1 - r

and xj-1 + 1 xj n + j r, 2 j r.

So the indexing parameters are i(1)n + i r for the ith loop and the control variable is

such that xi-1 + 1 xi is sufficient for combinations; consequently the explicit test for

xj < xj+1 is no longer necessary.

(iii) similarly for partitions (a), (b) 1 x1 [n / r],

xj - 1 xj [(n + 1 j) / (r + 1 j)], 2 j r.

For partitions the indexing parameters are 1(1) [(n + 1 i) / (r + 1 i)] for the ith loop and the control variable xi xi+1 will do the trick. Then the only condition necessary to

r

be tested is S xk = n

k=1

 

Thus it is quite clear that generalized control structure for a variable number of nested DO loops is a very efficient tool for handling many of the combinatorial problems and also problems requiring backtracking. This immediately yields efficient iterative algorithms for the combinatorial problems. Thus we have a simple structure of general solution of the combinatorial problems.

Reference :

 

1. Knuth, D. E. The Art of Programming, Vol. 1 2nd Ed. Addison-Weseley, Reading,

Massachusetts 1973.

2. Mckenzie, B. J. Takaoka, T. A control structure for a variable number of nested loops.

The Computer J. 26(983), 282-283.

3. Sedgewick, R. Permutation generation methods, ACM computing Surveys

9(No.2)(1977) 137-164.

4. Skordalakis, E.; Papakontantinou, G. A control structure for a variable number of

nested loops. The Computer J. 25(1982), 48-51.

5. Tompkins, C. Machine attacks on problems whose variables are permutations. Proc.

Symposium in Appl. Math. Numerical Analysis, McGraw Hill,

New York, 6(1956)195-211.

6. Zals, S. A new algorithm for generation of permutations. BIT 24(1984), 196-204.