card_sorting_basics v1.0.0

name: card_sorting_basics description: "Plan, run, and analyze card sorts to design or test information architecture: choose open, closed, or hybrid, design the cards and categories, recruit and brief participants, and turn similarity matrices and dendrograms into a navigation and label decision. Use when a site or app structure, menu, or category set needs evidence from how participants group content." metadata: { "includeInPrompt": true }

Card Sorting Basics

Purpose

Run a card sort that ends in a decision: a proposed navigation structure, category names for it, and a placement for every card, with the evidence for each placement kept on record. Participants group content cards in the way that makes sense to them, and the pattern across participants shows which groupings are shared, which are contested, and which labels participants reach for on their own.

Scope:

• usability-testing-basics is goal-based task testing with think-aloud: participants attempt set tasks in a built or mocked interface, and the finding is whether they can complete the task. This skill runs earlier or alongside that work and asks a different question: how participants group and name content when no interface guides them. A card sort gives no task success rate and proves nothing about whether a finished navigation can be used.
• heuristic-evaluation is an expert review with no participants: a small set of reviewers score an interface against a fixed heuristic list. This skill collects grouping data from participants instead, and its evidence is counts of how those participants sorted, not reviewer judgment.
• interview-transcript-analysis is coding transcripts after interviews: it builds a codebook and applies it to recorded talk. This skill analyzes sort data (which cards landed together, which category a card landed in, what a group was named). Interview notes from a sort debrief can be useful context, but coding them belongs to that skill.
• This skill does not cover building the navigation, writing the page content for the cards, or testing a finished tree of pages. It ends at a documented structure and label decision that other work can build and then test.
• Tool claims in this skill were checked on 2026-10-15. The analysis script in the Operating Rules section uses only the Python standard library and was run under Python 3.12.3 against its built-in fixture; every number quoted in this skill comes from that run. No vendor sorting tool is named with feature claims, because tools differ in what they export: any tool that exports, per participant, which cards were grouped together (open sort) or which category each card was placed in (closed sort) can supply the input this skill needs. Confirm the export shape before recruiting, not after the sessions close.

Workflow

1. Frame the decision before designing anything.

• Write down the decision the sort must support, in one sentence: for example, design a top-level navigation for a shop section, test whether a proposed help structure matches how participants group help topics, or settle where a set of new pages belongs in an existing structure.
• Write down what happens with each possible outcome. If a result in favor of the current structure and a result against it would both lead to the same build, the sort answers nothing and should not run.
• Record the audience for the structure. A sort run on participants who never use the content produces tidy clusters that describe the wrong mental model. The screening rules in step 5 come from this audience definition.
• Decide the unit of analysis: the whole structure, or one contested section. A sort that tries to settle an entire site and three disputed sections at once usually settles none of them, because the card set grows past what a participant can hold in mind (step 3).

1. Choose the sort type: open, closed, or hybrid.

• Open sort: participants group the cards freely and name each group themselves. Use it to design a structure, when the categories themselves are in question, or when the labels for categories are in question. The output is groupings plus participant-supplied names.
• Closed sort: participants place each card into a fixed set of categories supplied in advance. Use it to test a proposed structure: the finding is how often each card lands in its intended category and where the misses go. The output is a placement count per card per category.
• Hybrid sort: participants place cards into supplied categories and may also create their own categories. Use it when most of a structure is settled and a few areas are open, or when a closed test should still catch a missing category. Treat cards placed in participant-created categories as open-sort data in the analysis.
• Pick one type per study and record why. Running an open sort and then judging the results against a preferred structure after the fact turns design evidence into a rigged test; if the structure needs testing, run a closed sort as a separate study.
• Match the type to the analysis you can actually do. An open sort needs similarity and cluster analysis (steps 9 and 10). A closed sort needs per-card placement counts and a review of misses (step 9). A study with no analysis time allotted should be smaller, not vaguer.

1. Build the card set.

