mapping,combinatorics,computation-theory,np-complete,set-theory , How to match a set against a set of sets, completely


How to match a set against a set of sets, completely

Question:

Tag: mapping,combinatorics,computation-theory,np-complete,set-theory

This problem is similar to the "Exact Hitting Set" problem (http://en.wikipedia.org/wiki/Exact_cover#Exact_hitting_set) but with slightly different constraints.

I am looking for libraries, implementations, or papers that solve the following.

Say I have a set of sets S, and is initialized as follows:

S = {N, O, P, E};

N = {1, 2, 5}
O = {4, 5}
P = {1, 6, 7}
E = {2, 3, 8}};

S has n sets, and each subset set is of unknown size. In this example n = 4

Now I have another set X of size n, which is initialized to:

X = {1, 2, 4, 6}

What I need to do, is match each element in X to one and only one set in S.

So S should be completely satisfied with all of it's sets mapped to X and vice versa.

X[0] --> N
X[1] --> E
X[2] --> O
X[3] --> P

The main problem I am having is how to deal with the duplicated data with in the sets of S. How do I deal with these collisions? And How to implement the algorithm in such a way that is relatively scalable?

If you have any information that could point me in the right direction to solve this will be very much appreciated.


Answer:

You could create a bipartite graph in the following manner:

Then having the bipartite graph you can solve the problem using hopcroft karp algorithm to produce the maximum cardinality matching.(O(|E|sqrt(V)))


Related:


Change lowercase and uppercase of characters in java


java,unicode,mapping,uppercase,lowercase
If I want to create a dictionary where the user can create a custom alphabet (that still uses unicode) Is there a way to change lowercase and uppercase mapping of the characters? Let's say I want the lowercase of 'I' to be 'ı' instead of 'i' or upperCase of 'b'...

vim comment/uncomment with one mapping [duplicate]


function,vim,mapping,comments
This question already has an answer here: What's a quick way to comment/uncomment lines in Vim? 32 answers I'm new(bie) in vim. I've got the following mapping to comment my python code : nmap cc 0i#<ESC> I would like to have the same mapping to uncomment a line. I...

Symfony2 / Doctrine2 : how to access an entity annotation mapping?


symfony2,doctrine2,annotations,mapping,accessor
In my Symfony2/doctrine2 application, I have two entities, Media and Recipe. They can be linked by a oneToMany or a ManyToMany association. In the case of a oneToMany relationship, I am using the following code to retrieve the Recipe linked to an instance of Media : $accessor = PropertyAccess::createPropertyAccessor(); $reflect...

Many to One Relation in Symfony 2


symfony2,doctrine2,mapping,schema,many-to-one
I have a problem related to Doctrine2: 1- I have two tables joining on a many-to-one relation: Table 1 - Activity The Schema: Backend\adminBundle\Entity\Activity: type: entity table: activity indexes: result_id: columns: - result_id id: id: type: integer nullable: false unsigned: false comment: '' id: true generator: strategy: IDENTITY fields: .........

Searching in specific indices with JSON object


