Set Theory: Difference

12 Mar 2014

C#, Maths, Python

In set theory, the difference operation determines which elements from one set do not appear in the elements of another given set.

The - symbol denotes a difference, it is essentially similar to a subtraction operation, and we write it the same way:

X - Y

For example:

X = { 1, 2, 3, 4 }
Y = { 3, 4, 5, 6 }

X - Y = { 1, 2 }

A difference result is calculated by determining which elements in X do not appear in Y.

Here's a difference extension method in C# you can use to add set differences to your code:

///

/// Generates an array of all the elements in X that are not in Y ///

/// An array of integers /// An array of integers /// Returns a distinct, ordered difference array public static int[] Difference(this int[] X, int[] Y) { return new List(X.Where(m => (Y.Contains(m) == false))).Distinct().OrderBy(m => (m)).ToArray(); } ///

/// Generates an array of all the elements in X that are not in Y. Provided for those who don't like LINQ. ///

/// An array of integers /// An array of integers /// Returns a distinct, ordered difference array public static int[] Difference(this int[] X, int[] Y) { X = X.Distinct(); Y = Y.Distinct(); int[] iNonLinqDifference = new int[] { }; foreach (int iX in X) { bool bIsFound = false; foreach (int iY in Y) { bIsFound = (iX == iY); if (bIsFound == true) { break; } } if (bIsFound == false) { iNonLinqDifference = Resize(iNonLinqDifference, (iNonLinqDifference.Length + 1)); iNonLinqDifference[(iNonLinqDifference.Length - 1)] = iX; } } return iNonLinqDifference; } public static int[] Distinct(this int[] Values) { int[] iValues = new int[] { }; for (int i = 0; i < Values.Length; i++) { int iValue = Values[i]; bool bIsValueFound = false; for (int j = 0; j < iValues.Length; j++) { if (iValues[j] == iValue) { bIsValueFound = true; break; } } if (bIsValueFound == false) { iValues = Resize(iValues, iValues.Length + 1); iValues[(iValues.Length - 1)] = iValue; } } return iValues; }

Here's the code rewritten in Python:

class SetTheory(object):

    def Difference(self, X, Y):
        iDifference = []

        X = self.Distinct(X)
        Y = self.Distinct(Y)

        for i in range(len(X)):
            bIsValueFound = False

            for j in range(len(Y)):
                if (X[i] == Y[j]):
                    bIsValueFound = True
                    break

            if (bIsValueFound == False):
                iDifference.append(X[i])

        return iDifference

    def Distinct(self, Values):
        iDistinct = []

        for i in range(len(Values)):
            iValue = Values[i]

            bIsValueFound = False
            for j in range(len(iDistinct)):
                if (iDistinct[j] == iValue):
                    bIsValueFound = True
                    break

            if (bIsValueFound == False):
                iDistinct.append(iValue)

        return iDistinct