[BUG] Shard allocator leaves unassigned shards

[jainankitk]

Describe the bug
Shard allocation does not consider all combinations especially for Zone Aware allocation leaving unassigned shards which could be assigned otherwise. This is observed more commonly for clusters with total_shards_per_node setting enabled.

To Reproduce
Steps to reproduce the behavior:
Create 3 node cluster with each node in different AZ. Now create index with 3 shards and 1 replica. Now, 1 of the shard might not get assigned:

0p and 1r were assigned to Node1
1p and 0r were assigned to Node2

so, only Node3 was left for 2p and 2r. Hence, 2r cannot be assigned as not both copies can be in same zone. Also, other nodes are not eligible as they violate total shards per node constraint

Expected behavior
The shard allocator should be able to pick any other alternative assignment like:

Node1 - 0p, 2r
Node2 - 0r, 1p
Node3 - 1r, 2p

Plugins
NA

Screenshots

% cat /tmp/explain | grep explanation | sort | uniq -c
      1   "allocate_explanation" : "cannot allocate because allocation is not permitted to any of the nodes",
      1           "explanation" : "a copy of this shard is already allocated to this node [[index][2], node[xxxxx], [P], s[STARTED], a[id=xxxxx]]"
      1           "explanation" : "there are too many copies of the shard allocated to nodes with attribute [zone], there are [2] total configured shard copies for this shard id and [3] total attribute values, expected the allocated shard count per attribute [2] to be less than or equal to the upper bound of the required number of shards per attribute [1]"
      4           "explanation" : "too many shards [2] allocated to this node for index [index], index setting [index.routing.allocation.total_shards_per_node=2]"

Host/Environment (please complete the following information):

• Observed in OS 1.0, but should be part of other releases as well

Additional context
Add any other context about the problem here.