CODEWITHSUNDEEP
javacombinationsmemory-efficient
Nico Pizzo
Nico Pizzo

Reputation: 105

Finding combinations in a set of numbers efficiently

I am currently working on a java project, and I need one of part of it to give me a list of combination of numbers that fullfils
1<= A<=B<=C<=D<=E<=F<=N where N is any integer as small as 75 which will be taken as the input. A B C D E F can be any integer as long as it fulfills the equality.

I know that I can just simply just go through every combination using brute force but it takes to long. What I want to try to do is split the equality into two separate equalities in a way that still fulfills the original, but it would cut the run in almost half.

Upvotes: 2

Views: 525

Answers (2)

Colin D
Colin D

Reputation: 5661

The following will only generate valid valid combinations. It might take a while for large values of N, but that is because there will be a large number of combinations that satisfy your inequality.

N = 75; 300500200 combinations

N = 100; 1609344100 combinations

    for(int A = 1; A <= N ; ++A) {
        for(int B = A; B <= N; ++B) {
            for(int C = B; C <= N; ++C) {
                for(int D = C; D <= N; ++D) {
                    for(int E = D; E <= N; ++E) {
                        for(int F = E; F <=N; ++F) {
                            // do whatever you want with the combo
                        }
                    }
                }
            }
        }
    }

Upvotes: 0

sampson-chen
sampson-chen

Reputation: 47377

Assuming you want a list of all possible combinations of A, B, C, D, E, F that satisfy the specified condition, you can't get more efficient than doing a brute force backtracking search.

For each acceptable value of A: find all acceptable values of B, then for each of those, find for C... and so on.

You'll get equivalent run time with:

  • divide and conquer
  • dynamic programming
  • greedy (which just reduces to backtracking)

(but these algorithms aren't suitable for this problem and would require contrived implementations)

Upvotes: 2

Related Questions