View previous topic :: View next topic |
Author |
Message |
Notquitenewton
Joined: 25 May 2021 Posts: 20 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 1-D (length) at present, so my next escapade will be to do this in 2-D (length and width).
I thought this might be tricky but it is turning out to be very tricky indeed!!
I'm using FTN95 (64-bit 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: 1217 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 2-D. There are numerous packing algorithms that one can find on-line. 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 2-D 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: 1886
|
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,n-r)
ncr=ncr*(n+1-i)/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: 20 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: 445 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: 1217 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 |
|
|
|