• One card per concept. A card names a single page, topic, product type, or task destination. A card that names two concepts ("Returns and refunds") forces participants to sort a pair they might split, and the result cannot show which half drove the placement.
• Use participant language on the cards, taken from search terms, support questions, existing page titles that participants already see, or prior interview wording. Internal product names, team names, and jargon belong on a card only if participants meet those words in the real product.
• Keep card wording parallel: same level of detail, same style of phrase, no card longer or more specific than the rest by accident. A long, detailed card reads as more important and attracts grouping attention for the wrong reason.
• Put no category hints on the cards. If three cards begin with the same word because their source pages did, check whether that shared word is a real signal participants should use or an artifact of internal naming; if it is an artifact, reword.
• Size the set for one sitting. As a planning target, choose a set a pilot participant can finish without rushing, and cut cards before you cut participants: drop cards whose placement is already settled by other evidence, merge true duplicates, and move a second contested section to a second study. Record the final card count and every cut made after the pilot.
• Randomize or rotate card order per participant when the tool allows it. A fixed order lets the first cards anchor the first groups.
• Freeze the card list before recruiting. Changing a card mid-study splits the data into two studies with different card sets, and the counts no longer share a denominator.

1. Design the categories for a closed or hybrid sort.

• Write each category as a name plus a one-line description of what belongs in it. Test the descriptions, not just the names: two categories with clear names and overlapping descriptions will split cards between them for reasons the counts alone cannot explain.
• Cover the card set. Walk every card against the category list before the pilot and confirm each card has at least one defensible home. A card with no defensible home measures a gap in the structure, which is a finding, but it should be a deliberate test card, not an accident.
• Keep category count close to the structure being tested. Adding extra decoy categories, or collapsing two real sections into one category to make the test easier, changes the question being asked.
• Decide the escape options in advance and record them: a "Not sure" category, an "Other" category, or neither. An escape category absorbs hard cards and lowers every placement count, so its size is part of the result. In a hybrid sort, participant-created categories serve this role and also supply label evidence.
• Use the exact labels the build would ship. Testing friendly paraphrases of awkward real labels produces a pass the real structure will not repeat.

1. Plan participants, screening, and the pilot.

• Recruit from the audience defined in step 1, screened on behavior that matters for the content: for example, has bought from the shop, has used the help section, manages an account. Demographic screening alone rarely predicts how someone groups specialist content.
• Set a target completed-sort count before recruiting and treat it as a planning target, not a precision claim. Working targets that suit most site and app studies: 15 to 20 completed sorts for an open sort, and 20 to 30 completed sorts for a closed sort, with more when two distinct audience segments must be read separately. The reason for the target is denominator stability: every pair percentage in step 9 is a count over the number of participants, so at small counts a single participant moves a pair a long way. The worked fixture in the Operating Rules section uses 6 participants so the arithmetic can be checked by hand; treat it as a teaching example, not a decision-grade sample.
• Recruit per segment when segments plausibly group differently (first-time buyers against account holders, for example) and plan to read their matrices separately before combining them. A combined matrix can hide two clear, different structures inside one muddy average.
• Pilot with 2 or 3 participants from the target audience. Time the sort, watch for cards nobody understands, cards read two ways, and category descriptions that collide. Fix wording problems after the pilot, freeze the materials, and exclude pilot data from the final counts unless the materials did not change at all.
• Decide moderated or unmoderated and record it. Moderated sessions (in person or by call) allow a debrief on the hard cards and suit small open sorts. Unmoderated remote sessions suit larger closed sorts and give cleaner counts, but no reasons for a placement unless a follow-up question per card or per group is included in the session design.

1. Write the session protocol.

