Where should I look if I want to write a piece of code which looks for Array1 in Array2, regardless of the order (keeping the duplicates in mind)? e.g.
Array1: { 2,5,6,6,3 }
Array2: { 1,2,3,4,5,6,6 }
will return true
Array1: { 2,5,6,6,3 }
Array2: { 1,2,3,4,5,6 }
will return false
I sort of want to solve it myslef, I just need to be pointed in some direction.
Thanks in advance.
Well, since you only want hints rather than code, one method would be:
Copy array2 into a List<int>.
Allocate a bit array called used equal to the size of the list. These will be flags indicating whether a specific item in the sorted list has been used for a match.
For each item item in array1:
4.1 Binary search the sorted list for item.
4.2. If not found, return false -- array2 does not contain array1.
4.3. If found, and there are duplicates, the binary search algorithm will randomly return the index of one of the duplicates. Scan backward in the portion of the list that matches item until you find one for which used[i] is false. If you find one, set used[i] to true, and continue the outer loop. If you don't find one, scan forward from the initial binary search index, trying to find an unused match. Similarly set used[index] to true if one is found, and continue looping through array1.
4.4 If no unused match is found, return false -- array2 does not contain array1.
Having found an unused match for each item in array1, return true: array1 is contained inside array2.
An advantage of this algorithm is that, to check multiple arrays for being contained in a given array, you don't need to re-sort the array every time, you only need to re-allocate the BitArray.
