Set Covering: Identify an array combination that intersects with all elements of a specified target array

Suppose there is an array, A, which can be sorted if that information helps.

We have multiple arrays, B, C, D, etc., all sortable and potentially overlapping with array A.

The objective is to identify the smallest combination of arrays B, C, D, etc., which completely overlap with array A. The function should return the first matching set.

For example:

const A = [1, 2, 3, 4, 'a', 'b', 'c'];

const B = [1, 3, 4, 5, 10];
const C = [1, 3, 5, 'a', 'b']
const D = [2, 4, 'a', 'b', 'c'];
const E = [1, 2, 'b', 'c'] 

findSmallestSet(A, [B, C, D, E]);
// => [B, D]

Note: Initially, the problem was about identifying node trees fully encompassing a target node tree. However, this simplified version might offer a more straightforward solution.

Answer №1

Referred to as the 'Set Cover' dilemma, it falls under the category of NP-complete problems and has been extensively researched. The optimal solution varies depending on the scale of the input data and your tolerance for approximate solutions.

Answer №2

To achieve this, first create a sorting function that will arrange the second parameter based on the number of matching elements. Then loop through each inner array and remove elements from the first parameter if they are found in the current array. If there are remaining elements in the first array, sort the keys again and repeat the process using recursion.

const A = [1, 2, 3, 4, 'a', 'b', 'c'];

const B = [1, 3, 4, 5, 10];
const C = [1, 3, 5, 'a', 'b']
const D = [2, 4, 'a', 'b', 'c'];
const E = [1, 2, 'b', 'c']

function findSmallestSet(one, [B, C, D, E]) {
  let obj = {B, C, D, E}
  let keys = Object.keys(obj);
  let getL = (e) => obj[e].filter(e => one.includes(e)).length
  let sortK = (keys) => keys.sort((a, b) => getL(b) - getL(a))
  sortK(keys)
  var r = []

  let find = (one, k) => {
    obj[k[0]].forEach(function(a) {
      var index = one.indexOf(a);
      if (index != -1) one.splice(index, 1)
    })
    
    r.push(k[0])

    if (one.length) {
      k.shift()
      sortK(k)
      find(one, k)
    }
  }

  find(one, keys)
  return r;
}

console.log(findSmallestSet(A, [B, C, D, E]));

Similar questions

If you have not found the answer to your question or you are interested in this topic, then look at other similar questions below or use the search

Triggering Submit Button Based on Checkbox Value in jQuery

Hey there, I'm encountering an issue. Let's say I have two types of checkboxes - one for person and one for company. If I submit the form without checking any of the person or company checkboxes, I want jQuery to display an alert. Otherwise, the ...

The fs.fsync(fd, callback) function in the node.js API allows you

Can you explain the purpose of fs.fsync(fd, callback) in the Node.js API? fs.fsync(fd, callback) This function is used for asynchronous fsync(2). The completion callback only returns an exception if there is one. fs.fsyncSync(fd) This function is for ...

There seems to be a caching issue in ReactJS and Spring Data Rest that could be causing problems with

Encountering an unusual caching problem here. Just recently wiped out my database. While adding new users to the system, an old user mysteriously reappeared. This user has not been recreated and is not in the current database whatsoever. I'm at a lo ...

Guide on transferring data from a JSON file to a JavaScript array

Currently, I am manually declaring the countries list for my typeahead search. To streamline this process, I want to retrieve the data from an external JSON file named countries.json. Here is a snippet of what the JSON file contains: [ { "id": ...

What is the best way to rotate an image using AngularJS?

Hey there, I've got an image that I need help rotating. There are two buttons - left and right - that should rotate the image 45 degrees in opposite directions. I attempted to create a directive using the jquery rotate library, but it's not worki ...

How do I modify the date format displayed in the Bootstrap 4 datetimepicker when sending the value?

I have a datetimepicker() set with ID start_date that matches an input name. In the props, the format is specified as YYYY-MM-DD. I want to use this format for my API, but I want the user to see the date displayed in the format DD-MM-YYYY. $('#start_ ...

How can you effectively blend Vue/Angular with other JavaScript resources to enhance your development process?

My curiosity lies in understanding how front-end javascript libraries such as Vue and Angular can seamlessly integrate with other libraries and assets. For instance, if I were to procure a website template already equipped with additional javascript, is it ...

Implementing a 3D cylinder chart with ReactJS using Highcharts

I've been attempting to incorporate a cylinder 3D chart into my react component, but I keep encountering this error message. Error: Highcharts error #17: www.highcharts.com/errors/17/?missingModuleFor=cylinder missingModuleFor: cylinder The code in ...

Display collection in Vue app

I am working with a model called files, which includes a property named response containing an array called errorMessages. In my Vue component, I am looking for a way to display these errors individually rather than as an array. Is there a solution for thi ...

The purpose of eventOverlap is to enable the inclusion of another event with a distinct tag within the same day

Here is the code snippet: eventOverlap: function(stillEvent, movingEvent) { console.log("I am overlapping something"); if (stillEvent.tags == ""|| movingEvent.tags == "") { console.log("One of the events h ...

If the condition is false, the Bootstrap 4 carousel will not transition to another slide

With Bootstrap 4, each slide contains a form section and there is a next button. I want to ensure that the carousel does not move to the next slide unless a certain variable is true (for form validation purposes). I have attempted using the onclick event ...

performing dual functions within a single click event handler

Is there a way to simultaneously execute 2 functions? In the following code snippet, I am trying to capture the id of the parent Div with the onclick event and then trigger a function using that id. <div id="selDe"> <input type="radio" class="ger ...

What is the best way to invoke a function using a string as its name?

In my grid configuration function, I am assigning column definitions. One key, valueGetter, requires a function to be called to fetch the column value. The issue I am encountering is that the API returns this value as a string. When I try to set it using ...

Minimize/Maximize Swagger Response Model Class View

After successfully integrating Swagger API documentation with my rest services, I encountered a challenge. The Swagger page appears too lengthy due to the numerous response classes in my project, requiring users to scroll extensively to find information. ...

Words within a string are divided in the center, with JS and CSS involved

I'm currently working on developing a hangman game in JavaScript (I am new to web technologies) and I have come across my first challenge. The placeholder string for the word to be guessed, which consists of hyphens and spaces, is overflowing from the ...

Using $emit to send parameters based on the route in Vue.js is essential for conditional communication

Is there a way to create a conditional statement based on the user's route? refreshData (){ var params = {}; for (var key in this.filters) { if (this.filters.hasOwnProperty(key)) { if ( this.filters[key] ...

Having trouble arranging the elements when swapping within a pop-up modal

When I drag and drop two divs inside a modal popup, their positions shift down during the animation. I am struggling to fix this issue. HTML Code: <title> Tile Swapping with Animation</title> <body> <button type="button" class=" ...

Is there a way to bypass the "Error: Another application is currently displaying over Chrome" message using Javascript or Typescript?

Can the "Another app is displaying over chrome error" be bypassed using JavaScript or TypeScript? Error Message: https://i.stack.imgur.com/iSEuk.png ...

Hindering advancement: Bootstrap Form Wizard causing roadblocks

I am currently facing an issue with my form wizard setup. I want to prevent the user from advancing to the next step when the success key in my json is set to false. It seems like the project is utilizing the bootstrap wizard plugin. You can find more in ...

What is the best way to incorporate a CSS transition without any dynamic property changes?

Is there a way to add a transition effect to a header when its size changes without a specified height value in the CSS? The header consists of only text with top and bottom padding, so as the text changes, the height adjusts accordingly. How can I impleme ...