View previous topic :: View next topic 
Author 
Message 
Notquitenewton
Joined: 25 May 2021 Posts: 14 Location: England, UK

Posted: Sun Jan 02, 2022 4:14 pm Post subject: Permutations and combinations with a trolley! 


A bit late but seasons greetings...the blurb under the line Selection.for hopefully explains what I've been trying to do! This problem has no doubt been looked at by better folk than I and with much faster code!
The code seems to run ok and gives the right answers but as the the no. of objects increases the time taken becomes crazy, mainly due to the numbers involved. If anyone has the time or inclination, could you make some suggestions how to speed this up please? The objects placed on a trolley are 1D (length) at present, so my next escapade will be to do this in 2D (length and width).
I thought this might be tricky but it is turning out to be very tricky indeed!!
I'm using FTN95 (64bit option) Vers. 8.8
Many thanks
Notquitenewton
C
C Program: Selection.FOR
C
C Program to make selection of a number of objects from a total
C pile of objects and see if they will fit on a trolley!
C To avoid taking too long, restrict the total number (n) to
C <= 30. At a first attempt try n = 10 to check it's ok. As n
C increases, the number of calculations begins to escalate
C rapidly. The idea is to generate objects of different lengths and
C see which combinations will fit on a trolley of known length.
C Not quite as simple as it first appeared!
C The length of each object is stored in array length() and it's
C reference is used as a pointer in array itempointer().
C The lengths of the items are generated randomly (or the same)
C and will be between ilow and ihigh. The min. amount of trolley
C is stored in imin.
C The other two routines calculate the no. of permutations and
C the combinations using factorials.
C The routines are compiled using FTN95 with /WIN/64 and linked
C using SLINK64 to make the 'selection.exe' file.
C After a run, the results are stored in file Results001.txt which
C should be in the same directory as the program.
C
Link for full code is
https://www.pcmodfit.co.uk/Selection.for
Notquitenewton
Last edited by Notquitenewton on Sun Jan 02, 2022 5:28 pm; edited 1 time in total 

Back to top 


wahorger
Joined: 13 Oct 2014 Posts: 1021 Location: Morrison, CO, USA

Posted: Sun Jan 02, 2022 4:49 pm Post subject: 


Packing algorithm challenge to start 2022!
I have a similar need, but in 2D. There are numerous packing algorithms that one can find online. Most that I have found require that the algorithm run as a recursive algorithm. FTN95 can certainly do that part.
One thing FORTRAN is not designed to do is to define a "class" for the data and attach operations to accomplish the packing. The "trick" would be to define the "C++" class as a Fortran construct. There just isn't any reasonable to do that for the algorithms I have found.
Some of the 2D algorithms target packing the objects in order to minimize the resulting area. One I ran across: https://flipcode.com/archives/Rectangle_Placement.shtml
My specific problem is more like packing the bottom of a utility trailer, where the size (length and width) of the trailer is fixed, the width of each object is fixed, and the length of each object is variable. You're looking to maximize the number of objects that can be packed onto the trailer, minimizing the uncovered "floor".
I look forward to your solution! 

Back to top 


mecej4
Joined: 31 Oct 2006 Posts: 1682

Posted: Sun Jan 02, 2022 6:22 pm Post subject: 


Two suggestions.
A. Do not perform a lot of screen output, especially when you are already doing the same output to a file. Such output is only useful when debugging with small data sets.
B. Instead of calculating nCr by calling the factorial function three times, try the following:
Code:  real function nCr(n,r)
implicit none
integer n,r,i
!
ncr=n
do i=2,min(r,nr)
ncr=ncr*(n+1i)/i
end do
end function nCr 
Note: You called the nCr function "permutate", but the formula is for combinations. 

Back to top 


Notquitenewton
Joined: 25 May 2021 Posts: 14 Location: England, UK

Posted: Mon Jan 03, 2022 4:49 pm Post subject: 


Hi mecej4,
Thanks for the comments...
I only use screen output for debugging (forgot to comment out).
Tried your suggested little bit of code and bingo...goes much more like a rocket. With small numbers of n there isn't much difference as one would expect but as n increases the time difference is excellent indeed, At n >50 I note a speeding up over 1000x and even more so as n approaches 100.
Really chuffed with your help, so thanks very much indeed!
There is just one routine now instead of the previous three.
Regards
Notquitenewton
The single file is linked to...
https://www.pcmodfit.co.uk/Selection.for
for download if you'd like a copy (or anyone else) 

Back to top 


Robert
Joined: 29 Nov 2006 Posts: 406 Location: Manchester

Posted: Tue Jan 04, 2022 7:03 pm Post subject: 


Can't you simulate what a C++ class does with a TYPE and a module? The TYPE contains the data and the module contains the methods that operate on the type? I am assuming here there is no inheritance in the classes... 

Back to top 


wahorger
Joined: 13 Oct 2014 Posts: 1021 Location: Morrison, CO, USA

Posted: Sat Jan 08, 2022 8:49 pm Post subject: 


Robert, you may be able to do this; I don't see why it cannot be done. I will not claim to be familiar with the use of MODULE's and what limitations there might be.
I have created several DLL's using MINGW and CodeLite to compile and link to FTN95 many public domain and Open Source "C" and C++. I would be likely to do that again rather than try to recode/port a large amount of C++ code to FTN. 

Back to top 


