Searching extreme points of polyhedron Planned maintenance scheduled April 23, 2019 at 23:30...

Flight departed from the gate 5 min before scheduled departure time. Refund options

Does the main washing effect of soap come from foam?

NIntegrate on a solution of a matrix ODE

How to make an animal which can only breed for a certain number of generations?

Twin's vs. Twins'

Plotting a Maclaurin series

How to name indistinguishable henchmen in a screenplay?

Why can't fire hurt Daenerys but it did to Jon Snow in season 1?

Why is there so little support for joining EFTA in the British parliament?

The test team as an enemy of development? And how can this be avoided?

Why are two-digit numbers in Jonathan Swift's "Gulliver's Travels" (1726) written in "German style"?

Does the universe have a fixed centre of mass?

Short story about astronauts fertilizing soil with their own bodies

Is there a spell that can create a permanent fire?

By what mechanism was the 2017 UK General Election called?

Problem with display of presentation

Why does BitLocker not use RSA?

Found this skink in my tomato plant bucket. Is he trapped? Or could he leave if he wanted?

Can two people see the same photon?

How do Java 8 default methods hеlp with lambdas?

One-one communication

Is the Mordenkainen's Sword spell underpowered?

Do i imagine the linear (straight line) homotopy in a correct way?

Besides transaction validation, are there any other uses of the Script language in Bitcoin



Searching extreme points of polyhedron



Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)
Announcing the arrival of Valued Associate #679: Cesar Manara
Unicorn Meta Zoo #1: Why another podcast?Finding points with the shortest distanceFaster computation of barycentric coordinates for many pointsStrange performance differenceShakespeare and dictionariesFind k nearest pointsClustering points on a sphereClosest distance between points in a listFind the closest parametric values corresponding to a BSpline's control points2D Perlin noise generaton needs PerfomanceEfficiently determining maximum allowed euclidean distance between lists of colors





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}







3












$begingroup$


