Ready to begin
No records have been processed. Start with Next step.
SECTION 08 / 31
Use seen to avoid reversed pairs without marking cards
REAL COURSE DATA · KEYS, COUNTS AND CONNECTIONS
Mark seen and compare each unordered pair once
Follow the dictionary as its keys and values change. Predict each lookup or update before revealing the next step.
Ready
What we remember
- Processed
- 0
Predict the next key, whether it already exists, and the value that will be stored.
seen = {}
foreach A in scores {
seen[A.CardNo] = True
foreach B in scores {
if (not isKey(seen,B.CardNo)) {
if (A.Mathematics == B.Mathematics) {
# record [A.CardNo,B.CardNo]
}
}
}
}Mark the OUTER card before checking inner cards. The mark excludes the card itself and all earlier outer cards. A later inner card remains unmarked until it becomes an outer card. Marking every inner candidate would wrongly remove future pairs. Start a fresh seen dictionary for a new task.
For three cards A,B,C, the accepted comparisons are A–B, A–C and B–C. A–A and reversed B–A are skipped. For 30 students there are 435 accepted mark comparisons. This particular two-full-loop algorithm still performs 900 membership checks. It organizes pairs but does not remove the nested loops.
Try it yourself
Why mark A before the inner loop?
Show explained answer
To skip A itself and every previously processed outer card.
Try it yourself
Should we mark B just because it was an inner candidate?
Show explained answer
No. That would wrongly prevent later comparisons involving B.
Try it yourself
Does a seen dictionary make this pair algorithm one-pass linear time?
Show explained answer
No. It still scans all inner cards for each outer card; the accepted unordered comparisons number n(n−1)/2.