I have a set of N blocks of different lengths. The length of each block is a multiple of a basic unit. The blocks, once lined up, make a path of distance equal to R. Let's say we have 5 blocks with the following lengths: N_set_lengths = (1, 3, 2, 1, 3), then the path we cover by lining them up is equal to R = 10. Now, each of these blocks is associated with a different metric m (metric) which depends on the location/position that the block occupies within the path. So a block of length 1 will have R = 10 different m values, one for each of the 10 positions it can occupy within the path, while a block of length 3 will have R-3+1 = 8 different m values.
Here is a graphical representation: -------------------------------------------------------------------------------- block 0: |m0,0|m0,1|m0,2|m0,3|m0,4|m0,5|m0,6|m0,7|m0,8|m0,9| (length 1, 10 different metrics) -------------------------------------------------------------------------------- ------------------------------------------------------------------------------- block 1: |m1,0|m1,1|m1,2|m1,3|m1,4|m1,5|m1,6|m1,7| | | (length 3, 8 different metrics, each metric ------------------------------------------------------------------------------- refers to 3 consecutive units) ------------------------------------------------------------------------------- block 2: |m2,0|m2,1|m2,2|m2,3|m2,4|m2,5|m2,6|m2,7|m2,8| | (length 2, 9 different metrics, each ------------------------------------------------------------------------------- referring to 2 consecutive units) ------------------------------------------------------------------------------- block 3: |m3,0|m3,1|m3,2|m3,3|m3,4|m3,5|m3,6|m3,7|m3,8|m3,9| (length 1, 10 different metrics) ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- block 4: |m4,0|m4,1|m4,2|m4,3|m4,4|m4,5|m4,6|m4,7| | | (length 3, 8 different metrics) ------------------------------------------------------------------------------- Those blocks can be allocated in fact(N) possible different ways to cover the path (In the example considered I have 5 possible blocks to choose from to cover the first part of the path, 4 blocks to cover the second part of the path, and so on). Each of these possible combinations results in a different overall metric which we can define as the sum of the individual metrics that each block gets according to the position occupied within the path. There is at least one combination which is the optimum solution, because it maximizes the overall metric. Finding such a combination is possible but it may require a long processing time. If, for example, the number of blocks is 20 the number of possible combinations is expressed as 2.4*10^18. In the application I'm considering the time is really a constraint so I'm trying to find an algorithm which would give a near optimum solution but with a much lower complexity. Does anyone have suggestion on how should such an algorithm behave (possibly considering implementation issues)? Sorry for the lengthy description, I was just trying to be as clear as possible. Please, don't hesitate to ask questions if the problem statement is not clear. Many thanks and regards Francesco -- http://mail.python.org/mailman/listinfo/python-list
