Find Symmetric Pairs In An Array In C Program

Identifying symmetric pairs within a collection of data is a common task in computer science, particularly when dealing with relationships or network configurations. A symmetric pair (a, b) implies that its reverse, (b, a), also exists within the same dataset. This article will guide you through various methods to efficiently find and extract these pairs using C programming.

Problem Statement

Given a set of pairs, such as (1, 2), (3, 4), (5, 2), (2, 1), (4, 3), (6, 7), the objective is to identify all pairs (a, b) for which (b, a) is also present in the set. For instance, in the example above, (1, 2) and (2, 1) form a symmetric pair, as do (3, 4) and (4, 3). The challenge lies in developing an algorithm that can find these pairs accurately and with reasonable performance.

Example

Let's consider the input [(1, 2), (3, 4), (5, 2), (2, 1), (4, 3), (6, 7)]. The expected output for symmetric pairs would be:

Symmetric Pairs:
(1, 2) and (2, 1)
(3, 4) and (4, 3)

Background & Knowledge Prerequisites

To effectively follow the solutions presented, you should have a basic understanding of:

• C Language Fundamentals: Variables, data types, loops (for), conditional statements (if).
• Structures in C: Defining and using struct to group related data elements.
• Arrays in C: Declaring and manipulating arrays of primitive types and structures.
• Boolean Type (stdbool.h): Using true and false for logical conditions.

Use Cases or Case Studies

Finding symmetric pairs has applications across various domains:

