Can a set have duplicate elements?

Question

I have been asked a question that is a little ambiguous for my coursework.

The array of strings is regarded as a set, i.e. unordered.

I'm not sure whether I need to remove duplicates from this array?

I've tried googling but one place will tell me something different to the next. Any help would be appreciated.

Answer 1

A set cannot have duplicate elements by its mere definition. The correct structure to allow duplicate elements is Multiset or Bag:

In mathematics, a multiset (or bag) is a generalization of the concept of a set that, unlike a set, allows multiple instances of the multiset's elements. For example, {a, a, b} and {a, b} are different multisets although they are the same set. However, order does not matter, so {a, a, b} and {a, b, a} are the same multiset.

A very common and useful example of a Multiset in programming is the collection of values of an object:

values({a: 1, b: 1}) //=>  Multiset(1,1)

The values here are unordered, yet cannot be reduced to Set(1) that would e.g. break the iteration over the object values.

Further, quoting from the linked Wikipedia article (see there for the references):

Multisets have become an important tool in databases.[18][19][20] For instance, multisets are often used to implement relations in database systems. Multisets also play an important role in computer science.

Answer 2

Let A={1,2,2,3,4,5,6,7,...} and B={1,2,3,4,5,6,7,...} then any element in A is in B and any element in B is in A ==> A contains B and B contains A ==> A=B. So of course sets can have duplicate elements, it's just that the one with duplicate elements would end up being exactly the same as the one without duplicate elements.

Answer 3

From Wikipedia in Set (Mathematics)

A set is a collection of well defined and distinct objects.

Perhaps the confusion derives from the fact that a set does not depend on the way its elements are displayed. A set remains the same if its elements are allegedly repeated or rearranged.

As such, the programming languages I know would not put an element into a set if the element already belongs to it, or they would replace it if it already exists, but would never allow a duplication.

Programming Language Examples

Let me offer a few examples in different programming languages.

In Python

A set in Python is defined as "an unordered collection of unique elements". And if you declare a set like a = {1,2,2,3,4} it will only add 2 once to the set.

If you do print(a) the output will be {1,2,3,4}.

Haskell

In Haskell the insert operation of sets is defined as: "[...] if the set already contains an element equal to the given value, it is replaced with the new value."

As such, if you do this: let a = fromList([1,2,2,3,4]), if you print a to the main ouput it would render [1,2,3,4].

Java

In Java sets are defined as: "a collection that contains no duplicate elements.". Its add operation is defined as: "adds the specified element to this set if it is not already present [...] If this set already contains the element, the call leaves the set unchanged".

Set<Integer> myInts = new HashSet<>(asList(1,2,2,3,4));
System.out.println(myInts);

This code, as in the other examples, would ouput [1,2,3,4].

Answer 4

"Sets are Iterables that contain no duplicate elements." https://docs.scala-lang.org/overviews/collections/sets.html