-1

I am trying to figure out the most optimized code that will find the list of combinations that are between X, and Y for a given list like below:

  • A = 4
  • B = 6
  • C = 3
  • D = 5
  • E = 4
  • F = 1

And let's say X = 7, and Y = 16

So finds all the combinations whose sum are greater than or equal to X, and less than or equal to Y. The values can be repeated.

That is:

  • AA
  • AAA
  • AAAA
  • ABA
  • ABB
  • ABC
  • ...
  • EE
  • EEE
  • EEEE
  • EA
  • EAA

...And so on

Final condition: Duplicate arrangements should not be included. For example, ABB is the same as BBA, and BAB. So the latter two should not be included.

I am trying to find the most optimised code for this as the input list can contain up to 200 numbers...

anothermh
  • 9,815
  • 3
  • 33
  • 52
cc12345
  • 15
  • 1
  • What? Is it numbers or letters you are asking about? I don't see how the top and bottom of this question relates. – Andreas May 15 '18 at 06:28
  • @Andreas, A = 4, therefore A+A = 8, which is between X = 7 and Y = 16, so it is included, and so is AAA because 3xA = 12 where A = 4 – Alan May 15 '18 at 06:35
  • 1
    What have you tried so far? How your approach look like? – Marcel May 15 '18 at 06:53
  • I see that you have been here on the site recently. Do you have any attempts to share with us? – Andreas May 15 '18 at 09:29

1 Answers1

0

Things you'll need to do:

  1. Loop all our letter combinations
  2. Order the combination alphabetically, so that we can find duplicates. e.g. ABB is the same as BAB - see https://stackoverflow.com/a/9912497/897266
  3. If it's a duplicate, mark it as such or exclude it - see https://stackoverflow.com/a/10096034/897266
  4. Calculate each combinations value - see https://stackoverflow.com/a/49181225/897266
  5. Compare each combinations value to confirm it's within our min/max bounds - see https://stackoverflow.com/a/4684064/897266
  6. If it is then retain it, else mark it as not or exclude it
  7. After the loop, output the set of combinations which pass the test and are not duplicates

I could write that all out in php, but I'm hoping that's enough guidance to give you a fighting chance at it.

Harry B
  • 2,864
  • 1
  • 24
  • 44