**General Solution of the Combinatorial
Problems**

Bipul Syam Purkayastha
Arindam Bhattacherjee

and Aparajita Das

Department of Computer
Science,

Silchar

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

(x_{1,}
x_{2,} x_{3, }… x_{p}), each component satisfying
certain conditions, which can be obtained by using t nested loops with x_{t} = I_{t}(J_{t})K_{t},
where I_{t}, J_{t}, K_{t} are pre-specified natural numbers, which
stands for starting limit, increment and the ending limit for x_{t} .
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 £ x_{i}
£
n "i ½1 £ i £ r,

(b)
x_{i} ¹ x_{j} "j ½i +1 £ j £ r.

(ii) Combinations

(a) 1 £ x_{i}
£
n "i ½1 £ i £ r,

(b)
x_{j} < x_{j+1} "j ½1 £ j£ r - 1.

(iii) Partitions

(a) 1 £ x_{i}
£
n "i ½1 £ i £ r,

r

(b) x_{j} £ x_{j+1} "j
½1
£
j £
r – 1 and S x_{k} = 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 £ x_{1}
£
n + 1 - r

and x_{j}_{-1} + 1 £ x_{j
}£
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 x_{i-1}
+ 1 £ x_{i } is sufficient for combinations; consequently
the explicit test for

x_{j} < x_{j+1 }is no longer necessary.

(iii) similarly for partitions (a), (b) Þ 1 £ x_{1} £ [n / r],

x_{j}_{
- 1} £ x_{j} £ [(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 x_{i} £ x_{i+1}
will do the trick. Then the only condition necessary to

r

be tested is S x_{k} = 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 2^{nd} Ed. Addison-Weseley,

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.