In my Uni, my scientific professor asked me to make some researches about the extreme points of polyhedrals. And I did them. I found that there is still no code in public for searching extreme points for polyhedral with n dimensions (n - x's), but polyhedrons are everywhere (CV, game theories, etc.). I wrote a function for this task and made a python library (also there are matrix and array combination maker functions).



All I want is to make this code more optimal and compatible for all python versions (I have some troubles that some times happen when I install it by "pip install lin", but other times no). I want to make the life of people easier and make it more comfortable.



I am asking for you to test this function on your computer and write if you have any bugs, fails or thoughts on how to make it better. I am open to constructive criticism and non-constructive too (it will help to understand if somebody needs it or that is just a waste of time).



All the examples, instructions and code on my GitHub: https://github.com/r4ndompuff/polyhedral_set



import numpy as np
import itertools as it
import math
import re

def permutation(m,n):
return math.factorial(n)/(math.factorial(n-m)*math.factorial(m))

def matrix_combinations(matr,n):
timed = list(map(list, it.combinations(matr, n)))
for i in range(n):
timed[i][i][i] = np.asscalar(timed[i][i][i])
all = np.array(list(timed))
return all

def array_combinations(arr,n):
timed = list(map(list, it.combinations(arr, n)))
for i in range(n):
timed[i][i] = np.asscalar(timed[i][i])
all = np.array(list(timed))
return all

def check_extreme(matr, arr, x, sym_comb, m):
sym_comb = sym_comb.replace(']', '')
sym_comb = sym_comb.replace('[', '')
sym_comb = re.split("[ ,]", sym_comb)
for i in range(m):
td_answer = sum(matr[i]*x)
if sym_comb[i] == '>':
if td_answer <= arr[i]:
return 0
elif sym_comb[i] == '>=':
if td_answer < arr[i]:
return 0
elif sym_comb[i] == '<':
if td_answer >= arr[i]:
return 0
elif sym_comb[i] == '<=':
if td_answer > arr[i]:
return 0
elif sym_comb[i] == '=':
if td_answer != arr[i]:
return 0
elif sym_comb[i] == '!=':
if td_answer == arr[i]:
return 0
else:
return 0
return 1

def extreme_points(m,n,A,b,sym_comb):
# Input
A = np.array(A).reshape(m,n)
b = np.array(b).reshape(m,1)
# Proccess
ans_comb = np.zeros((1,n))
arr_comb = array_combinations(b,n)
matr_comb = matrix_combinations(A,n)
for i in range(int(permutation(n,m))):
if np.linalg.det(matr_comb[i]) != 0:
x = np.linalg.solve(matr_comb[i],arr_comb[i])
ans_comb = np.vstack([ans_comb,x])
ans_comb = np.delete(ans_comb, (0), axis=0)
j = 0
for i in range(len(ans_comb)):
if check_extreme(A, b, ans_comb[j], sym_comb, m):
ans_comb = ans_comb
j = j + 1
else:
ans_comb = np.delete(ans_comb, (j), axis=0)
# Output
return ans_comb


And I am uploading some more tests. https://imgur.com/mjweDyy










share|improve this question









New contributor




Andrey Lovyagin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$












  • $begingroup$
    Can you provide some more information on what exactly is going on, from a math standpoint? Is this actually a polyhedron, or a polytope? In how many dimensions? By "extreme", what do you mean? Euclidean norm from (the origin, an arbitrary point)?
    $endgroup$
    – Reinderien
    4 hours ago










  • $begingroup$
    "there is still no code in public for searching extreme points for polyhedral with n dimensions" - I can nearly guarantee that that isn't the case.
    $endgroup$
    – Reinderien
    4 hours ago






  • 1




    $begingroup$
    @Reinderien I am still in the process of deciphering the question. I have a math background, and I share the mother tongue with OP. My impression is that by extremal points OP means the vertices of a simplex where a certain linear form (defined by A, b, and the condition) achieves an extremum. I could be wrong.
    $endgroup$
    – vnp
    3 hours ago










  • $begingroup$
    @vnp That's kind of what I guessed, and if that's the case, linear programming is a quite well-established field already - with some stuff built right into scipy.
    $endgroup$
    – Reinderien
    2 hours ago










  • $begingroup$
    @Reinderien Agreed. Still deciphering.
    $endgroup$
    – vnp
    2 hours ago


















3












$begingroup$


In my Uni, my scientific professor asked me to make some researches about the extreme points of polyhedrals. And I did them. I found that there is still no code in public for searching extreme points for polyhedral with n dimensions (n - x's), but polyhedrons are everywhere (CV, game theories, etc.). I wrote a function for this task and made a python library (also there are matrix and array combination maker functions).



All I want is to make this code more optimal and compatible for all python versions (I have some troubles that some times happen when I install it by "pip install lin", but other times no). I want to make the life of people easier and make it more comfortable.



I am asking for you to test this function on your computer and write if you have any bugs, fails or thoughts on how to make it better. I am open to constructive criticism and non-constructive too (it will help to understand if somebody needs it or that is just a waste of time).



All the examples, instructions and code on my GitHub: https://github.com/r4ndompuff/polyhedral_set



import numpy as np
import itertools as it
import math
import re

def permutation(m,n):
return math.factorial(n)/(math.factorial(n-m)*math.factorial(m))

def matrix_combinations(matr,n):
timed = list(map(list, it.combinations(matr, n)))
for i in range(n):
timed[i][i][i] = np.asscalar(timed[i][i][i])
all = np.array(list(timed))
return all

def array_combinations(arr,n):
timed = list(map(list, it.combinations(arr, n)))
for i in range(n):
timed[i][i] = np.asscalar(timed[i][i])
all = np.array(list(timed))
return all

def check_extreme(matr, arr, x, sym_comb, m):
sym_comb = sym_comb.replace(']', '')
sym_comb = sym_comb.replace('[', '')
sym_comb = re.split("[ ,]", sym_comb)
for i in range(m):
td_answer = sum(matr[i]*x)
if sym_comb[i] == '>':
if td_answer <= arr[i]:
return 0
elif sym_comb[i] == '>=':
if td_answer < arr[i]:
return 0
elif sym_comb[i] == '<':
if td_answer >= arr[i]:
return 0
elif sym_comb[i] == '<=':
if td_answer > arr[i]:
return 0
elif sym_comb[i] == '=':
if td_answer != arr[i]:
return 0
elif sym_comb[i] == '!=':
if td_answer == arr[i]:
return 0
else:
return 0
return 1

def extreme_points(m,n,A,b,sym_comb):
# Input
A = np.array(A).reshape(m,n)
b = np.array(b).reshape(m,1)
# Proccess
ans_comb = np.zeros((1,n))
arr_comb = array_combinations(b,n)
matr_comb = matrix_combinations(A,n)
for i in range(int(permutation(n,m))):
if np.linalg.det(matr_comb[i]) != 0:
x = np.linalg.solve(matr_comb[i],arr_comb[i])
ans_comb = np.vstack([ans_comb,x])
ans_comb = np.delete(ans_comb, (0), axis=0)
j = 0
for i in range(len(ans_comb)):
if check_extreme(A, b, ans_comb[j], sym_comb, m):
ans_comb = ans_comb
j = j + 1
else:
ans_comb = np.delete(ans_comb, (j), axis=0)
# Output
return ans_comb


And I am uploading some more tests. https://imgur.com/mjweDyy










share|improve this question









New contributor




Andrey Lovyagin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$












  • $begingroup$
    Can you provide some more information on what exactly is going on, from a math standpoint? Is this actually a polyhedron, or a polytope? In how many dimensions? By "extreme", what do you mean? Euclidean norm from (the origin, an arbitrary point)?
    $endgroup$
    – Reinderien
    4 hours ago










  • $begingroup$
    "there is still no code in public for searching extreme points for polyhedral with n dimensions" - I can nearly guarantee that that isn't the case.
    $endgroup$
    – Reinderien
    4 hours ago






  • 1




    $begingroup$
    @Reinderien I am still in the process of deciphering the question. I have a math background, and I share the mother tongue with OP. My impression is that by extremal points OP means the vertices of a simplex where a certain linear form (defined by A, b, and the condition) achieves an extremum. I could be wrong.
    $endgroup$
    – vnp
    3 hours ago










  • $begingroup$
    @vnp That's kind of what I guessed, and if that's the case, linear programming is a quite well-established field already - with some stuff built right into scipy.
    $endgroup$
    – Reinderien
    2 hours ago










  • $begingroup$
    @Reinderien Agreed. Still deciphering.
    $endgroup$
    – vnp
    2 hours ago














3












3








3





$begingroup$


In my Uni, my scientific professor asked me to make some researches about the extreme points of polyhedrals. And I did them. I found that there is still no code in public for searching extreme points for polyhedral with n dimensions (n - x's), but polyhedrons are everywhere (CV, game theories, etc.). I wrote a function for this task and made a python library (also there are matrix and array combination maker functions).



All I want is to make this code more optimal and compatible for all python versions (I have some troubles that some times happen when I install it by "pip install lin", but other times no). I want to make the life of people easier and make it more comfortable.



I am asking for you to test this function on your computer and write if you have any bugs, fails or thoughts on how to make it better. I am open to constructive criticism and non-constructive too (it will help to understand if somebody needs it or that is just a waste of time).



All the examples, instructions and code on my GitHub: https://github.com/r4ndompuff/polyhedral_set



import numpy as np
import itertools as it
import math
import re

def permutation(m,n):
return math.factorial(n)/(math.factorial(n-m)*math.factorial(m))

def matrix_combinations(matr,n):
timed = list(map(list, it.combinations(matr, n)))
for i in range(n):
timed[i][i][i] = np.asscalar(timed[i][i][i])
all = np.array(list(timed))
return all

def array_combinations(arr,n):
timed = list(map(list, it.combinations(arr, n)))
for i in range(n):
timed[i][i] = np.asscalar(timed[i][i])
all = np.array(list(timed))
return all

def check_extreme(matr, arr, x, sym_comb, m):
sym_comb = sym_comb.replace(']', '')
sym_comb = sym_comb.replace('[', '')
sym_comb = re.split("[ ,]", sym_comb)
for i in range(m):
td_answer = sum(matr[i]*x)
if sym_comb[i] == '>':
if td_answer <= arr[i]:
return 0
elif sym_comb[i] == '>=':
if td_answer < arr[i]:
return 0
elif sym_comb[i] == '<':
if td_answer >= arr[i]:
return 0
elif sym_comb[i] == '<=':
if td_answer > arr[i]:
return 0
elif sym_comb[i] == '=':
if td_answer != arr[i]:
return 0
elif sym_comb[i] == '!=':
if td_answer == arr[i]:
return 0
else:
return 0
return 1

def extreme_points(m,n,A,b,sym_comb):
# Input
A = np.array(A).reshape(m,n)
b = np.array(b).reshape(m,1)
# Proccess
ans_comb = np.zeros((1,n))
arr_comb = array_combinations(b,n)
matr_comb = matrix_combinations(A,n)
for i in range(int(permutation(n,m))):
if np.linalg.det(matr_comb[i]) != 0:
x = np.linalg.solve(matr_comb[i],arr_comb[i])
ans_comb = np.vstack([ans_comb,x])
ans_comb = np.delete(ans_comb, (0), axis=0)
j = 0
for i in range(len(ans_comb)):
if check_extreme(A, b, ans_comb[j], sym_comb, m):
ans_comb = ans_comb
j = j + 1
else:
ans_comb = np.delete(ans_comb, (j), axis=0)
# Output
return ans_comb


And I am uploading some more tests. https://imgur.com/mjweDyy










share|improve this question









New contributor




Andrey Lovyagin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$




In my Uni, my scientific professor asked me to make some researches about the extreme points of polyhedrals. And I did them. I found that there is still no code in public for searching extreme points for polyhedral with n dimensions (n - x's), but polyhedrons are everywhere (CV, game theories, etc.). I wrote a function for this task and made a python library (also there are matrix and array combination maker functions).



All I want is to make this code more optimal and compatible for all python versions (I have some troubles that some times happen when I install it by "pip install lin", but other times no). I want to make the life of people easier and make it more comfortable.



I am asking for you to test this function on your computer and write if you have any bugs, fails or thoughts on how to make it better. I am open to constructive criticism and non-constructive too (it will help to understand if somebody needs it or that is just a waste of time).



All the examples, instructions and code on my GitHub: https://github.com/r4ndompuff/polyhedral_set



import numpy as np
import itertools as it
import math
import re

def permutation(m,n):
return math.factorial(n)/(math.factorial(n-m)*math.factorial(m))

def matrix_combinations(matr,n):
timed = list(map(list, it.combinations(matr, n)))
for i in range(n):
timed[i][i][i] = np.asscalar(timed[i][i][i])
all = np.array(list(timed))
return all

def array_combinations(arr,n):
timed = list(map(list, it.combinations(arr, n)))
for i in range(n):
timed[i][i] = np.asscalar(timed[i][i])
all = np.array(list(timed))
return all

def check_extreme(matr, arr, x, sym_comb, m):
sym_comb = sym_comb.replace(']', '')
sym_comb = sym_comb.replace('[', '')
sym_comb = re.split("[ ,]", sym_comb)
for i in range(m):
td_answer = sum(matr[i]*x)
if sym_comb[i] == '>':
if td_answer <= arr[i]:
return 0
elif sym_comb[i] == '>=':
if td_answer < arr[i]:
return 0
elif sym_comb[i] == '<':
if td_answer >= arr[i]:
return 0
elif sym_comb[i] == '<=':
if td_answer > arr[i]:
return 0
elif sym_comb[i] == '=':
if td_answer != arr[i]:
return 0
elif sym_comb[i] == '!=':
if td_answer == arr[i]:
return 0
else:
return 0
return 1

def extreme_points(m,n,A,b,sym_comb):
# Input
A = np.array(A).reshape(m,n)
b = np.array(b).reshape(m,1)
# Proccess
ans_comb = np.zeros((1,n))
arr_comb = array_combinations(b,n)
matr_comb = matrix_combinations(A,n)
for i in range(int(permutation(n,m))):
if np.linalg.det(matr_comb[i]) != 0:
x = np.linalg.solve(matr_comb[i],arr_comb[i])
ans_comb = np.vstack([ans_comb,x])
ans_comb = np.delete(ans_comb, (0), axis=0)
j = 0
for i in range(len(ans_comb)):
if check_extreme(A, b, ans_comb[j], sym_comb, m):
ans_comb = ans_comb
j = j + 1
else:
ans_comb = np.delete(ans_comb, (j), axis=0)
# Output
return ans_comb


And I am uploading some more tests. https://imgur.com/mjweDyy







python algorithm numpy homework computational-geometry






share|improve this question









New contributor




Andrey Lovyagin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|improve this question









New contributor




Andrey Lovyagin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|improve this question




share|improve this question








edited 18 mins ago









200_success

131k17157422




131k17157422






New contributor




Andrey Lovyagin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked 4 hours ago









Andrey LovyaginAndrey Lovyagin

161




161




New contributor




Andrey Lovyagin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





Andrey Lovyagin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






Andrey Lovyagin is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.












  • $begingroup$
    Can you provide some more information on what exactly is going on, from a math standpoint? Is this actually a polyhedron, or a polytope? In how many dimensions? By "extreme", what do you mean? Euclidean norm from (the origin, an arbitrary point)?
    $endgroup$
    – Reinderien
    4 hours ago










  • $begingroup$
    "there is still no code in public for searching extreme points for polyhedral with n dimensions" - I can nearly guarantee that that isn't the case.
    $endgroup$
    – Reinderien
    4 hours ago






  • 1




    $begingroup$
    @Reinderien I am still in the process of deciphering the question. I have a math background, and I share the mother tongue with OP. My impression is that by extremal points OP means the vertices of a simplex where a certain linear form (defined by A, b, and the condition) achieves an extremum. I could be wrong.
    $endgroup$
    – vnp
    3 hours ago










  • $begingroup$
    @vnp That's kind of what I guessed, and if that's the case, linear programming is a quite well-established field already - with some stuff built right into scipy.
    $endgroup$
    – Reinderien
    2 hours ago










  • $begingroup$
    @Reinderien Agreed. Still deciphering.
    $endgroup$
    – vnp
    2 hours ago


















  • $begingroup$
    Can you provide some more information on what exactly is going on, from a math standpoint? Is this actually a polyhedron, or a polytope? In how many dimensions? By "extreme", what do you mean? Euclidean norm from (the origin, an arbitrary point)?
    $endgroup$
    – Reinderien
    4 hours ago










  • $begingroup$
    "there is still no code in public for searching extreme points for polyhedral with n dimensions" - I can nearly guarantee that that isn't the case.
    $endgroup$
    – Reinderien
    4 hours ago






  • 1




    $begingroup$
    @Reinderien I am still in the process of deciphering the question. I have a math background, and I share the mother tongue with OP. My impression is that by extremal points OP means the vertices of a simplex where a certain linear form (defined by A, b, and the condition) achieves an extremum. I could be wrong.
    $endgroup$
    – vnp
    3 hours ago










  • $begingroup$
    @vnp That's kind of what I guessed, and if that's the case, linear programming is a quite well-established field already - with some stuff built right into scipy.
    $endgroup$
    – Reinderien
    2 hours ago










  • $begingroup$
    @Reinderien Agreed. Still deciphering.
    $endgroup$
    – vnp
    2 hours ago
















$begingroup$
Can you provide some more information on what exactly is going on, from a math standpoint? Is this actually a polyhedron, or a polytope? In how many dimensions? By "extreme", what do you mean? Euclidean norm from (the origin, an arbitrary point)?
$endgroup$
– Reinderien
4 hours ago




$begingroup$
Can you provide some more information on what exactly is going on, from a math standpoint? Is this actually a polyhedron, or a polytope? In how many dimensions? By "extreme", what do you mean? Euclidean norm from (the origin, an arbitrary point)?
$endgroup$
– Reinderien
4 hours ago












$begingroup$
"there is still no code in public for searching extreme points for polyhedral with n dimensions" - I can nearly guarantee that that isn't the case.
$endgroup$
– Reinderien
4 hours ago




$begingroup$
"there is still no code in public for searching extreme points for polyhedral with n dimensions" - I can nearly guarantee that that isn't the case.
$endgroup$
– Reinderien
4 hours ago




1




1




$begingroup$
@Reinderien I am still in the process of deciphering the question. I have a math background, and I share the mother tongue with OP. My impression is that by extremal points OP means the vertices of a simplex where a certain linear form (defined by A, b, and the condition) achieves an extremum. I could be wrong.
$endgroup$
– vnp
3 hours ago




$begingroup$
@Reinderien I am still in the process of deciphering the question. I have a math background, and I share the mother tongue with OP. My impression is that by extremal points OP means the vertices of a simplex where a certain linear form (defined by A, b, and the condition) achieves an extremum. I could be wrong.
$endgroup$
– vnp
3 hours ago












$begingroup$
@vnp That's kind of what I guessed, and if that's the case, linear programming is a quite well-established field already - with some stuff built right into scipy.
$endgroup$
– Reinderien
2 hours ago




$begingroup$
@vnp That's kind of what I guessed, and if that's the case, linear programming is a quite well-established field already - with some stuff built right into scipy.
$endgroup$
– Reinderien
2 hours ago












$begingroup$
@Reinderien Agreed. Still deciphering.
$endgroup$
– vnp
2 hours ago




$begingroup$
@Reinderien Agreed. Still deciphering.
$endgroup$
– vnp
2 hours ago










1 Answer
1






active

oldest

votes


















1












$begingroup$

I created a rudimentary pull request to your GitHub repo. I won't show all of the content here except for the main file:



import numpy as np
import itertools as it
import math
import re


def permutation(m, n):
return math.factorial(n) / (math.factorial(n - m) * math.factorial(m))


def matrix_combinations(matr, n):
timed = list(map(list, it.combinations(matr, n)))
for i in range(n):
timed[i][i][i] = np.asscalar(timed[i][i][i])
return np.array(list(timed))


def array_combinations(arr, n):
timed = list(map(list, it.combinations(arr, n)))
for i in range(n):
timed[i][i] = np.asscalar(timed[i][i])
return np.array(list(timed))


def check_extreme(matr, arr, x, sym_comb, m):
sym_comb = sym_comb.replace(']', '')
sym_comb = sym_comb.replace('[', '')
sym_comb = re.split("[ ,]", sym_comb)
for i in range(m):
td_answer = sum(matr[i] * x)
if sym_comb[i] == '>':
if td_answer <= arr[i]:
return 0
elif sym_comb[i] == '>=':
if td_answer < arr[i]:
return 0
elif sym_comb[i] == '<':
if td_answer >= arr[i]:
return 0
elif sym_comb[i] == '<=':
if td_answer > arr[i]:
return 0
elif sym_comb[i] == '=':
if td_answer != arr[i]:
return 0
elif sym_comb[i] == '!=':
if td_answer == arr[i]:
return 0
else:
return 0
return 1


def extreme_points(m, n, A, b, sym_comb):
# Input
A = np.array(A).reshape(m, n)
b = np.array(b).reshape(m, 1)
# Process
ans_comb = np.zeros((1, n))
arr_comb = array_combinations(b, n)
matr_comb = matrix_combinations(A, n)
for i in range(int(permutation(n, m))):
if np.linalg.det(matr_comb[i]) != 0:
x = np.linalg.solve(matr_comb[i], arr_comb[i])
ans_comb = np.vstack([ans_comb, x])
ans_comb = np.delete(ans_comb, 0, axis=0)
j = 0
for i in range(len(ans_comb)):
if check_extreme(A, b, ans_comb[j], sym_comb, m):
ans_comb = ans_comb
j = j + 1
else:
ans_comb = np.delete(ans_comb, j, axis=0)
# Output
return ans_comb


This is a first cut mainly for PEP8 compliance, and doesn't solve the bigger issue that you should replace 99% of this with a call to scipy. I'll do that separately (I suspect that @vnp is, as well).






share|improve this answer









$endgroup$














    Your Answer






    StackExchange.ifUsing("editor", function () {
    StackExchange.using("externalEditor", function () {
    StackExchange.using("snippets", function () {
    StackExchange.snippets.init();
    });
    });
    }, "code-snippets");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "196"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: false,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });






    Andrey Lovyagin is a new contributor. Be nice, and check out our Code of Conduct.










    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217855%2fsearching-extreme-points-of-polyhedron%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    1












    $begingroup$

    I created a rudimentary pull request to your GitHub repo. I won't show all of the content here except for the main file:



    import numpy as np
    import itertools as it
    import math
    import re


    def permutation(m, n):
    return math.factorial(n) / (math.factorial(n - m) * math.factorial(m))


    def matrix_combinations(matr, n):
    timed = list(map(list, it.combinations(matr, n)))
    for i in range(n):
    timed[i][i][i] = np.asscalar(timed[i][i][i])
    return np.array(list(timed))


    def array_combinations(arr, n):
    timed = list(map(list, it.combinations(arr, n)))
    for i in range(n):
    timed[i][i] = np.asscalar(timed[i][i])
    return np.array(list(timed))


    def check_extreme(matr, arr, x, sym_comb, m):
    sym_comb = sym_comb.replace(']', '')
    sym_comb = sym_comb.replace('[', '')
    sym_comb = re.split("[ ,]", sym_comb)
    for i in range(m):
    td_answer = sum(matr[i] * x)
    if sym_comb[i] == '>':
    if td_answer <= arr[i]:
    return 0
    elif sym_comb[i] == '>=':
    if td_answer < arr[i]:
    return 0
    elif sym_comb[i] == '<':
    if td_answer >= arr[i]:
    return 0
    elif sym_comb[i] == '<=':
    if td_answer > arr[i]:
    return 0
    elif sym_comb[i] == '=':
    if td_answer != arr[i]:
    return 0
    elif sym_comb[i] == '!=':
    if td_answer == arr[i]:
    return 0
    else:
    return 0
    return 1


    def extreme_points(m, n, A, b, sym_comb):
    # Input
    A = np.array(A).reshape(m, n)
    b = np.array(b).reshape(m, 1)
    # Process
    ans_comb = np.zeros((1, n))
    arr_comb = array_combinations(b, n)
    matr_comb = matrix_combinations(A, n)
    for i in range(int(permutation(n, m))):
    if np.linalg.det(matr_comb[i]) != 0:
    x = np.linalg.solve(matr_comb[i], arr_comb[i])
    ans_comb = np.vstack([ans_comb, x])
    ans_comb = np.delete(ans_comb, 0, axis=0)
    j = 0
    for i in range(len(ans_comb)):
    if check_extreme(A, b, ans_comb[j], sym_comb, m):
    ans_comb = ans_comb
    j = j + 1
    else:
    ans_comb = np.delete(ans_comb, j, axis=0)
    # Output
    return ans_comb


    This is a first cut mainly for PEP8 compliance, and doesn't solve the bigger issue that you should replace 99% of this with a call to scipy. I'll do that separately (I suspect that @vnp is, as well).






    share|improve this answer









    $endgroup$


















      1












      $begingroup$

      I created a rudimentary pull request to your GitHub repo. I won't show all of the content here except for the main file:



      import numpy as np
      import itertools as it
      import math
      import re


      def permutation(m, n):
      return math.factorial(n) / (math.factorial(n - m) * math.factorial(m))


      def matrix_combinations(matr, n):
      timed = list(map(list, it.combinations(matr, n)))
      for i in range(n):
      timed[i][i][i] = np.asscalar(timed[i][i][i])
      return np.array(list(timed))


      def array_combinations(arr, n):
      timed = list(map(list, it.combinations(arr, n)))
      for i in range(n):
      timed[i][i] = np.asscalar(timed[i][i])
      return np.array(list(timed))


      def check_extreme(matr, arr, x, sym_comb, m):
      sym_comb = sym_comb.replace(']', '')
      sym_comb = sym_comb.replace('[', '')
      sym_comb = re.split("[ ,]", sym_comb)
      for i in range(m):
      td_answer = sum(matr[i] * x)
      if sym_comb[i] == '>':
      if td_answer <= arr[i]:
      return 0
      elif sym_comb[i] == '>=':
      if td_answer < arr[i]:
      return 0
      elif sym_comb[i] == '<':
      if td_answer >= arr[i]:
      return 0
      elif sym_comb[i] == '<=':
      if td_answer > arr[i]:
      return 0
      elif sym_comb[i] == '=':
      if td_answer != arr[i]:
      return 0
      elif sym_comb[i] == '!=':
      if td_answer == arr[i]:
      return 0
      else:
      return 0
      return 1


      def extreme_points(m, n, A, b, sym_comb):
      # Input
      A = np.array(A).reshape(m, n)
      b = np.array(b).reshape(m, 1)
      # Process
      ans_comb = np.zeros((1, n))
      arr_comb = array_combinations(b, n)
      matr_comb = matrix_combinations(A, n)
      for i in range(int(permutation(n, m))):
      if np.linalg.det(matr_comb[i]) != 0:
      x = np.linalg.solve(matr_comb[i], arr_comb[i])
      ans_comb = np.vstack([ans_comb, x])
      ans_comb = np.delete(ans_comb, 0, axis=0)
      j = 0
      for i in range(len(ans_comb)):
      if check_extreme(A, b, ans_comb[j], sym_comb, m):
      ans_comb = ans_comb
      j = j + 1
      else:
      ans_comb = np.delete(ans_comb, j, axis=0)
      # Output
      return ans_comb


      This is a first cut mainly for PEP8 compliance, and doesn't solve the bigger issue that you should replace 99% of this with a call to scipy. I'll do that separately (I suspect that @vnp is, as well).






      share|improve this answer









      $endgroup$
















        1












        1








        1





        $begingroup$

        I created a rudimentary pull request to your GitHub repo. I won't show all of the content here except for the main file:



        import numpy as np
        import itertools as it
        import math
        import re


        def permutation(m, n):
        return math.factorial(n) / (math.factorial(n - m) * math.factorial(m))


        def matrix_combinations(matr, n):
        timed = list(map(list, it.combinations(matr, n)))
        for i in range(n):
        timed[i][i][i] = np.asscalar(timed[i][i][i])
        return np.array(list(timed))


        def array_combinations(arr, n):
        timed = list(map(list, it.combinations(arr, n)))
        for i in range(n):
        timed[i][i] = np.asscalar(timed[i][i])
        return np.array(list(timed))


        def check_extreme(matr, arr, x, sym_comb, m):
        sym_comb = sym_comb.replace(']', '')
        sym_comb = sym_comb.replace('[', '')
        sym_comb = re.split("[ ,]", sym_comb)
        for i in range(m):
        td_answer = sum(matr[i] * x)
        if sym_comb[i] == '>':
        if td_answer <= arr[i]:
        return 0
        elif sym_comb[i] == '>=':
        if td_answer < arr[i]:
        return 0
        elif sym_comb[i] == '<':
        if td_answer >= arr[i]:
        return 0
        elif sym_comb[i] == '<=':
        if td_answer > arr[i]:
        return 0
        elif sym_comb[i] == '=':
        if td_answer != arr[i]:
        return 0
        elif sym_comb[i] == '!=':
        if td_answer == arr[i]:
        return 0
        else:
        return 0
        return 1


        def extreme_points(m, n, A, b, sym_comb):
        # Input
        A = np.array(A).reshape(m, n)
        b = np.array(b).reshape(m, 1)
        # Process
        ans_comb = np.zeros((1, n))
        arr_comb = array_combinations(b, n)
        matr_comb = matrix_combinations(A, n)
        for i in range(int(permutation(n, m))):
        if np.linalg.det(matr_comb[i]) != 0:
        x = np.linalg.solve(matr_comb[i], arr_comb[i])
        ans_comb = np.vstack([ans_comb, x])
        ans_comb = np.delete(ans_comb, 0, axis=0)
        j = 0
        for i in range(len(ans_comb)):
        if check_extreme(A, b, ans_comb[j], sym_comb, m):
        ans_comb = ans_comb
        j = j + 1
        else:
        ans_comb = np.delete(ans_comb, j, axis=0)
        # Output
        return ans_comb


        This is a first cut mainly for PEP8 compliance, and doesn't solve the bigger issue that you should replace 99% of this with a call to scipy. I'll do that separately (I suspect that @vnp is, as well).






        share|improve this answer









        $endgroup$



        I created a rudimentary pull request to your GitHub repo. I won't show all of the content here except for the main file:



        import numpy as np
        import itertools as it
        import math
        import re


        def permutation(m, n):
        return math.factorial(n) / (math.factorial(n - m) * math.factorial(m))


        def matrix_combinations(matr, n):
        timed = list(map(list, it.combinations(matr, n)))
        for i in range(n):
        timed[i][i][i] = np.asscalar(timed[i][i][i])
        return np.array(list(timed))


        def array_combinations(arr, n):
        timed = list(map(list, it.combinations(arr, n)))
        for i in range(n):
        timed[i][i] = np.asscalar(timed[i][i])
        return np.array(list(timed))


        def check_extreme(matr, arr, x, sym_comb, m):
        sym_comb = sym_comb.replace(']', '')
        sym_comb = sym_comb.replace('[', '')
        sym_comb = re.split("[ ,]", sym_comb)
        for i in range(m):
        td_answer = sum(matr[i] * x)
        if sym_comb[i] == '>':
        if td_answer <= arr[i]:
        return 0
        elif sym_comb[i] == '>=':
        if td_answer < arr[i]:
        return 0
        elif sym_comb[i] == '<':
        if td_answer >= arr[i]:
        return 0
        elif sym_comb[i] == '<=':
        if td_answer > arr[i]:
        return 0
        elif sym_comb[i] == '=':
        if td_answer != arr[i]:
        return 0
        elif sym_comb[i] == '!=':
        if td_answer == arr[i]:
        return 0
        else:
        return 0
        return 1


        def extreme_points(m, n, A, b, sym_comb):
        # Input
        A = np.array(A).reshape(m, n)
        b = np.array(b).reshape(m, 1)
        # Process
        ans_comb = np.zeros((1, n))
        arr_comb = array_combinations(b, n)
        matr_comb = matrix_combinations(A, n)
        for i in range(int(permutation(n, m))):
        if np.linalg.det(matr_comb[i]) != 0:
        x = np.linalg.solve(matr_comb[i], arr_comb[i])
        ans_comb = np.vstack([ans_comb, x])
        ans_comb = np.delete(ans_comb, 0, axis=0)
        j = 0
        for i in range(len(ans_comb)):
        if check_extreme(A, b, ans_comb[j], sym_comb, m):
        ans_comb = ans_comb
        j = j + 1
        else:
        ans_comb = np.delete(ans_comb, j, axis=0)
        # Output
        return ans_comb


        This is a first cut mainly for PEP8 compliance, and doesn't solve the bigger issue that you should replace 99% of this with a call to scipy. I'll do that separately (I suspect that @vnp is, as well).







        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered 2 hours ago









        ReinderienReinderien

        5,474928




        5,474928






















            Andrey Lovyagin is a new contributor. Be nice, and check out our Code of Conduct.










            draft saved

            draft discarded


















            Andrey Lovyagin is a new contributor. Be nice, and check out our Code of Conduct.













            Andrey Lovyagin is a new contributor. Be nice, and check out our Code of Conduct.












            Andrey Lovyagin is a new contributor. Be nice, and check out our Code of Conduct.
















            Thanks for contributing an answer to Code Review Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217855%2fsearching-extreme-points-of-polyhedron%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            “%fieldName is a required field.”, in Magento2 REST API Call for GET Method Type The Next...

            How to change City field to a dropdown in Checkout step Magento 2Magento 2 : How to change UI field(s)...

            變成蝙蝠會怎樣? 參考資料 外部連結 导航菜单Thomas Nagel, "What is it like to be a...