• Open with a fixed instruction script, read or shown word for word to every participant. It covers: what the cards are, that groups should reflect what makes sense to them, that there is no correct grouping, that every card goes in exactly one group (for an open or hybrid sort, groups they create; for a closed sort, one supplied category), and that a card they cannot place should be flagged rather than forced.
• For an open sort, add: make as many or as few groups as the content needs, a group can hold one card, and name each group with a label that describes its contents. Group names are data, so ask for them during the sort, not from memory afterward.
• For a closed sort, add: use the category descriptions when a name is ambiguous, and use the escape option (step 4) instead of guessing when no category fits.
• Include one practice item or a worked example that uses unrelated content, so the mechanics are learned on material that is not part of the study.
• Set the closing questions in advance. Useful ones: which cards were hardest to place and why, which group or category name was hardest to choose, and whether a group they wanted was missing. Record answers against the participant's sort, not as free-floating quotes.
• Close by checking completeness: every card placed exactly once, every open group named. An incomplete sort discovered during analysis has no clean fix, because the missing placements are not random.

1. Run the sessions and watch data quality while the study is open.

• Check the first few completed sorts the day they arrive: completion, time taken, group counts, and escape-category use. A defect in the materials found at sort three can still be studied around; the same defect found after the study closes cannot.
• Flag low-effort sorts by rules written before looking at results: for example, all cards in one group in an open sort, a completion time far below the pilot range, or the escape category holding a large share of one participant's cards. Flagging is a record, not an automatic deletion; step 8 decides exclusions and reports them.
• Do not coach placements. In a moderated session, answer questions about mechanics and about what a card means with a pre-written clarification if one exists; otherwise note the question as a card-wording finding and let the participant decide.
• Keep the raw export untouched. Save it as delivered, with the study date, sort type, card set version, and participant count, before any cleaning begins.

1. Clean the data and standardize open-sort group names.

• Apply the exclusion rules from step 7 and log every excluded sort with its reason. Report final counts after exclusions as the denominators for every percentage that follows.
• For open and hybrid sorts, standardize group names before counting label evidence: group together names that plainly mean the same grouping (for example, spelling variants and singular and plural forms), and keep a standardization log with the raw name, the standardized name, and the participant count behind each merge.
• Do not standardize by intent you cannot see. Two similar names over different card sets are different groups; the cards in the group decide what the group is, and the name is evidence about its label, not the definition of it.
• Keep singletons visible. A group holding one card, and a card that many participants isolate, are findings about that card (often a distinct concept or a label problem), not noise to be merged away.
• For closed sorts, there is nothing to standardize, but do log any participant-created categories in a hybrid sort the same way as open groups.

1. Analyze placement and similarity.

• Closed and hybrid sorts: build the placement table, cards as rows and categories as columns, with the count of participants who placed each card in each category. Read each card by its largest count (its modal category), the share of participants behind that count, and where the rest went. A card split evenly between two categories is a contested card: the structure, the label, or the card wording needs a decision in step 11, and the split itself is the evidence.
• Open and hybrid sorts: build the similarity matrix. For each pair of cards, similarity is the number of participants who placed both cards in the same group, divided by the number of participants, stated as a percentage. The script in the Operating Rules section computes this, plus the ranked pair list and each card's strongest partner. Read the matrix three ways:
• Strong pairs and cores: pairs at or near 100 percent are groupings the audience treats as settled. In the fixture, Account Settings with Password Reset, and the three pairs among Product Catalog, Shopping Cart, and Wishlist, sit at 100.0 percent.
• Contested cards: a card whose strongest partner is well below the settled pairs, or whose top partners point into different groups, has no agreed home. In the fixture, Billing History peaks at 66.7 percent with Order Tracking and also sits at 33.3 percent with each of Account Settings, Password Reset, and Delivery Options, which marks it as the contested card.
• Absences: pairs at 0.0 percent show groupings nobody made. The fixture has 16 such pairs out of 28, against 4 pairs placed together by every participant. Absences matter when a proposed structure would force two never-grouped cards together.
• Read per-segment matrices before the combined one when the study recruited segments (step 5). Report any grouping a segment holds strongly that the combined matrix dilutes.
• State every percentage with its denominator, as a count over participants (for example, 4 of 6). Percentages from small samples look more settled than they are, and the count keeps the reader honest about the weight of the evidence.

