I was doing some F.O.L. problems and I noticed that quite a lot of them could be easily solved if I could just treat a given array as a set.
Example: $B(1..n)$ is a permutation of $A(1..n)$
The first thing I thought about was something like this $$B\subset A, A\subset B, (\aleph A=\aleph B), A\neq B$$
(The answer may not be perfect, it's just to illustrate my point). The teacher said that, while the general idea was correct, the notation wasn't since you can't treat an array (which has ordered elements) as a set (which is a bunch of elements in no particular order), and the answers would not be correct unless I found a way to treat arrays as sets.
I have been thinking about this and looking for stuff for couple of days now and I can't find anything about this. Is there any notation that expresses this idea? Something like
$S[symbol]A(1..n)$ [The set $S=\lbrace1, \dots n\rbrace$ contains all the elements in the array $A$]
I have seen procedures and some juggling that does this, but I'm looking for something simpler that allows these kind of problem to be solved like this:
$$\forall S_1[symbol]A, S_2[symbol]B(S_1\subset S_2, S_2\subset S_1, \aleph S_1=\aleph S_2, A\neq B)$$
Your teacher most likely intends you to express sets and their operations (or at least the ones you use) in the terms of arrays.
It's not hard to create sets from arrays, the basic idea of a set is an structure that contains a number of elements unordered and without duplications, the most trivial way to implement this requires the element to be comparable for equality (duh) and is as simple as doing something along these lines:
Similar operations can be used to define unions and intersections and of course the way to check if an element is part of a set involves just iterating over all the elements of the array.
But as you porbably have infered this is a very expensive structure, thus there are optimized ways of doing it if the elements have an ordering on example would be using ordered arrays or representing balanced binary trees with arrays.
In a similar way, if the number of elements of the set is known you can map each element to an intheger and then use a bit array where the value 1 or 0 denotes the pressence of an elemento or not into the set.
Summarizing: A set basically is an unordered container with no duplicate elements, an array can be used for that if duplicates are removed (the algorithm posted here is a trivial one as there are better implementations).
Also the only operation that is hard do to with arrays containing sets is the complement (when the set is done over a group of infinite elements) as that'd result in an infinite array. Anything else (union, intersection, difference...) can be done easily in cuadratic time with unordered arrays and in faster times depending of the structure of the set.