Python | Minimum number of subsets with distinct elements using Counter
Last Updated :
27 Apr, 2023
You are given an array of n-element. You have to make subsets from the array such that no subset contain duplicate elements. Find out minimum number of subset possible. Examples:
Input : arr[] = {1, 2, 3, 4}
Output :1
Explanation : A single subset can contains all
values and all values are distinct
Input : arr[] = {1, 2, 3, 3}
Output : 2
Explanation : We need to create two subsets
{1, 2, 3} and {3} [or {1, 3} and {2, 3}] such
that both subsets have distinct elements.
We have existing solution for this problem please refer Minimum number of subsets with distinct elements link. We will solve this problem quickly in python using Counter(iterable) method. Approach is very simple, calculate frequency of each element in array and print value of maximum frequency because we want each subset to be different and we have to put any repeated element in different subset, so to get minimum number of subset we should have at least maximum frequency number of subsets.
Python3
from collections import Counter
def minSubsets(input):
freqDict = Counter(input)
print (max(freqDict.values()))
if __name__ == "__main__":
input = [1, 2, 3, 3]
minSubsets(input)
|
Approach#2: Using Counter and itertools.combinations()
We use Counter to count the frequency of each element in the input array. Then, we calculate the number of distinct elements in the array. If the number of distinct elements is equal to the length of the array, we return 1, as all elements are distinct and can be put in a single subset. Otherwise, we try to create subsets of increasing size, until we can create a subset with all the distinct elements. We check if the subset contains only distinct elements and the sum of frequencies of all elements in the subset is greater than or equal to the size of the subset.
Algorithm
1. Calculate the frequency of each element in the input array using Counter.
2. Calculate the number of distinct elements in the array using set() and len().
3. If the number of distinct elements is equal to the length of the array, return 1. Otherwise, try to create subsets of increasing size from 1 to the number of distinct elements.
4. For each subset size, generate all possible subsets using combinations() from itertools.
5. For each subset, check if the subset contains only distinct elements and the sum of frequencies of all elements in the subset is greater than or equal to the size of the subset.
6. If such a subset is found, return its size.
7. If no subset is found for any size, return -1.
Python3
from collections import Counter
from itertools import combinations
def count_min_subsets(arr):
freq = Counter(arr)
num_distinct = len(set(arr))
if num_distinct == len(arr):
return 1
else:
for i in range(1, num_distinct+1):
for subset in combinations(freq.keys(), i):
if len(set(subset)) == i:
if sum([freq[k] for k in subset]) >= i:
return i+1
arr=[1, 2, 3, 4]
print(count_min_subsets(arr))
|
Time Complexity: O(2^n * n), where n is the number of distinct elements in the array. The combinations() function generates all possible subsets of each size, and for each subset, we need to check if it contains only distinct elements and if the sum of frequencies is greater than or equal to the size of the subset. Therefore, the time complexity is exponential in the number of distinct elements.
Space Complexity: O(n), where n is the number of distinct elements in the array. We use a Counter to store the frequency of each element in the array, which requires O(n) space. The combinations() function also generates subsets of size up to n, so the space complexity is also O(n).
Please Login to comment...