1. Read the dendrogram and choose a cluster solution.

• A dendrogram draws the merges from a cluster analysis of the similarity matrix. The script in the Operating Rules section performs average-linkage clustering: distance between two clusters is 1 minus the mean similarity of every card pair spanning the two clusters, the closest clusters merge first, and each merge is printed with its distance.
• Read merges from low distance to high. Low-distance merges are groupings participants made consistently. High-distance merges are arithmetic completing the tree, joining clusters participants kept apart; the last merges in any dendrogram carry the least evidence and should never be quoted as found groups.
• Choose the solution at a gap. Look for a distance range where no merges happen: clusters below the gap formed cheaply, merges above it are forced. In the fixture, merges run at 0.0000, 0.3333, and 0.5000, then jump to 0.8889 and 0.9333, so cutting at 0.50 leaves three clusters: Account Settings and Password Reset; Billing History, Delivery Options, and Order Tracking; and Product Catalog, Shopping Cart, and Wishlist.
• Do not adopt the cut clusters as the structure on their own. Check each cluster against the raw pair counts (step 9), the standardized group names (step 8), and the contested cards. A cluster built around a contested card inherits that contest: the fixture's orders cluster holds together through Order Tracking, while Billing History and Delivery Options each join it at 66.7 percent with a different partner pattern, which is a weaker claim than the 100.0 percent shopping core.
• Try a second linkage or a second cut when a decision rests on one cluster, and report whether the contested cards move. A grouping that survives a different reading is safe to build on; a grouping that exists only under one cut belongs in the limits section of the report.
• Name the clusters from participant group names collected in the sessions (step 8 log), ordered by how many participants used each standardized name. Analyst-invented names are allowed only when no participant name covers the cluster, and the report must say so.

1. Turn the results into a structure and label decision.

• Draft the proposed structure from the chosen cluster solution for an open sort, or from the placement table for a closed sort. Every card from the study appears in the proposal exactly once at this stage, including contested cards, each with a marked decision.
• For each contested card, pick one action and record the reason:
• Place it in its modal group or category and accept the minority reading.
• Place it in one home and cross-link it from the other group or category that claimed it, when the product supports cross-links.
• Split the card into two cards when participants were plainly sorting two concepts (a card-wording finding from the sessions), and note that the split needs its own follow-up check.
• Rename the card or the destination label when the placements show participants understood the content but not the wording.
• Move it to the other claimant when the qualitative reasons from the closing questions outweigh a small count difference.
• Choose category labels from the standardized participant names first. Where the build must use an existing label that participants did not use, record the gap: the label is untested by this study even if the grouping under it is supported.
• Record decisions the evidence does not support as open questions, with the follow-up that would settle them (usually a closed sort on the revised structure, or task testing under usability-testing-basics once a version is built). A card sort report that resolves every dispute on thin counts is overstating its data.
• Stop when every card has a placement, every category has a label with a source, and every contested card has a named action. That complete decision table is the deliverable, not the matrix alone.

Output Contract

Deliver a card sort report with these sections, in this order:

1. Study brief: the decision the sort supported (Workflow step 1), the sort type chosen and why, the audience and screening rules, the target and final participant counts, and whether sessions were moderated.
2. Materials record: the exact card list as run, the exact category list and descriptions for a closed or hybrid sort, the escape options offered, the instruction script, and every change made after the pilot.
3. Data record: raw export saved untouched, exclusions applied with reasons, final denominator for every count, and for open or hybrid sorts the group-name standardization log (raw name, standardized name, participant count).
4. Analysis output: the full output of sort_analysis.py on the study data for an open or hybrid sort, or the full placement table for a closed sort. On the worked fixture in the Operating Rules section the headline numbers are: participants 6, cards 8, pairs 28, pairs together always 4, pairs together never 16, merges at distances 0.0000, 0.3333, 0.5000, 0.8889, and 0.9333, and three clusters at the 0.50 cut (Account Settings with Password Reset; Billing History with Delivery Options and Order Tracking; Product Catalog with Shopping Cart and Wishlist).
5. Findings: one entry per cluster or category with its supporting pair percentages or placement counts stated as counts over participants, the strongest pairs inside it, and its contested cards with their splits.
6. Decision table: one row per card with its decided placement, the label where it lands, the evidence behind the placement (pair percentages, placement counts, or participant group names), and the action taken for contested cards from Workflow step 11.
7. Labels record: each category label in the proposal, whether it came from participant group names (with counts from the standardization log) or from the existing product vocabulary, and any label the study did not test.
8. Limits and follow-ups: segments read separately or not at all, clusters that changed under a second cut or linkage, disputes left open, and the follow-up study that would settle each one.

