Can all objects be matched in sequence?

Question

First of all, this is not homework or something like that, it is a leading question from my last question Candidate in finding a control in an array .

There are n objects objects O1, O2, ..., On is the array F[1...n] , F[i] is the number Oi (that is, there are F[i] Ois, the array F[1...n] ), and each F[i] > 0 .

Now apply the following rule for pairing objects:

if i != j , Oi can be paired with Oj, else if i == j , Oi cannot be paired with Oj.

i., only two different types of objects can be paired with each other.

• Can there be a valid pairing method for the input array F[1...n] ? Give the algorithm with the best time complexity to say true or false and prove its correctness.

• If exists, print one valid parry sequence. Give an analysis of the algorithm and time / space.

For instance, F[] = {10, 2, 4, 4};

Then there is at least one valid mating method:

2 O1s and 2 O2s in pair, 4 O1s and 4 O3s in pair, 4 O1s and 4 O4s in pair.

One valid mating sequence:

(1) (1.2) (1.3) (1.3) (1.3) (1.3) (1.4) (1.4) (1.4) (1, 4)

Answer 1

Check for a solution in O (n)

Let s be the sum of F

• If s is odd, there is no solution (intuitive)
• If there exists i such that F[i] > s/2 there is no solution (intuitive)
• Otherwise, there is a solution (proof by construction)

Finding a solution in O (n)

 # Find s s = 0 for i in 1..n: s += F[i] # Find m such that F[m] is maximal m = 1 for i in 1..n: if F[i] > F[m]: m = i if s % 2 != 0 or F[m] > s/2: fail a = 1 b = 1 # Pair off arbitrary objects (except those of type m) until F[m] = s/2 while s/2 > F[m]: # Find a type with a non-zero frequency until F[a] > 0 and a != m: a = a + 1 # Find another type with a non-zero frequency until F[b] > 0 and b != m and b != a: b = b + 1 count = min(F[a], F[b], s/2 - F[m]) pair(a, b, count) # Pair off objects of type m with objects of different types while F[m] > 0: # Find a type with a non-zero frequency until F[a] > 0 and a != m: a = a + 1 pair(a, m, F[a]) end of algorithm def pair(a, b, count): # Pairs off 'count' pairs of types a and b F[a] = F[a] - count F[b] = F[b] - count s = s - (2 * count) output "Pairing off $a and $b ($count times)" 

The two while are linear. The first while loop increments either a or b at least at each iteration, because after matching the pairs count either F[a] is equal to zero, or F[b] is equal to zero, or s/2 = F[m] , and the cycle ends. a and b can be increased no more than n times each time before all elements are visited. The second while loop is also linear, since it increments a by at least every iteration.

Key invariants: (1) F[m] is the largest element of F
(2) F[m] <= s/2
I think both of them are fairly obvious on examination.

With an internal loop, while s/2 > F[m] must be at least two other types of objects with nonzero frequencies. If there was only one, say a , then F[a] + F[m] = s
F[a] = s - F[m] > s - s/2 (from the loop condition)
F[a] > s/2
F[a] > F[m]
which is a contradiction of invariant (1) .

Since there are at least two types with nonzero frequencies (except m ), the cycle will be able to find the types a and b and pair objects up to s/2 = F[m] .

The second cycle is trivial. Since exactly half of the objects are of type m , each object of type m can be paired with an object of another type.

Answer 2

Here is one suggestion. I am not sure if this succeeds for any possible case, or if it is the most efficient possible algorithm.

Let n be the total number of indices. Create a priority priority queue of object type numbers, where each type of object is its index i . In other words, create a priority queue in which the sort values ​​in the queue are F values. Associate each node with a list of all objects of this type. It takes O(n log(n)) .

For each type of object, starting from the type that has the most duplicates and moves to the type with the least number, connect one object from this "class" of objects with one object for each of the other classes that still have objects in them and delete this object from this node in the queue. Since each element of the queue, except the top one, will have fewer objects in it, most of the queue will still be in the order of priority; the top node, however, will have n-1 fewer elements (or it will be empty), so heapify down to maintain the queue. Also, delete nodes without objects. Repeat this process with the new highest queue value until all nodes are paired. It takes O(n log(n) + k) , where k is the total number of elements. Assuming k significantly greater than n , the total time complexity is O(k) .

Again, I am not entirely sure that this will always find a solution, if possible. My intuition is that if you re-type (if necessary) after each pairing, you will see that if a full connection is possible, it will , but (1) it will be much less effective, and (2) I'm not sure what cases this will happen if the original algorithm does not exist, and (3) I am not entirely sure that this will work every time.

As for which values ​​of F have no solution, it is obvious that if there is one class of objects that has more elements than all other classes, it cannot be conjugated. Other than that ... I'm not sure. It would be interesting to investigate whether my “improved” algorithm evaluates each case correctly or not.