CODEWITHSUNDEEP
javaalgorithmtime-complexity
Rishabh Gour
Rishabh Gour

Reputation: 1

How can I decrease complexity of this part of code?

This code prints a combination of elements present in an array "pts" (4 elements at a time) in such a way that a particular combination of digits never occurs more than once. Eg. If 1 2 3 4 is printed already then none of its permutations should get printed.

for (int i = 0; i < pts.length; i++) {
    for (int j = i+1; j < pts.length; j++) {
        for (int k = j+1; k < pts.length; k++) {    
            for (int l = k+1; l < pts.length; l++) {
                System.out.println(""+pts[i]+" "+pts[j]+" "+pts[k]+" "+pts[l]);
            }
        }
    }
}

If anyone can suggest some other approach or can tell me how to reduce this code's complexity. I shall be thankful

Upvotes: 0

Views: 84

Answers (1)

Florian F
Florian F

Reputation: 1377

There is not much you can to to improve this. The output is O(n^4). The complexity is in the problem statement, not in the implementation of this loop. You should look into the reason why you want to enumerate all sets (i,j,k,l) with i < j < k < l.

You could avoid to refer to pts.length in every loop. Depending on what you do in your loop it is not obvious to the compiler that the pts length doesn't change. The following code has only 1 reference to pts.length and still returns all sets with i < j < k < l < pts.length.

for (int l = 0; l < pts.length; l++) {
    for (int k = 0; k < l; k++) {    
        for (int j = 0; j < k; j++) {
            for (int i = 0; i < j; i++) {
                System.out.println(""+i+" "+j+" "+k+" "+l);
            }
        }
    }
}

Note that it changes the order of the generated sets, I don't know if it is important. It is a real small improvement anyway.

Upvotes: 2

Related Questions