• Network Topology: In a network where connections are represented as pairs, symmetric pairs indicate bidirectional links (e.g., if a connection exists from A to B, and B to A).
• Social Network Analysis: Identifying mutual friendships or reciprocal relationships where if user A follows user B, user B also follows user A.
• Database Relationships: Detecting symmetric relationships in a database, such as "is a sibling of" or "is married to," where the relationship holds true in both directions.
• Physics Simulations: Analyzing forces or interactions between two objects that are reciprocal (Newton's third law).
• Game Development: Matching game entities or properties that have a two-way connection, like trading routes between two cities.

Solution Approaches

We will explore two distinct approaches to solve this problem: a straightforward brute-force method and an optimized approach that uses flags to avoid redundant computations.

Approach 1: Brute-Force Method using Nested Loops

This approach involves comparing every pair with every other pair to find a symmetric match. It's simple to understand and implement but can be inefficient for very large datasets.

• One-line summary: Iterates through all possible unique pairs of pairs to identify symmetric counterparts.

// Find Symmetric Pairs (Brute-Force)
#include <stdio.h>

// Structure to represent a pair of integers
struct Pair {
    int first;
    int second;
};

int main() {
    // Step 1: Define the array of pairs
    struct Pair pairs[] = {{1, 2}, {3, 4}, {5, 2}, {2, 1}, {4, 3}, {6, 7}};
    int n = sizeof(pairs) / sizeof(pairs[0]);

    printf("Original Pairs:\\n");
    for (int i = 0; i < n; i++) {
        printf("(%d, %d) ", pairs[i].first, pairs[i].second);
    }
    printf("\\n\\n");

    printf("Symmetric Pairs:\\n");
    // Step 2: Iterate through each pair using the outer loop
    for (int i = 0; i < n; i++) {
        // Step 3: Iterate through subsequent pairs using the inner loop
        // Starting j from i + 1 avoids checking a pair with itself and duplicate checks
        for (int j = i + 1; j < n; j++) {
            // Step 4: Check if pairs[j] is the symmetric counterpart of pairs[i]
            if (pairs[i].first == pairs[j].second && pairs[i].second == pairs[j].first) {
                printf("(%d, %d) and (%d, %d)\\n", pairs[i].first, pairs[i].second, pairs[j].first, pairs[j].second);
            }
        }
    }

    return 0;
}

Run

• Sample Output:

Original Pairs:
    (1, 2) (3, 4) (5, 2) (2, 1) (4, 3) (6, 7)

    Symmetric Pairs:
    (1, 2) and (2, 1)
    (3, 4) and (4, 3)

• Stepwise explanation:

1. A struct Pair is defined to hold two integer values representing a pair.
2. An array of struct Pair is initialized with the given input data.
3. The outer for loop iterates through each pair from the beginning of the array.
4. The inner for loop iterates through the pairs that come after the current outer loop's pair (j = i + 1). This prevents comparing a pair with itself and ensures each unique pair of pairs is checked only once.
5. Inside the inner loop, a condition checks if the first element of pairs[i] matches the second element of pairs[j], AND if the second element of pairs[i] matches the first element of pairs[j].
6. If both conditions are true, pairs[i] and pairs[j] form a symmetric pair, and they are printed to the console.

Approach 2: Using an Auxiliary Array (Printed Flags)

This optimized approach also uses nested loops but introduces a boolean flag array to mark pairs that have already been identified as part of a symmetric set. This avoids re-processing and printing the same symmetric pair multiple times.

• One-line summary: Uses a boolean array to track and skip pairs that have already been identified and printed as part of a symmetric pair.

// Find Symmetric Pairs (Optimized with Printed Flags)
#include <stdio.h>
#include <stdbool.h> // Required for boolean type

// Structure to represent a pair of integers
struct Pair {
    int first;
    int second;
};

int main() {
    // Step 1: Define the array of pairs
    struct Pair pairs[] = {{1, 2}, {3, 4}, {5, 2}, {2, 1}, {4, 3}, {6, 7}, {7, 6}};
    int n = sizeof(pairs) / sizeof(pairs[0]);

    // Step 2: Create a boolean array to track if a pair has been printed
    bool was_printed[n];
    for (int i = 0; i < n; i++) {
        was_printed[i] = false; // Initialize all flags to false
    }

    printf("Original Pairs:\\n");
    for (int i = 0; i < n; i++) {
        printf("(%d, %d) ", pairs[i].first, pairs[i].second);
    }
    printf("\\n\\n");

    printf("Symmetric Pairs:\\n");
    // Step 3: Iterate through each pair using the outer loop
    for (int i = 0; i < n; i++) {
        // Step 4: Check if the current pair has already been marked as part of a symmetric pair
        if (!was_printed[i]) {
            // Step 5: Look for its symmetric counterpart in the subsequent pairs
            for (int j = i + 1; j < n; j++) {
                // Step 6: If pairs[j] is the symmetric counterpart AND it hasn't been printed yet
                if (!was_printed[j] &&
                    pairs[i].first == pairs[j].second &&
                    pairs[i].second == pairs[j].first) {

                    printf("(%d, %d) and (%d, %d)\\n", pairs[i].first, pairs[i].second, pairs[j].first, pairs[j].second);
                    was_printed[i] = true; // Mark both pairs as printed
                    was_printed[j] = true;
                    break; // Move to the next unique pair in the outer loop after finding a match
                }
            }
        }
    }

    return 0;
}

Run

• Sample Output:

Original Pairs:
    (1, 2) (3, 4) (5, 2) (2, 1) (4, 3) (6, 7) (7, 6)

    Symmetric Pairs:
    (1, 2) and (2, 1)
    (3, 4) and (4, 3)
    (6, 7) and (7, 6)

• Stepwise explanation:

1. Similar to the brute-force method, struct Pair is defined, and an array of pairs is initialized.
2. A bool array wasprinted of the same size as pairs is introduced. All its elements are initialized to false. This array acts as a flag for each pair.
3. The outer for loop iterates through each pair pairs[i].
4. Before processing pairs[i], it checks if (!wasprinted[i]). If the flag for pairs[i] is true, it means this pair has already been processed as part of a symmetric pair, so it's skipped.
5. If wasprinted[i] is false, an inner for loop searches for its symmetric counterpart pairs[j] among the subsequent pairs.
6. When a symmetric counterpart pairs[j] is found, an additional check !wasprinted[j] ensures that this jth pair hasn't also been processed. If both conditions are met, the symmetric pair (pairs[i], pairs[j]) is printed.
7. Both wasprinted[i] and wasprinted[j] are set to true to prevent future re-processing of these pairs.
8. A break statement is used after finding and marking a symmetric pair for pairs[i]. This allows the outer loop to proceed to the next un-flagged pair, avoiding unnecessary inner loop iterations for an already handled i.

Conclusion

Finding symmetric pairs in an array is a fundamental problem that highlights different approaches to data traversal and comparison. The brute-force method, while simple, serves as a good starting point for understanding the problem. The optimized approach, using a was_printed flag array, demonstrates a practical way to improve efficiency by avoiding redundant checks and ensuring each symmetric pair is reported only once. The choice between these methods often depends on the size of your dataset and the performance requirements of your application.

Summary

• A symmetric pair (a, b) exists if (b, a) is also present in the given dataset.
• C struct can effectively represent pairs of data.
• The brute-force method uses nested loops to compare every pair with every other pair, with a time complexity of O(N^2).
• An optimized approach uses an auxiliary boolean array to mark pairs that have already been processed, preventing duplicate outputs and slightly improving practical performance, though its worst-case time complexity remains O(N^2).
• Including stdbool.h allows the use of true and false for clearer boolean logic in C.