Operating Rules

1. Raw data stays raw. The export as delivered is saved before cleaning, exclusions and standardizations are applied to a copy, and every applied change is logged with its reason. An analysis nobody can trace back to the raw sorts is not evidence.
2. Every card exactly once per participant. An open sort group, a closed sort category, and a hybrid placement all follow the same rule: each card appears in exactly one group or category in each completed sort. sort_analysis.py enforces this on its input and rejects a participant whose cards do not match the card set exactly once.
3. Counts before percentages. Every similarity or placement figure is reported as a count over the participant denominator first, with the percentage after it. A percentage quoted without its denominator is a defect in the report.
4. No silent label merges. Standardized group names come only from the standardization log, similar names over different card sets stay separate, and the log ships with the report.
5. The dendrogram cut is a decision, not a finding. Report the cut used, the merge distances either side of it, and what changes at the nearest other plausible cut. Clusters above a large distance gap are not described as groups participants made.
6. Contested cards get named actions. Every card split between groups or categories gets one of the actions in Workflow step 11, with a reason. Leaving a contested card placed by default, without a row in the decision table, fails the output contract.
7. Do not mix study types after the fact. Open sort results are not scored against a preferred structure, and closed sort misses are not explained away by relabeling categories in the analysis. If the question changes, run the matching sort as its own study.
8. Quote numbers only from the analysis output. Pair percentages, merge distances, cluster membership, and placement counts come from sort_analysis.py output or the placement table, never from memory of browsing the raw data. If a number is not in the output, extend the script and rerun it rather than estimating.
9. Use the analysis script below for open and hybrid sort similarity and clustering. Save it as sort_analysis.py, run it on the fixture to confirm your copy works, then replace the FIXTURE data with the study data in the same shape (a list of participants, each a list of groups, each group a list of card names) and rerun it. Report numbers from its output, not from memory of the sorts.

Card sort analysis (sort_analysis.py)

Run: python3 sort_analysis.py prints the full analysis of the built-in fixture. Run: python3 sort_analysis.py --self-test prints the same analysis, checks the headline counts, confirms that a malformed participant is rejected, and ends with self_test: PASS (bad fixture rejected).

Expected output for the fixture run:

text
participants: 6
cards: 8
pairs: 28
similarity_matrix_pct:
  Account Settings | Billing History | Delivery Options | Order Tracking | Password Reset | Product Catalog | Shopping Cart | Wishlist
  Account Settings: - | 33.3 | 0.0 | 0.0 | 100.0 | 0.0 | 0.0 | 0.0
  Billing History: 33.3 | - | 33.3 | 66.7 | 33.3 | 0.0 | 0.0 | 0.0
  Delivery Options: 0.0 | 33.3 | - | 66.7 | 0.0 | 33.3 | 33.3 | 33.3
  Order Tracking: 0.0 | 66.7 | 66.7 | - | 0.0 | 0.0 | 0.0 | 0.0
  Password Reset: 100.0 | 33.3 | 0.0 | 0.0 | - | 0.0 | 0.0 | 0.0
  Product Catalog: 0.0 | 0.0 | 33.3 | 0.0 | 0.0 | - | 100.0 | 100.0
  Shopping Cart: 0.0 | 0.0 | 33.3 | 0.0 | 0.0 | 100.0 | - | 100.0
  Wishlist: 0.0 | 0.0 | 33.3 | 0.0 | 0.0 | 100.0 | 100.0 | -
