algorithmsetunique# Given multiple sets, how do I find the smallest subset of each set that is unique to all other subsets?

**Background**. I have numbers 1 to 20 (white digits on black background) that can appear on screen, and I wish to identify these numbers. As they cannot be simply copy-pasted, I will be comparing the position of the white pixels of the number on-screen with a list of positions of white pixels of all 20 numbers. However, each number can have a large number of pixels, and comparing all of those pixels may not be necessary to identify that number. Hence, I'd like to make the least number of comparisons as possible.

**Algorithmic question:** I have multiple sets with elements that are unique within each set, but may not be unique across all sets. How can I find the smallest possible subset of each set such that each subset is unique?

**Example 1:** Let A = {1, 2}, and B = {3, 4}. The smallest subset of A and B would be {1} and {3} (or {2} and {4}), as those subsets are unique to each original set, and are as small as possible.

**Example 2:** Let A = {1, 2, 3, 4}, B = {1, 2, 3, 5}, C = {1, 2, 4, 5}. Possible smallest subsets are {3, 4}, {3, 5}, {4, 5}. If any element were removed from any of those subsets, then that subset can also belong to a different set. E.g. removing 4 from the first subset will leave {3}, which makes it ambiguous if the {3} identifies the first or the second set.

Solution

It's a solution with O(n^3) time complexity, and O(n) memory complexity. (If I am not wrong)

```
function isElement(elem, s) {
return s.includes(elem)
}
function isId(id, sets) {
let setsWithSuchElementsNumber = 0
for (const s of sets) {
if (id.every((e) => isElement(e, s))) {
setsWithSuchElementsNumber++
}
}
return setsWithSuchElementsNumber === 1
}
function getSetId(s, sets) {
const count = {}
const elements = []
for (const elem of s) {
if (count[elem] == null) {
elements.push(elem)
}
count[elem] = 0
}
for (const otherSet of sets) {
for (const e of elements) {
if (isElement(e, otherSet)) {
count[e]++
}
}
}
elements.sort((first, second) => {
return Math.sign(count[first] - count[second])
})
for (let idSize = 1; idSize <= elements.length; idSize++) {
const possibleId = elements.slice(0, idSize)
if (isId(possibleId, sets)) {
return possibleId
}
}
return null
}
const getSetIds = (sets) => {
return sets.map((s) => getSetId(s, sets))
}
const res = getSetIds([
[1, 2, 3, 4],
[1, 2, 3, 5],
[1, 2, 4, 5],
])
console.log(res.join(' '))
```

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharp？
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array