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 trueArray1: { 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.

Well, since you only want hints rather than code, one method would be:

1. Copy `array2` into a `List<int>`.

2. Sort it.

3. 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.

4. 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`.

5. 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`.

Top