pairs_ranked:
  Account Settings + Password Reset: 6/6 = 100.0%
  Product Catalog + Shopping Cart: 6/6 = 100.0%
  Product Catalog + Wishlist: 6/6 = 100.0%
  Shopping Cart + Wishlist: 6/6 = 100.0%
  Billing History + Order Tracking: 4/6 = 66.7%
  Delivery Options + Order Tracking: 4/6 = 66.7%
  Account Settings + Billing History: 2/6 = 33.3%
  Billing History + Delivery Options: 2/6 = 33.3%
  Billing History + Password Reset: 2/6 = 33.3%
  Delivery Options + Product Catalog: 2/6 = 33.3%
  Delivery Options + Shopping Cart: 2/6 = 33.3%
  Delivery Options + Wishlist: 2/6 = 33.3%
  Account Settings + Delivery Options: 0/6 = 0.0%
  Account Settings + Order Tracking: 0/6 = 0.0%
  Account Settings + Product Catalog: 0/6 = 0.0%
  Account Settings + Shopping Cart: 0/6 = 0.0%
  Account Settings + Wishlist: 0/6 = 0.0%
  Billing History + Product Catalog: 0/6 = 0.0%
  Billing History + Shopping Cart: 0/6 = 0.0%
  Billing History + Wishlist: 0/6 = 0.0%
  Delivery Options + Password Reset: 0/6 = 0.0%
  Order Tracking + Password Reset: 0/6 = 0.0%
  Order Tracking + Product Catalog: 0/6 = 0.0%
  Order Tracking + Shopping Cart: 0/6 = 0.0%
  Order Tracking + Wishlist: 0/6 = 0.0%
  Password Reset + Product Catalog: 0/6 = 0.0%
  Password Reset + Shopping Cart: 0/6 = 0.0%
  Password Reset + Wishlist: 0/6 = 0.0%
strongest_partner_per_card:
  Account Settings: Password Reset 6/6 = 100.0% (next: Billing History 2/6 = 33.3%)
  Billing History: Order Tracking 4/6 = 66.7% (next: Account Settings 2/6 = 33.3%)
  Delivery Options: Order Tracking 4/6 = 66.7% (next: Billing History 2/6 = 33.3%)
  Order Tracking: Billing History 4/6 = 66.7% (next: Delivery Options 4/6 = 66.7%)
  Password Reset: Account Settings 6/6 = 100.0% (next: Billing History 2/6 = 33.3%)
  Product Catalog: Shopping Cart 6/6 = 100.0% (next: Wishlist 6/6 = 100.0%)
  Shopping Cart: Product Catalog 6/6 = 100.0% (next: Wishlist 6/6 = 100.0%)
  Wishlist: Product Catalog 6/6 = 100.0% (next: Shopping Cart 6/6 = 100.0%)
pairs_together_always: 4
pairs_together_never: 16
merge_steps_average_linkage:
  step 1: Account Settings + Password Reset at distance 0.0000
  step 2: Product Catalog + Shopping Cart at distance 0.0000
  step 3: Product Catalog + Shopping Cart + Wishlist at distance 0.0000
  step 4: Billing History + Order Tracking at distance 0.3333
  step 5: Billing History + Delivery Options + Order Tracking at distance 0.5000
  step 6: Account Settings + Billing History + Delivery Options + Order Tracking + Password Reset at distance 0.8889
  step 7: Account Settings + Billing History + Delivery Options + Order Tracking + Password Reset + Product Catalog + Shopping Cart + Wishlist at distance 0.9333
clusters_at_distance_cut_0.50:
  cluster: Account Settings + Password Reset
  cluster: Billing History + Delivery Options + Order Tracking
  cluster: Product Catalog + Shopping Cart + Wishlist

