Member Avatar for delta_frost

We had been assigned a problem in our Data Structures Laboratory that goes like this:

Fill 4 queues with 10 numbers each(Ranging from 1 through 20).Each number need not be unique,i.e a number may be repeated in a queue.Remove an element from each queue.Say 1,3,11,6 are removed from queues 1,2,3 and 4 respectively.Then find the largest number out of them.Here it is 11.Then find out the queue which gave the smallest number.In this case,it would be 1.Then insert the largest number into the queue from which you obtained the smallest number i.e. add 11 to queue 1.Repeat until you get an empty queue(Multiple queues may be emptied at once).

I used the rand() along with the srand(time(NULL)) function ot insert the numbers into the queues.
The teacher specified what to do when you found two or more equal numbers.I wrote a function but it got too messy.My query is what is the probability that any [A]two of the four numbers removed from the queues would be equal [B]three of the four numbers removed from the queues would be equal ?

If the probability is low enough,I would not have to bother about writing the function to check for equality cases.

  • 3 Contributors
  • 2 Replies
  • 198 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by TrustyTony

Dani AI

Generated

Assuming each queue entry is generated independently and uniformly from {1..20} (e.g. rand()%20+1), one round is four independent draws and the total outcome count is 20^4 = 160,000. Counting by multiplicity yields these exact probabilities:

  • All four distinct: (201918*17)/20^4 = 116,280 / 160,000 = 0.72675 (72.675%).
  • Exactly one pair (one value appears twice, the other two values different): 20 C(4,2) P(19,2) / 20^4 = 41,040 / 160,000 = 0.25650 (25.65%).
  • Two different pairs: C(20,2) * C(4,2) / 20^4 = 1,140 / 160,000 = 0.007125 (0.7125%).
  • Exactly three equal (a triple + one different): 20 C(4,3) 19 / 20^4 = 1,520 / 160,000 = 0.00950 (0.95%).
  • All four equal: 20 / 160,000 = 0.000125 (0.0125%).

If “[A] two equal” is interpreted as “at least one equality” (i.e. not all distinct) the probability is 1 − 0.72675 = 0.27325 (27.325%). If it means “exactly one pair” the probability is 25.65%. For “[B] three equal” the exact probability is 0.95%. These are exact, combinatorial counts and they sum to 1.

Practical takeaways: ties are common (about 27% of rounds), so omitting equality handling risks incorrect behavior. A much simpler approach than nested messy conditionals is to compute a small frequency table (counts and the list of queue indices per value), then inspect counts[maxValue] and counts[minValue] and apply a deterministic or random tie-breaker.

Example tie-handling sketch (Python-style):

v = [a,b,c,d]          # numbers just removed
from collections import defaultdict
idx = defaultdict(list)
for i,val in enumerate(v):
    idx[val].append(i)
maxv = max(v); minv = min(v)
# if multiple queues share maxv or minv, pick idx from idx[maxv] / idx[minv]

As noted, this is a discrete-probability calculation; 's warning about ignoring small probabilities is apt here because the tie probability is not small.

Recommended Answers

All 2 Replies

Member Avatar for Ancient Dragon

what you need to solve that problem is to study is probability theory, not computer science. Pay attention to the section Discrete probability distributions

Member Avatar for TrustyTony

Your words about not paying attention to too small probability sounds like famous last words of programmer ;) :(

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.