|
I have a problem with my homework.
Description:
1. In the group of people we define the relationship: A does not like B. This relation is not symmetrical.
If there is a series of relationships A1 does not like A2, A2 does not like A3 ... Ak does not like A1,
all people in this cycle belong to one group of "disliking".
For the given pair specifying the relations, determine the maximum division
groups of "disliking". Provide complexity and justify the correctness of your solution.
2. There are some animosities in the group of naughty children. The preschool teacher decided to
set the children in a row. If A does not like B, he can not stand in a row in front of B (not to throw papers in it).
a) Specify if a group of children can be set in one row.
b) If not, enter the minimum number of rows to set children in above configuration.
Provide complexity and justify the correctness of your solution.
c) Enter the minimum number of rows necessary to set the children, if:
Child A does not like child B, it must stand in a row with a lower number.
I know that in the first task I have to find strongly connected components. Actually I did it using Tarjan's algorithm in PHP implementations. I wonder that is it correct approach and how to provide complexity of my solution. Unfortunately I don't have any information how to solve second task. Maybe someone has an idea and could give a clue.
Thanks for advice
Code of first task:
const GROUPS_COUNTER = 10;
const MIN_ASCII = 65;
const MAX_ASCII = 69;
function generateGroups($n) {
$matrix = [];
$exist = [];
echo "************************\n";
for ($i = 0; $i < $n; $i++) {
$a = chr(rand(MIN_ASCII, MAX_ASCII));
$b = chr(rand(MIN_ASCII, MAX_ASCII));
if ($a == $b || isset($exist[$a][$b]) || isset($exist[$b][$a])) {
$i--;
continue;
}
$matrix[$i][0] = $a;
$matrix[$i][1] = $b;
$exist[$a][$b] = true;
echo $a . " " . $b . "\n";
}
echo "************************\n";
return $matrix;
}
function findGroups($groups) {
$dislikeList = [];
$checked = [];
foreach ($groups as $groupParent) {
if (isset($checked[$groupParent[0]])) {
continue;
}
$groupChildList = [];
foreach ($groups as $groupChild) {
if ($groupParent[0] == $groupChild[0]) {
array_push($groupChildList, $groupChild[1]);
}
}
echo $groupParent[0] . " => " . implode(", ", $groupChildList) . "\n";
$dislikeList[$groupParent[0]] = $groupChildList;
$checked[$groupParent[0]] = true;
}
echo "************************\n";
return $dislikeList;
}
function phpTarjanEntry($groups) {
global $cycles;
global $marked;
global $markedStack;
global $pointStack;
$cycles = array();
$marked = array();
$markedStack = array();
$pointStack = array();
$marked = array();
foreach ($groups as $key => $value) {
$marked[$key] = FALSE;
}
foreach ($groups as $key => $value) {
phpTarjan($key, $key);
while (!empty($markedStack)) {
$marked[array_pop($markedStack)] = FALSE;
}
}
$cycles = array_keys($cycles);
return $cycles;
}
function phpTarjan($s, $v) {
global $G;
global $cycles;
global $marked;
global $markedStack;
global $pointStack;
$f = FALSE;
$pointStack[] = $v;
$marked[$v] = TRUE;
$markedStack[] = $v;
foreach ($G[$v] as $w) {
if ($w < $s) {
$G[$w] = array();
} else if ($w == $s) {
$cycles[implode('|', $pointStack)] = TRUE;
$f = TRUE;
} else if (isset($marked[$w]) && $marked[$w] === FALSE) {
$g = phpTarjan($s, $w);
if (!empty($f) OR ! empty($g)) {
$f = TRUE;
}
}
}
if ($f === TRUE) {
while (end($markedStack) != $v) {
$marked[array_pop($markedStack)] = FALSE;
}
array_pop($markedStack);
$marked[$v] = FALSE;
}
array_pop($pointStack);
return $f;
}
$mixGroups = generateGroups(GROUPS_COUNTER);
$res = findGroups($mixGroups);
$G = $res;
$cycles = phpTarjanEntry($res);
echo '<p>Cycles found: ' . count($cycles);
print_r($cycles);
|
|
|
|
|
Hi, everyone, I am not a software developer or coder, but I have a very interesting question for you!
I work for a cargo airline, our cargo area inside aircraft is a cylinder with Radius of 30 inches and length of 332 inches, with a flat floor on bottom of 44 inches.
Now, here is the question,
I have a customer have many boxes with dimension of x*y*z,
lets say the box dimension is 24*18*14 and I want to know the max amount of boxes I can put in the aircraft, and how?
|
|
|
|
|
Member 13644847 wrote: I am not a software developer or coder, but I have a very interesting question for you! No, of course not.
See knapsack problem - Google Search[^]
|
|
|
|
|
Member 13644847 wrote: I am not a software developer or coder,...I want to know the max amount of boxes I can put in the aircraft, and how?
Then hire a mathematician. Or even a consulting company.
|
|
|
|
|
Hi,
there is no straightforward way to solve this problem. Instead, you should try different schemes and calculate how many boxes you can store in each of them, then pick the optimum.
Assuming box dimension d3 * d2 * d1 with d3>=d2>=d1, boxes are allowed to be rotated in any way and can be stacked all the way to the top, and assuming the cargo room is much longer than its diameter, this is what I would do in a first attempt, and I expect it to get really close to the absolute optimum:
- work one layer at a time, i.e. the problem gets reduced from a 3D problem to a number of much easier 2D problems;
- the first layer would have thickness d1;
- now fit as many boxes as possible in that one layer; obvious choices would be: all in long direction, or all in cross direction (the former normally being better than the latter);
- first refinement: if length of cargo room isn't a multiple of d3, you might be slightly better of splitting it (per layer!) in two parts, a big part using long direction, the remainder using cross direction;
- once the maximum is found for that layer proceed to the next layer again using thickness d1; note that the second layer has the same length but a larger width than the first layer, hence the result could be a larger number of boxes;
- continue designing your layers with thickness d1 until you reach the 45 degree angle, then the layer height should equal d2 (instead of d1), everything else remains the same;
- and once you reach the 135 degree angle, switch back to the original scheme (thickness d1).
Second refinement, somewhat more difficult: as you will probably not reach exactly 45 degrees, you might consider one less layer with thickness d1; similarly you might consider one less layer with thickness d2. This yields four cases to consider, there is a possibility one of them gives you one more layer in total, and a better solution.
Final remark: it is not sure that orthogonal filling yields the optimum, the optimum could consist of arches and other schemes that might not be practical at all, I would guess you won't care for those...
modified 8-Feb-18 21:36pm.
|
|
|
|
|
i am not able to figure out why linspace not able to create equal intervals till the value of machine epsilon
here is the code....
from numpy import *
import sys
import numpy as np
x=1
epsilon=sys.float_info.epsilon/2.0
# machine epsilon
h = np.linspace(1,epsilon,1000)
e1= (((sin(x)- sin(x-h))/h-cos(x))/cos(x)) #realtive error in first order
e2= (((sin(x-2*h)-4*sin(x-h)+3*sin(x))/(2*h)-cos(x))/cos(x)) #realtive error in second order
e3= (((2*sin(x+h)+3*sin(x)-6*sin(x-h)+sin(x-2*h))/(6*h)-cos(x))/cos(x))#realtive error in third order
e4 = (((-sin(x-3*h)+6*sin(x-2*h)-18*sin(x-h)+10*sin(x)+3*sin(x+h))/(12*h)-cos(x))/cos(x))#realtive error in fourth order
print(h)
import matplotlib.pyplot as plt
plt.plot(h,e1,'-b',lw=3)
plt.plot(h,e2,'-g',lw=3)
plt.plot(h,e3,'-m',lw=3)
plt.plot(h,e4,'-r',lw=3)
plt.xscale('log')
plt.yscale('log')
plt.xlabel('h')
plt.ylabel('Relative error')
plt.legend(['first order','second order','third order','fourth order'])
plt.title('Effect of order of accuracy on the numerical differentiation')
plt.show()
|
|
|
|
|
Works on my machine. However, since the samples are uniformly spaced, all but the last of them are extremely far from epsilon in a relative sense.
|
|
|
|
|
Hi, to be able to validate a cart I need to compare what is in the cart against the min and max limitations of one or more product categories.
In the example below, to be valid, my cart must have at least one product from Cat A and a maximum of 3 products in total from Cat A and Cat B.
Cat A > min=1 max=3
Cat B > min=0 max=2
What logic can I apply to tackle this (pref in C#) ?
Thanks for your inputs !
|
|
|
|
|
I think you need a litter box for all those cat products.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Very helpful thanks !
|
|
|
|
|
Member 13585107 wrote: What logic can I apply to tackle this How about comparing the values?
|
|
|
|
|
NOAA's National Centers for Environmental Information collects global climate data and aggregates this data to provide information on climate trends and variability. One product they offer is a monthly regional analysis. The following table gives "anomaly" data by continent for January 2017. "Anomaly" means the value is the temperature difference from the average temperature from years 1910–2000.
Continent Anomaly (C)
North America 3.18
South America 1.36
Europe -0.12
Africa 0.53
Asia 1.92
Oceania 0.98
Assignment task:
Your task is to develop an algorithm that would sort data such as these from least to greatest. Specifically, given an unsorted set of N decimal values, your algorithm should sort them to give an answer of the sorted data. For this set of N = 6, your algorithm should produce:
-0.12
0.53
0.98
1.36
1.92
3.18
Execute your algorithm for a different set of data, such as a subset of the given data, data you make up, or another month's climate data, such as February 2017: https://www.ncdc.noaa.gov/sotc/global-regions/201702
Does your algorithm work for any N? Have you thought of corner cases it might need to handle, such as N = 0 or N = 1?
|
|
|
|
|
Do you know the difference between "help" and "I did nothing; someone do it for me"?
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Member 13567142 wrote: Your task ... should you decide to accept.
|
|
|
|
|
An algorithm that would sort data such as these from least to greatest, specifically given an unsorted set of N decimal values, and the algorithm should sort them give an answer of the sorted data for this set of N=6
|
|
|
|
|
Your homework is set to test what you know, not how good you are at begging strangers on the internet to do your work for you.
Try it yourself, and you'll probably find it's not as hard as you think. After all, it will be based on the topics you have recently covered in your course.
If you genuinely don't know where to start, then talk to your teacher.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
The following table gives "anomaly" data by continent for January 2017. "Anomaly" means the value is the temperature difference from the average temperature from years 1910–2000.
Continent Anomaly (C)
North America 3.18
South America 1.36
Europe -0.12
Africa 0.53
Asia 1.92
Oceania 0.98
Assignment task:
Your task is to develop an algorithm that would sort data such as these from least to greatest. Specifically, given an unsorted set of N decimal values, your algorithm should sort them to give an answer of the sorted data. For this set of N = 6, your algorithm should produce:
-0.12
0.53
0.98
1.36
1.92
3.18
Execute your algorithm for a different set of data, such as a subset of the given data, data you make up, or another month's climate data, such as February 2017: https://www.ncdc.noaa.gov/sotc/global-regions/201702
Does your algorithm work for any N? Have you thought of corner cases it might need to handle, such as N = 0 or N = 1?
|
|
|
|
|
No, we're not doing your homework for you.
|
|
|
|
|
How can I find the number of permutation of different types of objects?Can anyone suggest the algorithm for me?thank you!
example: There is 5 walls. I have 5 cans of Yellow paint, 3 cans of Red paint and 2 cans of Blue paint.How many possible painting solutions do I have?
|
|
|
|
|
|
Hi,
you would need some algorithm to enumerate all possible permutations; you don't need an algorithm to find the number of permutations, you only need a formula (it is n! ) and a simple loop for n (different) items.
And there's an infinite number of ways to paint anything with three kinds of paint...
|
|
|
|
|
Hi everybody, i'm developing a Modified Compress Sparse Row Matrix Class (in C++, but i think this is not important for the algorithm) you can read a short explanation of the method here I wrote the constructor as follow :
template <typename T>
constexpr MCSRmatrix<T>::MCSRmatrix( std::initializer_list<std::initializer_list<T>> rows)
{
this->dim = rows.size();
auto _rows = *(rows.begin());
aa_.resize(dim+1);
ja_.resize(dim+1);
if(dim != _rows.size())
{
throw InvalidSizeException("Error in costructor! MCSR format require square matrix!");
}
itype w = 0 ;
ja_.at(w) = dim+2 ;
for(auto ii = rows.begin(), i=1; ii != rows.end() ; ++ii, i++)
{
for(auto ij = ii->begin(), j=1, elemCount = 0 ; ij != ii->end() ; ++ij, j++ )
{
if(i==j)
aa_[i-1] = *ij ;
else if( i != j && *ij != 0 )
{
ja_.push_back(j);
aa_.push_back(*ij);
elemCount++ ;
}
ja_[i] = ja_[i-1] + elemCount;
}
}
}
and it works well ! I also wrote a findIndex(i,j) method that return the value at i,j of the whole matrix and it works fine, so i'm able to print out the whole matrix using the operator overloading () who return 0 if in this position the element is zero otherwise the right value
template <typename T>
std::size_t constexpr MCSRmatrix<T>::findIndex(const itype row , const itype col) const noexcept
{
assert( row > 0 && row <= dim && col > 0 && col <= dim );
if(row == col)
{
return row-1;
}
int i = -1;
for(int i = ja_.at(row-1)-1 ; i < ja_.at(row)-1 ; i++ )
{
if( ja_.at(i) == col )
{
return i ;
}
}
return -1;
}
the operator is defined as :
template <typename T>
const T MCSRmatrix<T>::operator()(const itype r , const itype c) const noexcept
{
auto i = findIndex(r,c);
if( i != -1 && i < aa_.size() )
{
return aa_.at(i) ;
}
else
{
return 0.0 ;
}
}
Now I need to write an alghoritm that give 2 index of position is able to insert in the 2 vector the element in the right position could you help me about ?
I wrote this one but dosn't works fine !
template<typename T>
auto constexpr MCSRmatrix<T>::insertAt(itype row ,itype col , T elem) noexcept
{
if(elem == 0)
{
std::cerr << "zero element to insert ! Exit 1" << std::endl;
}
int index = findIndex(row,col);
if( index >= dim+1 || row == col)
{
aa_.at(index) = elem ;
}
else if(index == -1)
{
for(auto i=row; i< dim+1 ; i++)
{
ja_.at(i) += 1 ;
}
if(ja_.at(row) >= aa_.size() )
{
aa_.push_back(elem);
ja_.push_back(col);
}
else if ( ja_.at(row) < aa_.size() )
{
ja_.insert(ja_.begin() + dim + row , col );
aa_.insert(aa_.begin() + dim + row , elem);
}
}
}
I hope you give me a way to write down the correct way to inert element ! thanks in advance
P.S. itype is a typedef of std::size_t !
|
|
|
|
|
I am developing a project that is meant to improve feature smoothness in heightmaps that represent terrain from multiple maps at different resolutions from satellite imagery.
I know how to use the data in the maps to detect the shorelines. What I want to do however is turn shorelines into edges (lines) that do not intersect at all so that I can smooth them from the blocky look they have outside the USA where satellite resolution is not as good. Most of the time this is fairly straightforward but the lack of good resolution on some of the height maps may result in islands touching the coastline. I want to make sure that the coast on the island follows the outline of the island while the main coastline stays the main coastline. Basically I believe this would boil down to making sure they don't intersect. This area of programming is completely new to me. I want to understand the best algorithm for 'untangling' intersections when more than one coast line happens to touch.
|
|
|
|
|
A question arose here at work where they would like to find datagaps in timeline datasets. This can be from database or from images. (eg each 6 hours there's an image).
Basically they want a "pseudocode" function that would work across technologies.
in: at least an array of datetime stamps
out: a list of gaps in the list.
This is what I have so far (it's C type language, but no language in particular):
function FindGaps(DateTime dts_start, DateTime dts_end, int amount, string interval, Array list2check){
Array listreference<DateTime, boolean>;
for(DateTime dts = dts_start; dts < dts_end; dts += amount (interval)){
listreference.Add(dts, false);
}
for(int i = 0; i < list2check.length; i++){
if(KeyExists(listrefence, list2check[i])){
listrefence[list2check[i]]) = true;
}
}
return listrefence;
}
and some of my own thoughts:
problems/remarks:
* You cannot uniformally convert months, years, ... eg to milliseconds (january has different amount of milliseconds than february, ...)
* not all datasets have uniform progression (timegap difference between points)
* datasets passed should not be too large
* the key check should be on similar interval (minutes = minutes eg. 00:00 = 00:00, but 00:00 != 00:00:01)
* adding the fill value can also mark the gap as true / false / invalid eg.
* should you "remove" values that are in between gaps? eg. there are 100 values in a row = false. Should we only keep first and last value?
* This will not be very fast: can we loop from start --> end with amount (interval) and check if DateTime is in list2check? (how will we return?)
* better would be if there are points in between 2 points of the reference list, but how to do that practically? (could potentially fix point 2 to some extent)
Does anyone have experience in this? any tips or pointers?
(PS: I have a nice query that can do this in a (postgresql) database, but this does not fit file based datasets)
thanks!
|
|
|
|
|
I'm not sure I completely grok what you're trying to do, but what's wrong with comparing the difference between consecutive timestamps with your "required" interval?
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
|
|
|
|
|