The fixture is a teaching example with 6 participants and 8 cards, built so every reading in Workflow steps 9 and 10 has a case: a settled account pair (Account Settings and Password Reset at 100.0 percent), a settled shopping core (Product Catalog, Shopping Cart, and Wishlist, each pair at 100.0 percent), a looser orders cluster held together by Order Tracking (66.7 percent with each of Billing History and Delivery Options, while Billing History and Delivery Options pair at 33.3 percent), and one contested card (Billing History, which also pairs at 33.3 percent with each account card). The final two merges, at 0.8889 and 0.9333, are the forced joins step 10 warns against quoting as found groups.

sort_analysis.py (Python 3, standard library only). Save this code as sort_analysis.py:

python
#!/usr/bin/env python3
"""Analyze an open card sort: pair similarity, strongest partners, clusters.

Uses only the Python standard library. No external data file is needed:
the worked fixture is built in below, and analyze() accepts the same
shape for real data (a list of participants, each a list of groups,
each group a list of card names). Every card must appear exactly once
per participant.

Run:
  python3 sort_analysis.py
  python3 sort_analysis.py --self-test

What it reports: participant and card counts, the full pair similarity
matrix as percentages, pairs ranked by similarity, each card's
strongest partner, average-linkage merge steps (distance = 1 minus mean
pair similarity between clusters), and the clusters left at a 0.50
distance cut.
"""
import sys
from itertools import combinations

CARDS = [
    "Account Settings",
    "Billing History",
    "Delivery Options",
    "Order Tracking",
    "Password Reset",
    "Product Catalog",
    "Shopping Cart",
    "Wishlist",
]

# Each participant: a list of groups, each group a list of card names.
FIXTURE = [
    [["Account Settings", "Password Reset", "Billing History"],
     ["Product Catalog", "Shopping Cart", "Wishlist"],
     ["Order Tracking", "Delivery Options"]],
    [["Account Settings", "Password Reset"],
     ["Product Catalog", "Shopping Cart", "Wishlist", "Delivery Options"],
     ["Billing History", "Order Tracking"]],
    [["Account Settings", "Password Reset"],
     ["Product Catalog", "Shopping Cart", "Wishlist"],
     ["Billing History", "Order Tracking", "Delivery Options"]],
    [["Account Settings", "Password Reset", "Billing History"],
     ["Product Catalog", "Shopping Cart", "Wishlist"],
     ["Order Tracking", "Delivery Options"]],
    [["Account Settings", "Password Reset"],
     ["Product Catalog", "Shopping Cart", "Wishlist"],
     ["Billing History", "Order Tracking", "Delivery Options"]],
    [["Account Settings", "Password Reset"],
     ["Product Catalog", "Shopping Cart", "Wishlist", "Delivery Options"],
     ["Billing History", "Order Tracking"]],
]


def validate(participants, cards):
    want = sorted(cards)
    for i, groups in enumerate(participants, start=1):
        seen = sorted(card for group in groups for card in group)
        if seen != want:
            raise ValueError(
                f"participant {i}: cards do not match the card set exactly once"
            )


def pair_counts(participants, cards):
    counts = {pair: 0 for pair in combinations(sorted(cards), 2)}
    for groups in participants:
        for group in groups:
            for pair in combinations(sorted(group), 2):
                counts[pair] += 1
    return counts


def cluster_distance(cluster_a, cluster_b, sim):
    vals = []
    for a in cluster_a:
        for b in cluster_b:
            key = tuple(sorted((a, b)))
            vals.append(sim[key])
    return 1.0 - (sum(vals) / len(vals))


def merge_steps(cards, sim):
    clusters = [[c] for c in sorted(cards)]
    steps = []
    while len(clusters) > 1:
        best = None
        for a, b in combinations(range(len(clusters)), 2):
            d = cluster_distance(clusters[a], clusters[b], sim)
            label = (tuple(clusters[a]), tuple(clusters[b]))
            key = (round(d, 10), label)
            if best is None or key < best[0]:
                best = (key, a, b, d)
        _, a, b, d = best
        merged = sorted(clusters[a] + clusters[b])
        steps.append((merged, d))
        clusters = [c for i, c in enumerate(clusters) if i not in (a, b)]
        clusters.append(merged)
        clusters.sort()
    return steps


