Returning a subset that has a duplicate-CodePudding

My question is how to detect the duplicate on one subset of array that does not exist in the other substring?

For example Input: arr1 = 1,2,3 arr2 = 1,1

Output: Arr2 is not a subset of Arr1

So far everything else works fine and how I want it to but this duplicate one keeps returning that it is a subset. I have tried removing an element by putting it inside the for loop but as an else if but I don't think it was it. Removing the same element on both strings and then doing a loop again to

package com.company;

public class RandomArrayFunctionalities
{
    public boolean subSet(int Array1[], int Array2[], int sizeOne, int sizeTwo)
    {
        //
        int i, j;

        for(i = 0; i < sizeTwo; i  )
        {
            for(j = 0; j< sizeOne; j  )
            {
                if(Array2[i] == Array1[j])
                {
                    for(i = 0; i < sizeOne - 1; i  )
                    {

                        Array1[i] = Array1[i   1];

                        /* Decrement array size by 1 */
                        sizeOne--;

                        for(j = 0; j < sizeTwo-1; j  )
                        {
                            sizeTwo--;

                            if(Array2[i] == Array1[j])
                            {

                                break;
                            }
                        }
                        if(j == sizeOne)
                        {
                            return false;
                        }
                        else
                        {
                            return true;
                        }
                    }

                    break;
                }
            }
            if (j == sizeOne)
            {
                return false;
            }
        }
        return true;
    }
}

public static void main(String[] args)
    {
        RandomArrayFunctionalities ranMethod = new RandomArrayFunctionalities();

        int arr1[] = {1, 2, 3};
        int arr2[] = {1,1};

        int sizeOne = arr1.length;;
        int sizeTwo = arr2.length;;

        if(ranMethod.subSet(arr1, arr2, sizeOne, sizeTwo))
        {
            System.out.println("\nArray 2 is a subset of array 1\n");
        }
        else
        {
            System.out.println("\nArray 2 is not a subset of array 1\n");
        }
    }

CodePudding user response：

I think one of the problems you have in your implementation is to not remove the element in the main list when it is in the subset list.
So when you check the second "1", it still exists in the main list.

I would do it as follows. There should be more checks whether the subset list is bigger than the main list but it is easy to add.

public static void main(final String[] args) {
    final List<String> main = Arrays.asList("1", "2", "3");
    final List<String> subset = Arrays.asList("1", "2");
    final List<String> notSubset = Arrays.asList("1", "1");

    displaySubsetOrNot(main, subset);
    displaySubsetOrNot(main, notSubset);
}

private static void displaySubsetOrNot(final List<String> main, final List<String> subset) {
    if (isSubset(main, subset)) {
        System.out.println("subset");
    } else {
        System.out.println("not subset");
    }
}

private static boolean isSubset(final List<String> mainList, final List<String> subsetList) {
    final List<String> mainListCopy = new ArrayList<>(mainList);
    for (final String element : subsetList) {
        if (!mainListCopy.remove(element)) {
            return false;
        }
    }
    return true;
}

CodePudding user response：

Option 1 use a Set to record those matched index, when a repeated value comes in arr2, we skip the matched index and try to find anther repeated value in arr1.

public boolean subSet(int Array1[], int Array2[], int sizeOne, int sizeTwo) {
    if (Array2.length == 0 || Array2.length > Array1.length) {
        return false;
    }
    Set<Integer> matchedIndex = new HashSet<Integer>();
    for (int index = 0; index < Array2.length; index  ) {
        boolean matched = false;
        for (int k = 0; k < Array1.length; k  ) {
            if (matchedIndex.contains(k)) {
                continue;
            }
            if (Array1[k] == Array2[index]) {
                matched = true;
                matchedIndex.add(k);
                break;
            }
        }
        if (!matched) {
            return false;
        }
    }
    return true;
}

Option 2 sort both arrays, each value in the arr1 is compared once only

public boolean subSet(int Array1[], int Array2[], int sizeOne, int sizeTwo) {
    if (Array2.length == 0 || Array2.length > Array1.length) {
        return false;
    }
    /**
     * make a copy of arrays of the original array should not be modified
     */
    Arrays.sort(Array1);
    Arrays.sort(Array2);
    int k = 0;
    for (int index = 0; index < Array2.length; index  ) {
        boolean matched = false;
        for (; k < Array1.length; k  ) {
            if (Array1[k] == Array2[index]) {
                k  ;
                matched = true;
                break;
            }
        }
        if (!matched) {
            return false;
        }
    }
    return true;
}

CodePudding user response：

I would approach this completely differently. I would use the List class and use the below logic to check if one array is a subset of the other:

public boolean isSubset(int[] arr1, int[] arr2)
{
    // turn the first array into a list to make removing items easier.
    List<Integer> list1 = Arrays.stream(arr1).boxed().collect(Collectors.toList());

    for (Integer currentElement : arr2)
    {
        if (!list1.contains(currentElement)) // Check if list1 contains the element of list2, if not return false
        {
            return false;
        }

        list1.remove(currentElement); // we checked that the list has the currentElement, but if list2 has the element twice, then list1 must have it twice too, so we remove it to make sure that each element has the same count in list1 as in list2
    }

    return true;
}

This way you do not need to sort anything and you solve it in very few lines. That list1.remove() makes it possible to check that the count of the elements is the same.

CodePudding user response：

Frequency maps should be created for both arrays, and a difference of the frequencies needs to be calculated:

for each key in map2:
    map2.put(map2.get(key) - map1.getOrDefault(key, 9))

If the map2 contains all frequencies below or equal to 0, then arr2 is a "subset" of arr1.

```java
public static boolean subSet(int[] arr1, int[] arr2) {
    Map<Integer, Integer> freq1 = Arrays.stream(arr1).boxed()
        .collect(Collectors.groupingBy(x -> x, Collectors.summingInt(x -> 1)));
    Map<Integer, Integer> freq2 = Arrays.stream(arr2).boxed()
        .collect(Collectors.groupingBy(x -> x, Collectors.summingInt(x -> 1)));
    
    freq2.forEach((k, v) -> freq2.put(k, v - freq1.getOrDefault(k, 0)));

    // debug print
    System.out.println("freq2: "   freq2);

    return freq2.values().stream().allMatch(x -> 0 >= x);
}

Test:

System.out.println(subSet(new int[]{1, 2, 3}, new int[]{1, 1}));
System.out.println(subSet(new int[]{1, 2, 3}, new int[]{1, 3}));
System.out.println(subSet(new int[]{1, 2, 3, 1}, new int[]{1, 1}));

Output:

freq2: {1=1}
false
freq2: {1=0, 3=0}
true
freq2: {1=0}
true

Or just one map can be created for arr1 then the elements from arr2 can be "subtracted" from the frequencies in map1 and as soon as a negative value occurs, false is returned:

public static boolean subSet(int[] arr1, int[] arr2) {
    Map<Integer, Integer> freq1 = Arrays.stream(arr1)
        .boxed()
        .collect(Collectors.groupingBy(x -> x, Collectors.summingInt(x -> 1)));

    for (int x : arr2) {
        if (freq1.merge(x, -1, Integer::sum) < 0) {
            return false;
        }
    }
    return true;
}