Abstract: | The solution of the following problems is offered. Suppose a multiset J (¦J¦=p) is given. For each pair of elements and J, a number 1 P is given. Moreover, if 1 < x is undefined. If x=1, then x=p. Problem 1. Find the permutation 1...F of elements of the multiset J satisfying the following conditions. Let i, i=. If i,j < x, thenj <i. If i,j > x, then i<j. Such a permutation is called a PC-schedule. Problem 2. Find a PC-schedule in which the following property holds: if i < x < j, i=, j=, then. Such a PC-schedule is called an SC-schedule. The conditions under which these problems have solutions are studied. For their solution an algorithm of shifts is used with the complexity O(¦B(J)¦2¦J¦).Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 124, pp. 44–72, 1983. |