CODEWITHSUNDEEP
algorithmcombinationsformula
Fernando Tan
Fernando Tan

Reputation: 644

get all combinations of elements and elements can be repeat many times in single combination

I have a problem to get all combinations of elements, and elements can be repeat and reuse for many times, even in a single combination.
For example, I have a box with 100 cm2, then i have below objects:
1) Object A: 20cm2
2) Object B: 50cm2

The expected combinations would be: (A), (A, A), (A, A, A), (A, A, A, A), (A, A, A, A, A), (A, B), (A, B, A), (A, B, A, A) .....

Any combination are allowed, as long as they can fit into the box. Objects can be repeat many times in single combination. However, repeated pattern is not needed e.g. (A, B) is equal to (B, A).

I not sure what is the keyword to search for this question, do let me know if this is a repeated question.

Upvotes: 0

Views: 72

Answers (1)

Dese
Dese

Reputation: 348

Seems to me like a recursive algo would do the job: fit the first object then add all combinations of the next objects (including the one you just included) in the box with a reduced size.

Then do the same with the second object, always using combinations with the next objects in line, not the previous ones (can't have an A after a B).

With your example, you would have:

  • (A)
    • (A,A)
      • (A,A,A)
        • (A,A,A,A)
          • (A,A,A,A,A)
          • (A,A,A,A,B) does not work
        • (A,A,A,B) does not work
      • (A,A,B)
    • (A,B)
      • (A,B,B) does not work
  • (B)
  • (B,B)

Upvotes: 3

Related Questions