algorithm,list,ocaml,proof , Compute the highest value with a given list and operators in OCaml


Compute the highest value with a given list and operators in OCaml

Question:

Tag: algorithm,list,ocaml,proof

With a given positive integer list and the addition and the multiplication as operators, I want to compute the highest value.

So if my list is [2,3,4], it will be : 2 * 3 * 4 = 24. If there is at least one 1 in the list, it is a little bit more difficult. I found by testing on several examples that to compute the highest value, I have to add 1 to the minimum of the list and etc... until there is no more 1 in the list and compute the product of all integers. For example : [1,2,3,4] would return ( 2 + 1 ) * 3 * 4 = 36; [1,1,2,3,4] would return ( 1 + 1 ) * 2 * 3 * 4 = 48.

My first question is concerning the algorithm part : how to prove properly that my method is correct and will always return the highest value ?

My second concerns the implementation :

I wrote the following code in OCaml to programm it :

(* Return 'list' with the first occurence of 'x' removed *)
let rec remove list x =
match list with
| [] -> []
| hd :: tl -> if hd = x then tl else hd :: remove tl x
;;

(* Return the maximum value which can be computed with the given list*)
let rec test_max list = match list with
  | [] -> 0
  | hd :: [] -> hd
  | hd :: tl ->
    (* If the list contains 1 : remove it from the list, then sort the list to get the min value and add 1 to it *)
    if List.mem 1 list then begin
      let list = List.sort (fun x y -> if (x < y) then 1 else 0) (remove list 1) in
      let test = (List.hd list) + 1 in
      test_max test::(List.tl list);
    end
    else
     List.fold_left ( * ) 1 list;;

And at the instruction

let test = (List.hd list) + 1 in
          test_max test::(List.tl list);

in test_max I get the error :

Error: This expression has type 'a list
       but an expression was expected of type int

Well, I don't really understand why it is expecting an expression of type int in the recursive call ... ?

Thank you in advance :)


Answer:

Function application has higher precedence than ::. So, your code test_max test::(List.tl list) should indeed be test_max (test::List.tl list).

Also, you shouldn't use a ; in this place, as it's used to separate unit instructions. Just put nothing and it'll be fine.

As for some proof hints:

n + m > n * m
<=> ( n + m ) / (n * m) > 1
<=> 1/m + 1/n > 1

As we use positive integers, and as / is decreasing in its second argument. It's easy to see that this is true iff m or n = 1 (equality can be attained when n and m = 2).

Now, how do we use this +1?

(n+1) * m > n * (m+1)
<=> n * m + m > n * m + n
<=> m > n

So here are your two lemmas. I'll let you search for a full proof.


Related:


Filter list using Boolean array


python,list
How can I use boolean array as index to filter a list? For example: >>> l = ['a','b','c'] >>> b = [True,False,False] >>> l[b] The result should be: ['a'] I know numpy support it but want to know how to solve in Python. >>> import numpy as np >>> l...

how to insert into python nested list


python,list,list-comprehension
I want to insert an item into a list inside a list. I'm wondering if someone can show me. list5 = [[], [(1,2,3,4), 2, 5]] print("1. list5", list5) list5.insert(0, (2,5,6,8)) print("2. list5", list5) Output: 1. list5 [[], [(1, 2, 3, 4), 2, 5]] 2. list5 [(2, 5, 6, 8), [],...

Sort List of Numbers according to Custom Number Sequence


list,python-2.7,sorting
Question :A set of numbers will be passed as input. Also the redefined relationship of the digits 0-9 in ascending order will be passed as input. Based on the redefined relationship, the set of numbers must be listed in ascending order. Input Format: The first line will contain the the...

Python RuntimeError: maximum recursion depth exceeded in cmp


python,list,dictionary,recursion
I have a complex data structure that I'm trying to process. Explanation of the data structure: I have a dictionary of classes. The key is a name. The value is a class reference. The class contains two lists of dictionaries. Here's a simple example of my data structure: import scipy.stats...

join two different list by id into one list


c#,list,join,merge,automapper
I've got two different list of two different objects. Then i got one list of a viewmodel that contains properties from both the objects and i want them to be joined into that list. //Product public string id { get; set; } public string unitMeasurement { get; set; } public...

Reverse ^ operator for decryption


c,algorithm,security,math,encryption
I'm trying to reverse the following code in order to provide a function which takes the buffer and decrypts it. void crypt_buffer(unsigned char *buffer, size_t size, char *key) { size_t i; int j; j = 0; for(i = 0; i < size; i++) { if(j >= KEY_SIZE) j = 0;...

group indices of list in list of lists


