How can I decrease complexity of this part of code?

Question

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

No, this is the best you can do. No improvement possible, except for readability. Don't add those awful "// k" comments - they only clutter the code without adding information. — duffymo
– duffymo, Commented Oct 12, 2014 at 12:26
One println command gets executed per thing in the result. How could it possibly be less than this without omitting results? — Paul Hankin
– Paul Hankin, Commented Oct 12, 2014 at 12:28
You are never actually using any value stored in the pts array. Is this intended? — gdiazc
– gdiazc, Commented Oct 12, 2014 at 12:30
If this is a competition, you should definitely mention what you are going to do with the results. You're probably not supposed to only print them. If there is some computation involved, it's very likely that there is a trick that allows you to quickly skip some of the inner loops based on the current values of the outer loops. — Marco13
– Marco13, Commented Oct 12, 2014 at 12:43
@Marco here is the full description for the problem codechef.com/OCT14/problems/CHEFSQUA .... and since it is a problem from a live contest , I don't want you to give a full description of the logic. just help me with how can i choose combinations of 4 points at a time without considering repeated combinations. here's my solution for the problem wikisend.com/download/529854/Square.java — Rishabh Gour
– Rishabh Gour, Commented Oct 12, 2014 at 13:02

Florian F · Accepted Answer · 2014-10-12 15:26:11Z

2

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.

edited Oct 12, 2014 at 15:26

answered Oct 12, 2014 at 12:35

Florian F

1,3871 gold badge13 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How can I decrease complexity of this part of code?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related