Best Logic to implement comparison of two arrays
I have two arrays -arr 1 and arr 2, here both the arrays will have some common items and many uncommon items, first the common items should be removed from both the arrays.
therefore for each uncommon item in arr 1 may probably be a sum of two or more values in arr 2 or vice versa.if the sum is found the values must be removed from the respective arrays. Finally the output should only be the unmatched values on both the arrays
I need a logic where i can do this calculation in much faster way.
1 answer
-
answered 2018-04-14 19:11
Raghav
I'm not going to give out the code that implements your logic but rather I would be happy to point you in the right direction.
I code in C++, so I'm gonna answer with respect to that. If you want a different language, I'm sure you can freely do so.
To remove the common elements:
You first sort the arrays
arr1
andarr2
. Then do a set_symmetric_difference on them. This will effectively run in linear time. Then create two sets out of them, sayset1
andset2
.To remove pairs that sum up to an element in the other array
For this, you need to loop through all the possible pairs of elements in
arr1
and check if this sum of this pair exists inset2
. Likewise do forarr2
as well and remove the element when necessary.This can be done in O(n2). If you don't want to create the extra sets, you can always trade performance for memory, by just looping through the pairs of
arr1
and checking for the sum in thearr2
by doing a binary search. Then the time complexity may shoot up to O(n2 log(n)).
See also questions close to this topic
-
How to compare a string in Reactjs to a list of strings and display the result
I have an input field in one of my React Component which will take the inputs which will be email id's of users. I have a list of email id's saved in the server.So,when I type something in the input field, I want to have the suggestion of the email id's to appear below the input field from the currently existing list.So, what I have come up with is that I should use the localeCompare(string) function from javascript where I will have to use some condition like :
input_string.localeCompare(existing_string)
So,is this the correct way or is there some other way to proceed? And do I have to create a new component for displaying the suggestion below the input?
NOTE: I want my search to work in a similar manner like how google search works when we type some input in the search bar, the suggestion similar to the search string appears below.
-
multiple checkbox logic with search function
I have 3 checkboxes that I will be using for search options. Now the user can select any number of them for searching. My question is:
Is there a more convenient way to write out the logic for the search, rather than doing an if/else or boolean check for for every combination?
3 checkboxes isn't too bad, but I could see an issue with say 5+ checkboxes. Would there be a better way to implement a search function with multiple options?This is what I am currently doing:
public ViewResult Index(string sortOrder, string currentFilter, string searchString, int? page, string searchFilter) { ViewBag.CurrentSort = sortOrder; ViewBag.NameSortParm = String.IsNullOrEmpty(sortOrder) ? "year" : ""; if (searchString != null) { page = 1; } else { searchString = currentFilter; } ViewBag.CurrentFilter = searchString; ViewBag.CurrentFilterSelection = searchFilter; var resolutions = from c in db.AllResolutions select c; if (!String.IsNullOrEmpty(searchString)) { resolutions = resolutions.Where(c => c.ResolutionYear.Contains(searchString) || c.ResolutionTextShort.Contains(searchString) || c.ResDescription.Contains(searchString)); } switch (sortOrder) { case "date": resolutions = resolutions.OrderByDescending(c => c.ResDate); break; case "year": resolutions = resolutions.OrderByDescending(c => c.ResolutionYear); break; case "number": resolutions = resolutions.OrderByDescending(c => c.ResolutionNumber); break; default: resolutions = resolutions.OrderBy(c => c.ResolutionYear).ThenBy(c => c.ResolutionNumber); break; } int pageSize = 25; int pageNumber = (page ?? 1); return View(resolutions.ToPagedList(pageNumber, pageSize)); }
I am currently searching the database in 3 separate columns and returning the results that contain
searchString
. I would like to be able to have the user select whether or not they want to limit the columns they are searching forie: I want to search for all 2018 resolutions or I want to search all 2018 resolutions with the keyword here
-
Herbrand vs FOL
Q1] Is there any example of formula in first order logic that has a model but not an Herbrand model?
Q2]what are the differences BETWEEN :
Models of P(a) when the signature is {P,a,b}:
Herbrand Models of P(a) when the signature is {P,a}:
Herbrand Models of P(a) when the signature is {P,a,b}:
Thank you
-
How to iterate a YAML file to give all possible combinations from items in different lists in PYTHON
I have a YAML document with sequences like this
--- One: - a - b - c Two: - d - e Three: - f - g - h - i
I need to get all possible combinations of the elements taken from each list one at a time, only one element at every instance from the list and all list must be used.
I need to do this is python.
Until now, I can print the YAML file using:
#!/usr/bin/env python import yaml with open("parameters.yaml", 'r') as stream: try: print(yaml.load(stream)) except yaml.YAMLError as exc: print(exc)
-
Scala Match Error Case Prevention
I have this function that basically combines Lists of Lists, but you can ignore that, for that is not the issue:
def combinationList[T](ls:List[List[List[T]]]) : List[List[List[T]]] = ls match { case head :: Nil => for(x <- head) yield List(x) case head :: tail :: Nil => for { hl <- head tl <- tail if tl.forall(te => !hl.contains(te)) } yield List(hl, tl) }
This works when I have a List with two sub-lists but it fails to match when I have more than two. I obviously need to use this function recursively to make a more general case, and I've tried to add the following case at the end of the function:
case _ => combinationList(combinationList(ls.tail):::List(ls.head))
The logic here is that, imagine we have a List with 3 sub lists, like so:
List ( List(1), List(2), List(3) )
When I first call the fucntion, it will only match in the last case I mentioned, so, I will call the function with the list's tail (List(2), List(3)), and, in that call, it will match for the second case (head::tail::Nil), then, when it returns, it should be a single List and when added to the list's original head (List(1)::List(2+3)) it should match on the second condition. The issue here is that the return is not a single list (List(2+3)) but rather yet another combination of lists (List(2), List(3)) so it will obviously recursive forever. I've tried to modify the case like this:
combinationList(List(combinationList(ls.tail)):::List(ls.head))
But it gives me an error ("The expression of type List[List[List[Any]]] doesn't conform to type List[List[List[T]]]"
Any ideas? Thanks.
[EDIT:] This function's purpose is to combine lists in such manner:
simplified input: List( List(1,2), List(3), List(4)) simplified output: List( List(1,3,4), List(2,3,4)) real input: List( List(List(1), List(3), List(4)), List(List(2), List(3), List(4)) ) real expected output: List( List(List(1), List(2)), List(List(1), List(3)), List(List(1), List(4)), List(List(3), List(2)), List(List(3), List(4)), List(List(4), List(2)), List(List(4), List(3)) )
With the real input, the function is able to return the expected output, it only fails when another sub list is added, like so:
input: List( List(List(1), List(2)), List(List(3), List(4)), List(List(5)) )
The expected output here, would be:
expected output: List( List(List(1), List(3), List(5)), List(List(1), List(4), List(5)), List(List(2), List(3), List(5)), List(List(2), List(4), List(5)) )
So, the order of the combinations don't really matter much, I can head:::tail or tail:::head, it's the same thing.
-
How to show all combinations of picking 3 balls in a jar of 20 balls and 1 ball in two other jars of 5 balls
I know how to return the list of all possible combinations of picking 3 balls in a jar of 20 possible balls:
list(itertools.combinations(range(1,21),3))
But what if I have two balls from two jars ( First I will pick a ball in a jar of 5 balls and do it again in another jar), How can I get the possible list of all combinations?
-
Generating Permutations without Repetition Using Index
Suppose you have a sequence of numbers, e.g., {1, 2, 3, 4, 5). from which you want all the permutations without repetition, choosing two elements.
Thus, {1,2}, {1,3}, {1,4}, {1,5}, {2,1}, {2,3}, {2,4} ...
Given an index of the permutation number, e.g., the 6th permutation, is there some easy approach to calculate what that permutation (here {2,4} using zero indexing) looks like?
I see approaches for combinations like: https://math.stackexchange.com/questions/1368526/fast-way-to-get-a-combination-given-its-position-in-reverse-lexicographic-or
I am looking for something similar for my problem. I am using C++.
I have looked at Gray Codes, Lermer Codes, Combinadics, Factoradics, etc. but none of these seem quite right.
Thanks for any help.
-
Scheduling a 16-team 1v1 competition with 6 different game types
I've been given the task of creating the schedule for a company's team competition. Initially I thought this would be pretty trivial, but I'm having some trouble coming up with a valid solution. Here are the facts that need to be met:
- There are 16 teams
- There are 6 different 1v1 games to be played
- Each team must play all 6 game types
- No two teams can play each other twice
- There are 8 available "rounds" or "time slots" that a team can play a game. This means a team will have two rounds where they rest and play no games
- No game type may be played twice in the same round
This isn't a round robin since all teams will not play each other. It's kind of similar to a Swiss Tournament, but with the constraint of having multiple game types that all teams must play. I'm struggling to figure out the correct algorithm to determine this schedule and any help or information leading to a solution would be great.
-
Get all "Permutations" of a tree with respect to the nodes state
I have a tree like structure of objects and want to "resolve" them into list of new trees. It basically describes a building process. To make product A you need to have product B and C in amount of x. You can either buy product B and C or build one of them, or both, yourself if it has sub inputs. Inputs can be 0 - n.
Both "states" (build and produce) have different costs and requirements and I want to create a list of trees, with each tree representing a possible combination and the whole list representing all possible combinations.
I've tried permutations but that didn't really work, I think, because every node has two possible states and I do need the permutations only for every 'level'.
Any help would be much appreciated.
Example: Initial Configuration
A / \ B C / \ / \ D E F G
Possible combinations to make product A
(p) = produced (b) = bought
- A = B(b) + C(b)
- A = B(p) (D(b) + E(b)) + C(b)
- A = B(b) + C(p) (F(b) + C(b))
- A = B(p) (D(b) + E(b)) + C(p) (F(b) + G(b))
Example Code:
public class ProductionInfo { public string Name { get; set; } public List<ProductionInput> Inputs { get; set; } = new List<ProductionInput>(); } public class ProductionInput { public ProductionInput(ProductionInfo schematic = null, int requiredAmount = 0) { Schematic = schematic; RequiredAmount = requiredAmount; } public ProductionInfo Schematic { get; set; } public int RequiredAmount { get; set; } } public void CreateTest() { var a = new ProductionInfo() { Name = "A" }; var b = new ProductionInfo() { Name = "B" }; var c = new ProductionInfo() { Name = "C" }; var d = new ProductionInfo() { Name = "D" }; var e = new ProductionInfo() { Name = "E" }; var f = new ProductionInfo() { Name = "F" }; var g = new ProductionInfo() { Name = "G" }; var h = new ProductionInfo() { Name = "H" }; var j = new ProductionInfo() { Name = "J" }; var k = new ProductionInfo() { Name = "K" }; var l = new ProductionInfo() { Name = "L" }; a.Inputs.Add(new ProductionInput(b, 1)); a.Inputs.Add(new ProductionInput(c, 1)); b.Inputs.Add(new ProductionInput(d, 1)); b.Inputs.Add(new ProductionInput(e, 1)); c.Inputs.Add(new ProductionInput(f, 1)); c.Inputs.Add(new ProductionInput(g, 1)); d.Inputs.Add(new ProductionInput(h, 1)); e.Inputs.Add(new ProductionInput(j, 1)); f.Inputs.Add(new ProductionInput(k, 1)); g.Inputs.Add(new ProductionInput(l, 1)); }