python,list
I am looking for an elegant solution for the following problem. I have a list of ints and I want to create a list of lists where the indices with the same value are grouped together in the order of the occurrences of said list. [2, 0, 1, 1, 3,...

Sort when values are None or empty strings python


python,list,sorting,null
I have a list with dictionaries in which I sort them on different values. I'm doing it with these lines of code: def orderBy(self, col, dir, objlist): if dir == 'asc': sorted_objects = sorted(objlist, key=lambda k: k[col]) else: sorted_objects = sorted(objlist, key=lambda k: k[col], reverse=True) return sorted_objects Now the problem...

List of tuples from (a, all b) to (b, all a)


python,list,python-2.7,tuples
I am starting with a list of tuples (a,all b). I want to end with a list of tuples (b,all a). For example: FROM (a1,[b1,b2,b3]) (a2,[b2]) (a3,[b1,b2]) TO (b1,[a1,a3]) (b2[a1,a2,a3]) (b3,[a1] How do I do this using Python 2? Thank you for your help....

Knapsack with unbounded items


algorithm,dynamic-programming,knapsack-problem
I am familiar with the 0-1 knapsack problem and when you are given a certain number of copies from each item but I can figure out how to solve it when you are given infinite copies of each item using dynamic programming. I am trying to solve it by hand...

I need to make sure that only certain characters are in a list?


python,regex,string,list,python-2.7
I have this to get input and put it in a list: def start(): move_order=[raw_input("Enter your moves: ").split()] And I only want the characters A, D, S, C, H (it's for a game >_>) to be allowed. I've tried using the regular expressions stuff: if re.match('[ADSCH]+', [move_order]) is False: print...

Django: Handling several page parameters


python,django,list,parameters,httprequest
I have several possible parameter to process in a page. Assume x0, x1, x2,..., x1000. It seems awkward to get and process them one by one by request.GET.get('x0'), request.GET.get('x1'), ... Any idea to put them in a list, so that they can be processed in a loop....

3 X 3 magic square recursively


c++,algorithm,math,recursion
I'm trying to find all possible solutions to the 3X3 magic square. There should be exactly 8 solutions. My code gets them all but there are a lot of repeats. I'm having a hard time tracking the recursive steps to see why I'm getting all the repeats. // This program...

How do I read this list and parse it?


python,list
I'm using requests and the output I get from the sites API is a list, I've been stuck trying to parse it to get the data from it. I use r = requests.get(urlas, params=params) r.json() to get the data I want. Here is a snippet of the list [{'relation_type': None,...

Insertion into a list doesn't reflect outside function whereas deletion does?


list,lisp,common-lisp
I am new to Lisp. Deletion of an item in a list by a function gets reflected outside the function but insertion doesn't. How can I do the same for insertion? For example (defun test (a b) (delete 1 a) (delete 5 b) (append '(5) b) (member '5 b)) (setq...

Understanding Big-Ω (Big-Omega) notation


algorithm,big-o
I was doing some reading on logarithms and the rate of growth of the running time of algorithms. I have, however, a problem understanding the Big-Ω (Big-Omega) notation. I know that we use it for 'asymptotic lower bounds', and that we can express the idea that an algorithm takes at...

How to reduce time to find the n-th place from consecutive digits number for less than 1 second


php,algorithm,digits
I'm following the programming test, and there are questions like this From this consecutive digits: 123456789101112131415161718192021.... For example The 10th digit is 1 The 11th digit is 0 and so on What is the 1,000,000th digit? What is the 1,000,000,000th digit? What is the 1,000,000,000,000th digit? Your solution should run...

Reduction of list dimensions in Python


python,list,indexing,nodes
I'm trying to assign classes to a list of nodes, and separate all nodes into separate lists based on class tag. For example, if we have the following code: #define number of classes MaxC=5 index=[4 4 5 1 4 1 4 5 4 4 3 1 3 3 1 1]...

How can I iterate through nested HTML lists without returning the “youngest” children?


javascript,jquery,html,list,loops
Fiddle: https://jsfiddle.net/zayjeLrk/12/ I want to iterate through an HTML nested list that is 3-layers deep. <ul> <li>animals <ul> <li>birds <ul> <li>crow</li> <li>parrot</li> </ul> </li> <li>reptiles</li> </ul> </li> <li>plants</li> <li>bugs</li> </ul> I want it to iterate through the list so that it returns the elements in this order (note, this isn't...

Algorithmic big o order of growth code


algorithm,discrete-mathematics
I'm doing an online course and i'm stuck on this question. I know there are similar questions but they don't help me. What is the order of growth of the worst case running time of the following code fragment as a function of N? int sum = 0; for (int...

Identify that a string could be a datetime object


python,regex,algorithm,python-2.7,datetime
If I knew the format in which a string represents date-time information, then I can easily use datetime.datetime.strptime(s, fmt). However, without knowing the format of the string beforehand, would it be possible to determine whether a given string contains something that could be parsed as a datetime object with the...

Stopping list selection in Python 2.7


python,list,python-2.7
Imagine that I have an order list of tuples: s = [(0,-1), (1,0), (2,-1), (3,0), (4,0), (5,-1), (6,0), (7,-1)] Given a parameter X, I want to select all the tuples that have a first element equal or greater than X up to but not including the first tuple that has...

Python 2.7 “list index out of range”


python,list
I keep getting "IndexError: list index out of range", the code does fine with things like "s = 'miruxsexxzlbveznyaidekl'" but this particular length makes it throw an error. Can anyone help me understand what I did wrong here, not just give me the answer? (I'd like to not have to...

Create array/list of many objects(initially unknown amount) by tag


c#,arrays,list,unity3d,gameobject
I'm currently working on a radar system for my space game, and I am trying to work out how to add gameobjects, by tag, to either a list or array that can then be used in other methods. I can't do this manually because I will be procedurally generating each...

Java Get and then remove from a list


java,list,setter,getter,instances
In my code i have a list of instances of a class. And i want to get a attribute of 1 instance which is ArrayList. In this class i have implement getters and setters. So I call listofinstances.get(i).getArrayList().remove(0); in order to remove the 1st item of this list. Is this...

How to use XDocument to get attributes and add them to a List


c#,xml,winforms,list
I am trying to load data from an XML file and add it to a List. The XML file looks like this: and this is my code: public void LoadPayments(List<List<string>> list1, List<List<string>> list2) { try { if (File.Exists(Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.ApplicationData), "RentData.xml"))) { int count = 0; XDocument doc; using (var reader =...

Implementing a dictionary function to calculate the average of a list


python,list,dictionary
As always, I've attempted this for awhile before I proceed to ask a question on here. I know there are several attempts at answering this, but none really worked for what I needed. Here are the instructions: Implement the following three functions (you should use an appropriate looping construct to...

chunk of data into fixed lengths chunks and then add a space and again add them all as a string


regex,list,join,ironpython,findall
I have got hex values as a85b080040010000. I want it to be as a8 5b 08 00 40 01 00 00. I have done it by using below code. But I have to work with very large data. So I want computed time to be very low. import binascii import...

Dynamic programming: how to design algorithm for when there are two factors to consider?


algorithm,optimization,dynamic-programming,frequency
I have the following problem and I only have a slight idea about it: Consider a tape storage problem. Given n files of length l1,...,ln and frequencies with which they are accessed f1,...,fn, where sum of all frequencies is 1 and 0<fi<1. "Optimal" means to minimize the average retrieval time...

Getting Wrong Answer in “Longest non regular parentheses sub-sequence ”codechef june cook off


algorithm
I attended a programming competition(it has ended now). I don't know why my solution is giving WA, I read the editorial, saw other people solution but unable to find a flaw in my solution. Obviously I am missing somewhere. Please help! Question Link My Solution My approach If the pattern...

Should checking loop conditions be counted towards total number of comparisons?


c++,algorithm,sorting,c++11
I have implemented three different sorting algorithms and now I want to confirm that my approach of counting the total number of comparisons is correct. In my mind, the number of comparisons shouldn't be tied to the conditional branches because if the condition isn't met, the comparison was still made...

Update list of items in c#


c#,linq,list,updates
I would like to know if you can suggest me an efficient way to update a list of items in c#. Here is a generic example: If CurrentList is [ {Id: 154, Name: "George", Salary: 10 000} {Id: 233, Name: "Alice", Salary: 10 000}] And NewList is [ {Id: 154,...

What is this algorithm mapping coordinates to numbers called?


algorithm,coordinates,coordinate-systems,coordinate
I'm writing a program for visualizing crystals. As a part of the program, I have to generate all different basic points in a lattice structure. For those that aren't familiar with crystallography, you can find the most general cases of these structures here: https://en.wikipedia.org/wiki/Hermann%E2%80%93Mauguin_notation#Lattice_types The problem was that I wanted...

represent an index inside a list as x,y in python


python,list,numpy,multidimensional-array
I have a list which contains 1000 integers. The 1000 integers represent 20X50 elements of dimensional array which I read from a file into the list. I need to walk through the list with an indicator in order to find close elements to each other. I want that my indicator...

Easiest way to Add lines wrong a .txt file to a list


c#,string,list,streamreader
At the moment I am opening the .txt file twice, once to get the number of all the lines, second to add a line to a list as much as how much lines there are in the .txt file. Is there an easier/better way to do this? This is my...

Operand order in Scala List.prepend (::)


list,scala,operators
Odersky has brilliantly optimized Java syntax, enabling object calls without dots and parenthesis. I.e. instead of list.prepend(item), you now simply write list :: item, which also turns language operators into simple object methods. Here, List defines :: (prepend) operator. However, you normally write it vice-verse in Scala, using item ::...

Python - Using a created list as a parameter


python,list,loops,if-statement,compare
When I run my code it tells me: Type Error: unorderable types: str() < float(). I can't figure out why it won't let me compare these two numbers. The list I am using is defined, and the numbers in it have been redefined as floats, so I'm not sure what...

Why cant I refer to a random index in my 4D list, while I know it exists?


c#,list,for-loop,dimensions
I got a 4D list, and I want where I want to display only the [k][3][j][z], but this isnt working. I checked all the counts and they are all 5+, so 3[4] should work... for (int k = 0; k < lijst4D.Count; k++) { for (int i = 0; i...

How to give mathemarical proof or support my answer through reasoning as a general case?


algorithm
You are managing a software project that involves building a computer-assisted instrument for medical surgery. The exact placement of the surgical knife is dependent on a number of different parameters, usually at least 25, sometimes more. Your programmer has developed two algorithms for positioning the cutting tool, and is seeking...

Recursive solution doesn't iterate correctly


ruby,algorithm,search,recursion
I'm working through a toy problem in Ruby: how to produce all possible 10-digit phone numbers where each successive number is adjacent to the last on the keypad. I've represented the adjacent relationships between numbers, and have a recursive function, but my method isn't iterating through the whole solution space....

why java API prevents us to call add and remove together?


java,list,collections,listiterator
As per Java API- IllegalStateException - if neither next nor previous have been called, or remove or add have been called after the last call to next or previous remove()- Removes from the list the last element that was returned by next() or previous() (optional operation). This call can only...

Find the shortest path sum in a matrix. Is Dijkstra not optimal for this case?


algorithm,go
I am trying to solve the following problem from project euler (please take a look at description and the example in the link, but here is the short explanation). in the matrix, find the minimal path sum from the top left to the bottom right, by moving left, right, up,...

Does there exist an algorithm for iterating through all strings that conform to a particular regex?


c#,regex,algorithm
I'm making a script to try and hack into an account whose login password is at least 8 characters long and includes at least 1 number, 1 special character and 1 capital letter. I will use brute force. Is there a compact, elegant and efficient way to iterate through every...

Python regular expression, matching the last word


python,regex,list
I've the following problem. I'm looking to find all words in a string that typically looks like so HelloWorldToYou Notice, each word is capitalized as a start followed by the next word and so on. I'm looking to create a list of words from it. So the final expected output...

Disconnect all vertices in a graph - Algorithm


algorithm,graph
I am looking for an algorithm that finds minimal subset of vertices such that by removing this subset (and edges connecting these vertices) from graph all other vertices become unconnected (i.e. the graph won't have any edges). Is there such algorithm? If not: Could you recommend some kind of heuristics...

Can I put StreamReaders in a list? Or any other way to read a lot of text files at once?


c#,list,text,streamreader
I have a lot of text files and want to read them all by once, how do I do this? This is my code till now: List<StreamReader> lijst = new List<StreamReader>(); using (StreamReader qwe = new StreamReader("C:\\123.txt")) using (StreamReader qwer = new StreamReader("C:\\1234.txt")) lijst.Add(qwe); lijst.Add(qwer); But I get an ObjectDisposedException(Cannot...

Saving elements of a list as data.frames using R


r,list,save,lapply
How can I save each element of a list in a in a separate .RData file? Consider the following example: # Generating a list containing 3 matrices set.seed(1) mylist=list(M1=matrix(LETTERS[sample(1:26,9)],3),M2=matrix(LETTERS[sample(1:26,9)],3),M3=matrix(LETTERS[sample(1:26,9)],3)) mylist[1:2] # $M1 # [,1] [,2] [,3] # [1,] "G" "U" "W" # [2,] "J" "E" "M" # [3,] "N" "S"...

Algorithm for [inclusive/exclusive]_scan in parallel proposal N3554


c++,algorithm,parallel-processing,c++14
Proposal N3554 (A Parallel Algorithms Library) for C++14, proposes (among other things), what seem to be parallel versions of the current std::partial_sum, e.g.: template< class ExecutionPolicy, class InputIterator, class OutputIterator, class BinaryOperation> OutputIterator inclusive_scan( ExecutionPolicy &&exec, InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); With the explanation Effects: For each...

Get element starting with letter from List


java,android,list,indexof
I have a list and I want to get the position of the string which starts with specific letter. I am trying this code, but it isn't working. List<String> sp = Arrays.asList(splited); int i2 = sp.indexOf("^w.*$"); ...

ZipList with Scalaz


list,scala,scalaz,applicative
Suppose I have a list of numbers and list of functions to apply to numbers: val xs: List[Int] = List(1, 2, 3) val fs: List[Int => Int] = List(f1, f2, f3) Now I would like to use an Applicative to apply f1 to 1, f2 to 2, etc. val ys:...