elasticsearch,mapping,elasticsearch-dsl
I have a problem. In my application I'm using ElasticSearch. I'm posting JSON object to my ElasticSearch server. That JSON object contain DSL query. So, what I need to do, is to query specific index for some data. This is the query: { "query":{ "indices":{ "indices":[ "index-1" ], "query":{ "bool":{...

Spring RequestBody Mapping maps all attributes to null values


java,spring,web-services,rest,mapping
i have the following RESTfull method : @RequestMapping(value = "/budgetLines", method = RequestMethod.POST, produces = MediaType.APPLICATION_JSON_VALUE) @Timed public void create(@RequestBody BudgetLine budgetLine) { System.out.println("Before Persisting in the repository " + budgetLine); budgetLineRepository.save(budgetLine); } I'am consuming this method inside a web application, i checked using the network analysis tool (in the...

Leaflet package in R not plotting all coordinates


r,mapping,leaflet
I'm trying to plot using leaflet with a somewhat sizable set of coordinates (~34K latitude/longitude pairs) however, using the code below it seems that leaflet is only plotting a small portion of these: data <- read.csv("Food_inspections.csv", header = TRUE) names(data) <- tolower(names(data)) data1 <- filter(data, risk == c("Risk 1 (High)","Risk...

Control pan and zoom animation duration in mapbox.js


mapping,gis,mapbox,mapbox-gl-js
I'm making an animated map showing a series of points using Mapbox.js. Ideally, I want to smoothly switch focus between points by combining zoom and pan like this example created in d3.js. I wonder if there is anyway to control the pan & zoom animation speed (mainly to slow it...

How to understand the following C# linq code of implementing the algorithm to return all combinations of k elements from n


c#,.net,linq,recursion,combinatorics
Anyone can elaborate some details on this code or even give a non-Linq version of this algorithm: public static IEnumerable<IEnumerable<T>> Combinations<T> (this IEnumerable<T> elements, int k) { return k == 0 ? new[] { new T[0] } : elements.SelectMany( (e, i) => elements .Skip(i + 1) .Combinations(k - 1) .Select(c...

Selenium Web Driver : How to map html elements to Java Object.


selenium,webdriver,mapping
As part of Selenium Web-driver learning I came across a scenario. Please let me know the professional approach to proceed. I am testing a eCommerce application where while I click on Mobile link all mobile phones are getting displayed.I want to check whether they are sorted based on name and...

C# LINQ combinatorics: All Combinations of a Set without the Empty Set


c#,linq,combinatorics
I have a set of strings, and I want to find all possible combinations of the strings and add them to a list. I want to end up with a list of a list of each combination of the strings, minus the empty set. I have created a solution that...

When I try to map the properties for an entity (Entity Framework), I get the error the type '__' must be a non-nullable value type


c#,entity-framework,generics,mapping,nullable
My mapping class looks like the following: public class EmployeeMap : EntityTypeConfiguration<EFEmployee> { public EmployeeMap() { HasKey(t => t.Id); Property(t => t.Id).HasDatabaseGeneratedOption(DatabaseGeneratedOption.Identity); Property(t => t.HireDate).IsRequired(); //Property(t => t.JobTitle).IsRequired(); Property(t => t.Salary).IsRequired(); //Property(t => t.Certifications).IsRequired(); Property(t => t.VacationTime).IsRequired(); Property(t => t.SickTime).IsRequired(); //Property(t =>...

Combinations of variable length with fixed set


haskell,permutation,combinatorics
I have a set of possible colors defined like this: data Peg = Red | Green | Blue | Yellow | Orange | Purple deriving (Show, Eq, Ord) colors = [Red, Green, Blue, Yellow, Orange, Purple] And code which is a combination of colors defined like this: type Code =...

My ES custom analyser is not used?


elasticsearch,mapping,elastic
I'm using Elasticsearch and create an index with the following information for mapping and settings. The problem I have is that my field geography.locality which should use the 'name_analyser' doesn't seem to use it. { "index": "programs", "body": { "settings": { "number_of_shards": 5, "analysis": { "filter": { "elision": { "type":...

Mapping values of a matrix?


matlab,matrix,mapping
So I have a large matrix(4091252x2) that looks something like this: 439105 1053224 439105 1696241 439105 580064 439105 1464748 1836139 1593258 1464748 439105 1464748 1053224 1464748 1696241 1464748 580064 580064 439105 Basically, the matrix represents calls made from one person to another, represented by a personID (439105 calls 1053224). What...

can't force GROK parser to enforce integer/float types on haproxy logs


types,mapping,logstash,kibana,grok
Doesn't matter if integer/long or float, fields like time_duration (all time_* really ) map as strings in kibana logstash index. I tried using mutate (https://www.elastic.co/blog/little-logstash-lessons-part-using-grok-mutate-type-data) did not work either. How can i correctly enforce numeric type instead of strings on these fields? My /etc/logstash/conf.d/haproxy.conf: input { syslog { type =>...

vim - how to stop this bug: insert single char func - put vs p


vim,time,mapping
I wanted to be able to easily insert a single char from normal mode, and clean up some of the mappings that were being added for that purpose while I was at it. I have this in my vimrc now: "insert single char from normal mode function! InsertSingleChar() "jump into...

JavaScript objects: 'addEventListener is not a function'


javascript,html,object,canvas,mapping
I create an array of JavaScript objects called elements and loop through it in order to draw every one on a canvas as well as hooking up a few event handlers to it. However, I get an error stating that 'Uncaught TypeError: elements[i].addEventListener is not a function' Here is the...

AutoMapper: An exception of type 'AutoMapper.AutoMapperMappingException' occurred in AutoMapper.dll but was not handled in user code


c#,mapping,automapper,dto
I have a problem like this. But this answer it didn't work for me. I am working on a little project. I have two domain model (Post, Source): public class Post { public Post() { Sources = new HashSet<Source>(); } public int Id { get; set; } public string Title...

model isn't working as expected C#


c#,model,mapping,dapper
My model is getting data I need, but I'm not sure how to organize it in the way I need. I have it where the model pulls a team, and a player. The issue is when mapping my data to the model it gives me duplicate teams, and doesn't allow...

Data transformations on-the-fly


mapping,apache-spark,storm
Is there a way, other than a manual mapping, to translate related values on-the-fly? I know this sounds vague but what I am looking for is a way to take an input value of say "2015 Ford" and translate it given to a mapping provided by a client that indicates...

How to generate all partitions of a set


algorithm,set,combinatorics,backtracking
For a set of the form A = {1, 2, 3, ..., n}. It is called partition of the set A, a set of k<=n elements which respect the following theorems: a) the union of all the partitions of A is A b) the intersection of 2 partitions of A...

Azure Table Storage - TableEntity map column with a different name


azure,mapping,windows-azure-storage,azure-storage-tables
I am using Azure Table Storage as my data sink for my Semantic Logging Application Block. When I call a log to be written by my custom EventSource, I get columns similar to the ff.: EventId Payload_username Opcode I can obtain these columns by creating a TableEntity class that matches...

org.hibernate.MappingException: Unknown entity: from xxx


hibernate,mapping,entity
I was trying to resolve issue which I posted here But, now I'm getting another issue. :( org.hibernate.MappingException: Unknown entity: from EmpTest at org.hibernate.internal.SessionFactoryImpl.getEntityPersister(SessionFactoryImpl.java:1095) at org.hibernate.internal.SessionImpl.getOuterJoinLoadable(SessionImpl.java:1754) at org.hibernate.internal.SessionImpl.list(SessionImpl.java:1659) at org.hibernate.internal.CriteriaImpl.list(CriteriaImpl.java:380) at com.model.EmpModelImp.getAll(EmpModelImp.java:84) at...

There should be one non-read-only mapping defined for the primary key field


jpa,mapping,eclipselink
Hi I've the following code (using eclipselink 2.6): Transmission: @Entity public class Transmission { @Column(name="TRANSMISSION_ID") @Id private Long id; @Column(name="TRANSMISSION_CONTENT") private String content; .... } HeaderPk: @Embeddable public class HeaderPk { // this is a foreign key to "TRANSMISSION_ID" in Transmission @Column(name="FK_TRANSMISSION_ID") private Long transmissionId; @Column(name="MAILBOX_ID") private String mailboxId; @Column(name="TRANSMISSION_TIME")...

Random sample of character vector, without elements prefixing one another


r,performance,combinatorics
Consider a character vector, pool, whose elements are (zero-padded) binary numbers with up to max_len digits. max_len <- 4 pool <- unlist(lapply(seq_len(max_len), function(x) do.call(paste0, expand.grid(rep(list(c('0', '1')), x))))) pool ## [1] "0" "1" "00" "10" "01" "11" "000" "100" "010" "110" ## [11] "001" "101" "011" "111" "0000" "1000" "0100" "1100"...

Add brands through company, it's possible? How?


php,symfony2,doctrine2,mapping,symfony-2.6
I have this two tables (see pics below) mapped as follow: class Brand { ... /** * @var Company * * @ORM\ManyToOne(targetEntity="Company") * @ORM\JoinColumn(name="companies_id", referencedColumnName="id") */ protected $company; } class Company { ... } I need to add support for add a new Brand from Company but I have not...

PowerShell map persistent sharepoint path


powershell,sharepoint,mapping
I'm trying to map the path to a SharePoint document library in a persistent way. It's strange that this works fine: $Sharepoint = '\\domain.net\stuff\Documents\Folders - Permission matrix' New-PSDrive -Name P -Root $Sharepoint -PSProvider FileSystem -Credential $Credentials But this doesn't work: New-PSDrive -Persist -Name P -Root $Sharepoint -PSProvider FileSystem -Credential $Credentials...

MapperParsingException when creating mapping for elasticsearch index


elasticsearch,mapping,sense
Using sense, I'm trying to create a mapping for an index with three properties. When i try to create it i get the following response { "error": "MapperParsingException[Root type mapping not empty after parsing! Remaining fields: [mappings : {gram={properties={gram={type=string, fields={gram_bm25={type=string, similarity=BM25}, gram_lmd={type=string}}}, sentiment={type=string, index=not_analyzed}, word={type=string, index=not_analyzed}}}}]]", "status": 400 } This...

How to quickly map a combination of elements to another vector


algorithm,mapping
Suppose I have two set of elements, X and Y. Both sets contain tens of thousands (or more) unique elements. Any combination of elements in X, like (X1, X4, X6, X100, ...), may be mapped to zero, one or multiple elements in Y. How should I store the data in...

How to find all strings that do not contain substring palindromes


string,algorithm,probability,combinatorics,discrete-mathematics
Disclaimer: This is a problem lifted from HackerRank, but their editorial answer wasn't sufficient so I hoped to get better answers. If it's against any policy, please let me know and I'll take this down. Problem: You are given two integers, N and M. Count the number of strings of...

Is there a way to configure Elasticsearch so that it will prevent creating new type in specific index?


indexing,elasticsearch,mapping
For example: I have index people and document type person-info. I explicitly defined its mapping by: curl -XPUT 'http://localhost:9200/people/_mapping/person-info' -d ' { "person-info" : { "properties" : { // some mapping } } } Once I inserted some documents to person_info instead of person-info by mistake. So Elasticsearch automatically created...

How to make a dictionary of arrays?


arrays,matlab,dictionary,mapping,containers
I can't seem to figure out how containers.Map works. It's doing okay with characters and numbers, but flips out when I try to feed it arrays. How do I make something like this? function test global a a = containers.Map(); a(pi) = 3:14; a(5) = 4:2:10; end ...

matlab algorithm for specific configurations [duplicate]


matlab,combinatorics
This question already has an answer here: Generate all possible combinations of the elements of some vectors (Cartesian product) 3 answers How to effectively implement in matlab this specific combinatorics problem? I have a list of possible values {{v1_1,...v1_n1},{v2_1, ..., v2_n2}, ... {vm_1, ... , vm_nm}} . I need...

EER diagram with mandatory sub-classes to SQL tables


sql,sql-server,mapping,relational
I am working on an assignment to create a database for fast food outlet and am stuck with generating a relational schema from my EER which has mandatory subclasses. I have a CustOrderDetails(OrderNo {PK}, EmployeeNo, DiscCode,....) entity with subclasses DeliveryOrder(CallStart,...) and PickUpOrder(PickUpName,...). These are "Maandatory/Disjoint" so CustOrderDetails MUST be one...

HIbernate mapping on the wrong froreign key


java,xml,hibernate,mapping
I have 2 classes Device and Position that have a relation one-to-many/many-to-one (One device has several positions, a position is associated to one and only one device). I have clearly specified in the hibernate mapping file that I want my table to join on device.DeviceID = position.FK_DeviceID, yet when i...

Serve private mapping from S3 tiles by proxying data or signing urls through heroku?


heroku,amazon-s3,mapping,leaflet,cesium
I want to store mapping tiles in a private S3 bucket. Each tile has its own URL and each set of tiles could potentially have GBs of tiles. I then want to visualise these tiles through a front end mapping client (e.g leaflet). This client pulls tiles as it needs...

Texture mapping consuming physical memory


c++,opengl,mapping,textures,glut
there's a problem with my texture mapping, when I execute the code, it run smoothly for 5-8 sec, then the framerate drop drastically, when I monitor the task manager, it seem the program consuming almost 95% of my physical memory, anybody know how to solve this problem?? I'm using visual...

R Creating a Character Column from a Numeric Column w/o using For Loop


r,for-loop,mapping,character,lookup
I am trying to create a column of characters based on an existing column of numbers, preferably without using a for loop. I have come up with a variety of ways to do this, but I keep feeling like I'm making this far more complicated than it needs to be....

Convert grayscale to color gradient in Java?


java,image,colors,mapping,grayscale
Is there any general algorithm or a provided class for mapping a grayscale value (0-255) to a value in a colour gradient? I am thinking of something of the sorts: public Color mapGrayscaleValue (byte value, Color[] gradientColors); I am wanting this to provide clearer highlights in what would otherwise be...

Creating analyzed and not_analyzed index on all fields in Elasticsearch


python,indexing,elasticsearch,mapping
Im pretty new to Elasticsearch. I have a requirement of creating ALL string fields with an "analyzed" and "not_analyzed" index. I have been able to do it for 1 or 2 fields, but how can I do this if I have 50 fields in my document? I have used the...

Optimal way to find number of operation required to convert all K numbers to lie in the range [L,R] (i.e. L≤x≤R)


arrays,algorithm,combinatorics
I am solving this question which requires some optimized techniques to solve it. I can think of the brute force method only which requires combinatorics. Given an array A consisting of n integers. We call an integer "good" if it lies in the range [L,R] (i.e. L≤x≤R). We need...

How to insert key and value to map that is inside another map in cpp?


c++,insert,mapping,iteration
I have this map : std::map<std::string, std::map<std::string, std::string> > objects; As far as I know, when I write objects[key] it will replace the value of the key already exists, but here I want it to add to the second map if the pair doesn't exist. Example: Current MAP :("key1",map(<"key_a","value_a">,<"key_c","value_d">)) input:...

Mapping from One Sheet to Another Fill Unfilled chracter


excel,excel-vba,printing,header,mapping
So I have one excel document that has partially filled character array ("|" shows excel column line): Current Result ("_" is a space): 1111GGH80100022190 1112QQH80100023201 1113GGH80100045201 1114AAH80100025190 So my current code outputs this above result. The problem is that characters 1-5 and 21-24 get skipped over. In general if there...

Permutation At A Railway Track(Stack Implementation)


algorithm,stack,combinatorics
Engines numbered 1, 2, ..., n are on the line at the left, and it is desired to rearrange(permute) the engines as they leave on the right-hand track. An engine that is on the spur track can be left there or sent on its way down the right track,...

Is finding a subset with exact cut with other given subsets NP-hard?


algorithm,complexity-theory,combinatorics,computation-theory
I am trying to figure out whether the following problem is NP-hard: Given G_1,..,G_n subsets of {1..m} c_1,..,c_n non-negative integers in {0..m} Find T subset of {1..m} S.T. for all i=1..n, T intersects G_i in exactly c_i elements I tried to find reductions to NP problems such as coloring, or...

Mapping int to int (in Java)


java,algorithm,dictionary,integer,mapping
In Java. How can I map a set of numbers(integers for example) to another set of numbers? All the numbers are positive and all the numbers are unique in their own set. The first set of numbers can have any value, the second set of numbers represent indexes of an...

Calculate latitude/longitude between two other coordinates certain meters away


javascript,mapping
I am working on a Javascript function for calculating a coordinate with latitude and longitude on a "line" between two other coordinates. This coordinate that i need to calculate for example is 300 meters away from the first coordinate while the distance between the two coordinates is 1600 meters. What...

Using EF6 code-first, reference same property name


c#,entity-framework,properties,mapping
How to reference both ShippingAddressId and BillingAddressId properties in Customer class to Address class which has a diffrent key named AddressId? Running update-database -verbose causes error: Unable to determine the principal end of an association between the types 'Project1.Customer' and 'Project1.Address'. The principal end of this association must be explicitly...

Copy web-builder created website to new hosting


file-upload,mapping,hosting
I have a website created in a web-building online app (link to the app: http://www.webnode.com). The app doesn't allow me to actually view the folder structure of my web, it's something more like creating a blog using blogspot by google or similar web apps. The problem is that I want...