def clusters_at_cut(cards, sim, cut):
    clusters = [[c] for c in sorted(cards)]
    while len(clusters) > 1:
        best = None
        for a, b in combinations(range(len(clusters)), 2):
            d = cluster_distance(clusters[a], clusters[b], sim)
            label = (tuple(clusters[a]), tuple(clusters[b]))
            key = (round(d, 10), label)
            if best is None or key < best[0]:
                best = (key, a, b, d)
        _, a, b, d = best
        if d > cut:
            break
        merged = sorted(clusters[a] + clusters[b])
        clusters = [c for i, c in enumerate(clusters) if i not in (a, b)]
        clusters.append(merged)
        clusters.sort()
    return clusters


def analyze(participants, cards):
    validate(participants, cards)
    n = len(participants)
    counts = pair_counts(participants, cards)
    sim = {pair: count / n for pair, count in counts.items()}
    ordered = sorted(cards)
    print(f"participants: {n}")
    print(f"cards: {len(cards)}")
    print(f"pairs: {len(counts)}")
    print("similarity_matrix_pct:")
    print("  " + " | ".join(ordered))
    for card in ordered:
        cells = []
        for other in ordered:
            if card == other:
                cells.append("-")
            else:
                key = tuple(sorted((card, other)))
                cells.append(f"{sim[key] * 100:.1f}")
        print(f"  {card}: " + " | ".join(cells))
    ranked = sorted(counts.items(), key=lambda kv: (-kv[1], kv[0]))
    print("pairs_ranked:")
    for (a, b), count in ranked:
        print(f"  {a} + {b}: {count}/{n} = {count / n * 100:.1f}%")
    print("strongest_partner_per_card:")
    for card in ordered:
        partners = []
        for other in ordered:
            if other != card:
                key = tuple(sorted((card, other)))
                partners.append((counts[key], other))
        partners.sort(key=lambda t: (-t[0], t[1]))
        top_count, top_name = partners[0]
        second_count, second_name = partners[1]
        print(
            f"  {card}: {top_name} {top_count}/{n} = {top_count / n * 100:.1f}%"
            f" (next: {second_name} {second_count}/{n} = {second_count / n * 100:.1f}%)"
        )
    together_always = sum(1 for c in counts.values() if c == n)
    together_never = sum(1 for c in counts.values() if c == 0)
    print(f"pairs_together_always: {together_always}")
    print(f"pairs_together_never: {together_never}")
    print("merge_steps_average_linkage:")
    for i, (merged, d) in enumerate(merge_steps(cards, sim), start=1):
        print(f"  step {i}: {' + '.join(merged)} at distance {d:.4f}")
    cut = 0.50
    print(f"clusters_at_distance_cut_{cut:.2f}:")
    for cluster in clusters_at_cut(cards, sim, cut):
        print(f"  cluster: {' + '.join(cluster)}")
    return {
        "participants": n,
        "cards": len(cards),
        "pairs": len(counts),
        "together_always": together_always,
        "together_never": together_never,
    }


def self_test():
    result = analyze(FIXTURE, CARDS)
    assert result == {
        "participants": 6,
        "cards": 8,
        "pairs": 28,
        "together_always": 4,
        "together_never": 16,
    }, result
    bad = [[["Account Settings"]]]
    try:
        validate(bad, CARDS)
    except ValueError:
        print("self_test: PASS (bad fixture rejected)")
        return 0
    print("self_test: FAIL (bad fixture accepted)")
    return 1


def main():
    args = sys.argv[1:]
    if "--self-test" in args:
        return self_test()
    analyze(FIXTURE, CARDS)
    return 0


if __name__ == "__main__":
    raise SystemExit(main())