Best Logic to implement comparison of two arrays

2018-04-14 15:47 Vignesh Kumar imported from Stackoverflow

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 and arr2. Then do a set_symmetric_difference on them. This will effectively run in linear time. Then create two sets out of them, say set1 and set2.

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 in set2. Likewise do for arr2 as well and remove the element when necessary.

This can be done in O(n²). 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 the arr2 by doing a binary search. Then the time complexity may shoot up to O(n² log(n)).

See also questions close to this topic

How to use maple to test if an expression is rational?
Is it possible to use maple to test whether not an expression involving symbolic variables is rational?

As a simple example, I'd like to declare that x and y rationals then have maple confirm that x*x+y is also rational.

Here's what I'm trying so far, and I'm confused by the results, so I fear I do not understand the is and assume functions.
```
assume(x,rational);
assume(y,rational);
assume(z,rational);
```
Then testing the sum x+y seems to work:
```
is(x+y,rational);
```
outputs:
```
                          true
```
But the full expression does not worK:
```
is(x*x+z,rational);
```
outputs:
```
                          FAIL
```
I'm further confused that if I write:
```
is(sqrt(x),irrational);
```
the answer is:
```
                          false
```
But sometimes sqrt(x) will be irrational when x is rational (e.g., x=2). What's going on here?

How can I use maple to determine if a (complex) expression involving symbolic declared-rational variables is rational?

Date Validation using JS

When I am trying to validate a date, it can be either: validity, without validity, revoked, or invalid validity.

When I put the endDate as today's date validity() should return true, but instead revoked() does. I don't understand why.

today = moment(new Date());

I created 4 methods:

withoutValidity = () => startDate  > today;

invalidVality = () =>
    !this.withoutValidty() &&
    !startDate  && (!startDate  && !endDate)) ||
    (startDate  && endDate && endDate < startDate );

validity = () =>
    (!this.invalidVality () &&
      !this. withoutValidity () &&
      (startDate  &&
        !endDate &&
        startDate  <= this.today )) ||
    (startDate  &&
      endDate &&
      startDate  < this.today  &&
      endDate >= this.today );

revoked = () =>
    !this.invalidVality () &&
    startDate  &&
    endDate &&
    endDate < this.today ;

Array trying to get first, me and one above / below optimisation

I have data containing scores of people in leagues, and I am trying to get a result set of 4 for each league. If I am in the top 4, then it returns the top 4, but if I am not, then it should return 1st place, and the one above and below me, and me.

currently I have a 1st through to 4th parameter, that I populate, which then gets added to the returned array. Currently this code is working, though, if there is less than 4 in the league, its not correct, and also not working if i'm in the top 4.

My concern is more, I have a big unwieldy if else if block, there must be a neater / better approach than what I have done? Am I missing something?

Input Data:

array(35) {
  [0]=>
  array(11) {
    ["groupID"]=>
    int(1)
    ["groupName"]=>
    string(6) "A Group"
    ["driverID"]=>
    int(1)
    ["screenName"]=>
    string(12) "MrBlog"
    ["score"]=>
    int(9231)
    ["position"]=>
    float(1)
  },
{
    ["groupID"]=>
    int(1)
    ["groupName"]=>
    string(6) "A Group"
    ["driverID"]=>
    int(2)
    ["screenName"]=>
    string(12) "Saxon"
    ["score"]=>
    int(7276)
    ["position"]=>
    float(2)
  },
{
    ["groupID"]=>
    int(4)
    ["groupName"]=>
    string(6) "All Drivers"
    ["driverID"]=>
    int(10)
    ["screenName"]=>
    string(12) "Anonymous"
    ["score"]=>
    int(9897)
    ["position"]=>
    float(1)
  },
{
    ["groupID"]=>
    int(4)
    ["groupName"]=>
    string(6) "All Drivers"
    ["driverID"]=>
    int(17)
    ["screenName"]=>
    string(12) "Joe"
    ["score"]=>
    int(9777)
    ["position"]=>
    float(2)
  },
{
    ["groupID"]=>
    int(4)
    ["groupName"]=>
    string(6) "All Drivers"
    ["driverID"]=>
    int(7)
    ["screenName"]=>
    string(12) "Wavey Davey"
    ["score"]=>
    int(9564)
    ["position"]=>
    float(3)
  },
{
    ["groupID"]=>
    int(4)
    ["groupName"]=>
    string(6) "All Drivers"
    ["driverID"]=>
    int(29)
    ["screenName"]=>
    string(12) "White Van Man"
    ["score"]=>
    int(9432)
    ["position"]=>
    float(4)
  },
{
    ["groupID"]=>
    int(4)
    ["groupName"]=>
    string(6) "All Drivers"
    ["driverID"]=>
    int(4)
    ["screenName"]=>
    string(12) "Dan"
    ["score"]=>
    int(9278)
    ["position"]=>
    float(5)
  },
{
    ["groupID"]=>
    int(4)
    ["groupName"]=>
    string(6) "All Drivers"
    ["driverID"]=>
    int(1)
    ["screenName"]=>
    string(12) "MrBlog"
    ["score"]=>
    int(9231)
    ["position"]=>
    float(6)
  },
{
    ["groupID"]=>
    int(4)
    ["groupName"]=>
    string(6) "All Drivers"
    ["driverID"]=>
    int(24)
    ["screenName"]=>
    string(12) "Big Dan"
    ["score"]=>
    int(8742)
    ["position"]=>
    float(7)
  },
{
    ["groupID"]=>
    int(4)
    ["groupName"]=>
    string(6) "All Drivers"
    ["driverID"]=>
    int(2)
    ["screenName"]=>
    string(12) "Saxon"
    ["score"]=>
    int(7276)
    ["position"]=>
    float(8)
  }

Desired Output:

"1": {
        "members": 2,
        "groupName": "A Group",
        "score": [
            {
                "groupID": 1,
                "driverID": 1,
                "screenName": "MrBlog",
                "score": 9231,
                "position": 1
            },
            {
                "groupID": 1,
                "driverID": 2,
                "screenName": "Saxon",
                "score": 7276,
                "position": 2
            }
        ]
    },
"4": {
        "members": 7,
        "groupName": "All Drivers",
        "score": [
            {
                "groupID": 4,
                "driverID": 10,
                "screenName": "Anonymous",
                "score": 9897,
                "position": 1
            },
            {
                "groupID": 4,
                "driverID": 17,
                "screenName": "Joe",
                "score": 9777,
                "position": 2
            },
            {
                "groupID": 4,
                "driverID": 7,
                "screenName": "Wavey Davey",
                "score": 9564,
                "position": 3
            },
            {
                "groupID": 4,
                "driverID": 29,
                "screenName": "White Van Man",
                "score": 9432,
                "position": 4
            },
            {
                "groupID": 4,
                "driverID": 4,
                "screenName": "Dan",
                "score": 9278,
                "position": 5
            },
            {
                "groupID": 4,
                "driverID": 1,
                "screenName": "MrBlog",
                "score": 9231,
                "position": 6
            },
            {
                "groupID": 4,
                "driverID": 24,
                "screenName": "Big Dan",
                "score": 8742,
                "position": 7
            },
            {
                "groupID": 4,
                "driverID": 2,
                "screenName": "Saxon",
                "score": 7276,
                "position": 8
            }       
        ]       
    }

Code:

foreach ($leagues as $aLeagueID => $aLeague) {
        $return[$aLeague['groupID']]['members'] = $aLeague['position'];
        // New group ID?
        if ($groupID != $aLeague['groupID']) {
            // get our position
            if($aLeague['_driverID'] == $driverID)
                $myPos = $aLeague['position'];

            $return[$aLeague['groupID']]['groupName'] = $aLeague['groupName'];
            $return[$aLeague['groupID']]['score'][] = $aLeague;

        } else if ($groupID == $aLeague['groupID']) {
            if($aLeague['_driverID'] == $driverID)
                $myPos = $aLeague['position'];

            if ($stop) {
                $fourth = $aLeague;
                $return[$aLeague['groupID']]['score'][] = $first;
                $return[$aLeague['groupID']]['score'][] = $second;
                $return[$aLeague['groupID']]['score'][] = $third;
                $return[$aLeague['groupID']]['score'][] = $fourth;
                $stop = false;
                $myPos = 0;
            }

            // If we dont know our position yet
            else if($myPos == 0 && $aLeague['position'] <= 4) {
                $second = $third;
                $third = $fourth;
                $fourth = $aLeague;
                #$return[$aLeague['groupID']]['score'][] = $prev;
                #$return[$aLeague['groupID']]['score'][] = $aLeague;
            }

            // IF we are in the top 4
            else if($myPos <= 4 && $aLeague['position'] <= 4) {
                $second = $third;
                $third = $fourth;
                $fourth = $aLeague;
            }

            // else show first place and our position + / - 1
            else if($myPos >= 5) {
                $stop = true;
                $second = $prev;
                $third = $aLeague;
            }
            $prev = $aLeague;
        }
        $groupID = $aLeague['groupID'];
    }

Asociate existing product variants with new generated variants

I want to create product variations for my own ecommerce website.

I have a probem when i want to know which variant is existing and which one is new, to insert or update it.

To create variants i use the following php function:

<pre>
function possible_combos($groups, $prefix='') {
    $result = array();
    $group = array_shift($groups);

    foreach($group as $selected) {
        if($groups) {
            $result = array_merge($result, possible_combos2($groups, $prefix .$selected.', '));
        } else {
            $result[] = [
                'combination_string' => $prefix.$selected,
            ];
        }
    }
    return $result;
}
</pre>

With the following array for build:

<pre>
Array
(
    [Color] => Array
        (
            [0] => Green
            [1] => Red
        )

    [Storage] => Array
        (
            [0] => 128 GB
            [1] => 256 GB
        )

)
</pre>

Color: Green, Red Storage: 128 GB, 256 GB

And the result for this is :

<pre>
Array
(
    [0] => Array
        (
            [combination_string] => Green, 128 GB
        )

    [1] => Array
        (
            [combination_string] => Green, 256 GB
        )

    [2] => Array
        (
            [combination_string] => Red, 128 GB
        )

    [3] => Array
        (
            [combination_string] => Red, 256 GB
        )

)
</pre>

All works good on add mode, the problem is on edit mode.

For each variant combination i create a new product using 'Parent_id';

So in edit page a have this:

<pre>
Array
(
    [0] => Array
        (
            [product_id] => 1,
            [combination_string] => Green, 128 GB
        )

    [1] => Array
        (
        [product_id] => 2,
            [combination_string] => Green, 256 GB
        )

    [2] => Array
        (
            [product_id] => 3,
            [combination_string] => Red, 128 GB
        )

    [3] => Array
        (
            [product_id] => 4,
            [combination_string] => Red, 256 GB
        )

)
</pre>

If i add new attribute for combination for example:

Size: Big

<pre>
Array
(
    [Color] => Array
        (
            [0] => Green
            [1] => Red
        )

    [Storage] => Array
        (
            [0] => 128 GB
            [1] => 256 GB
        )
    [Size] => Array
        (
            [0] => Big
        )

)
</pre>

For this case i want to return

<pre>
Array
(
    [0] => Array
        (
            [product_id] => 1,
            [combination_string] => Green, 128 GB, Big
        )

    [1] => Array
        (
            [product_id] => 2,
            [combination_string] => Green, 256 GB, Big
        )

    [2] => Array
        (
            [product_id] => 3,
            [combination_string] => Red, 128 GB, Big
        )

    [3] => Array
        (
            [product_id] => 4,
            [combination_string] => Red, 256 GB, Big
        )
)
</pre>

And ... if i add a new value for attribute Storage 512 GB fro example: The result should looks like:

<pre>
Array
(
    [0] => Array
        (
            [product_id] => 1,
            [combination_string] => Green, 128 GB, Big
        )

    [1] => Array
        (
            [product_id] => 2,
            [combination_string] => Green, 256 GB, Big
        )

    [2] => Array
        (
            [combination_string] => Green, 512 GB, Big
        )

    [3] => Array
        (
            [product_id] => 3,
            [combination_string] => Red, 128 GB, Big
        )

    [4] => Array
        (
            [product_id] => 4,
            [combination_string] => Red, 256 GB, Big
        )

    [5] => Array
        (
            [combination_string] => Red, 512 GB, Big
        )

)
</pre>

No product_id for existing combs.

I don't know if i'm clear with this, but i can give more info if needed.

EDIT for @PHPnoob

Python Get Random Unique N Pairs
Say I have a range(1, n + 1). I want to get m unique pairs.

What I found is, if the number of pairs is close to n(n-1)/2 (maxiumum number of pairs), one can't simply generate random pairs everytime because they will start overriding eachother. I'm looking for a somewhat lazy solution, that will be very efficient (in Python's world).

My attempt so far:
```
def get_input(n, m):

    res = str(n) + "\n" + str(m) + "\n"
    buffet = range(1, n + 1)
    points = set()

    while len(points) < m:
        x, y = random.sample(buffet, 2)
        points.add((x, y)) if x > y else points.add((y, x)) # meeh

    for (x, y) in points:
        res += "%d %d\n" % (x, y);

    return res
```
Custom grouping for all possible groups in a dataframe with missing values
I have a dataframe which represents a set of products. I need to find all duplicate products within these products. If products have same product_type,color and size -> they are duplicates. This would be an easy df.groupby('product_type','color','size') line if I did not have a problem: some values are missing. Now I have to find all possible groups of products that might be duplicates between themselves. This means that some elements can appear in multiple groups.

Let me illustrate:
```
import pandas as pd


def main():
    df = pd.DataFrame({'product_id': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
                       'product_type': ['shirt', 'shirt', 'shirt', 'shirt', 'shirt', 'hat', 'hat', 'hat', 'hat', 'hat', 'hat', ],
                       'color': [None, None, None, 'red', 'blue', None, 'blue', 'blue', 'blue', 'red', 'red', ],
                       'size': [None, 's', 'xl', None, None, 's', None, 's', 'xl', None, 'xl', ],
                       })
    print df   

if __name__ == '__main__':
    main()
```
for this dataframe:

I need this result - list of possibly duplicate products for each possible group (take only the biggest super groups):

So for example, lets take "shirt" with id=1 this product does not have color or size so he can appear in a possible "duplicates group" together with shirt #2 (which has size "s" but does not have color) and shirt #4 (which has color "red" but does not have size). So these three shirts (1,2,4) are possibly duplicates that same color "red" and size "s".

I tried to implement it by looping through all possible combinations of missing values but it feels wrong and complex.

Is there a way to get the desired result?
Perfect hashing for permutations
Consider the following list of permutations of {0,1,2,3,4,5,6,*,*,*} as generated with ordinary backtracking:
```
    Index  Permutation
    1.     0123456***
    2.     012345*6**
    3.     012345**6*
    4.     012345***6
    5.     0123465***
    ...
    60480. ***6543210
```
Is it there an O(1) function which, for any permutation gives back the permutation's index?
find multiple words by letters from input in a text file
I'm new to python (more or less) and am struggling with one task, where I need to enter one sentence either by user input or whatever way is better/easier (preferably long one, e.g. "We met each other yesterday", but doesn't matter much). Then iterate through all the letters, find all possible letter combinations of said words and find matches with them in a file which consists of thousands of words (approx. 4 mb file), each word is on a separate line, like this:
```
fun
dog
whatever
coffee
cup
```
I went with itertools.permutations and tried going with set and intersection. Without further ado, here's my code thus far:
```
from itertools import permutations


def alpha_check():
    """check whether a sentence consists of only letters"""
    sentence = str.lower(input('Type something in: '))
    while not sentence.replace(' ', '').isalpha():
        print(f"You typed in {sentence!s}. Only letters A-Z allowed, not case sensitive.")
        sentence = input("Please, type something again: ")
    return sentence


def file_iter(sentence: str):

    my_set = set(line.strip() for line in open('file.txt'))
    word_list = set(sentence.split())
    for x in word_list:
        temp = list(permutations(x))
        for f in temp:
            print(''.join(f), end=' ') # gets rid of commas etc.
        inters = my_set.intersection(f)
        return inters


print(file_iter(alpha_check()))
```
Alpha check doesn't interest me at the moment, I only would like to get this monster to work. Currently it outputs something like this, granted I enter "map lake" after being prompted:
```
Type something in: map lake
lake laek lkae lkea leak leka alke alek akle akel aelk aekl klae klea kale kael kela keal elak elka ealk eakl ekla ekal {'l', 'e', 'a', 'k'}
```
and expected output would be map and lake permutations and then found intersections within input and the file. I searched a lot on SO and google. Found a lot of info, but I couldn't make this work anyway. This is the best one I came up with. Also I'm not asking for a complete solution, just for help to understand what I'm doing wrong and how can I solve this. Clues, tips, etc. Thank you!
Calculate No of ways
Suppose i have 4 2's and 2 1's. In how many ways we can form a no contains (4 + 2)digits such that all are different and each no contain at least 2 2's together.

I tried in the following way- Suppose a=4 and b=2
1. total no of ways= (6)!/(4!*2!)= 15 ways
2. Now according to question at least 2 2's should be together so i assumed 2 2's a single quantity now i have a=3 and b=2 which gives 10 ways
But the correct answer will be 15 because whatever be the arrangement at least 2 2's will always occur together.

Example for more clarification-

if a=2 and b=1

221,212,122 3 ways possible

I just want to know how to find the formula for this type of questions.

Related questions

Best Logic to implement comparison of two arrays

1 answer

See also questions close to this topic